Hello Codeforces!
On Apr/26/2020 17:35 (Moscow time) Educational Codeforces Round 86 (Rated for Div. 2) will start.
Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.
This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 or 7 problems and 2 hours to solve them.
The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Special thanks to Mikhail darnley Dvorkin for helping in round preparation!
Good luck to all the participants!
Our friends at Harbour.Space also have a message for you:
Hi Codeforces!
You really went for it in the last Educational Round! We had an all-time high participation of 21750 people :) We are happy to support such an awesome community, and look forward to growing these numbers in the future!
We are searching for diamonds in the rough — driven, talented humans, passionate about technology and design, undefined by nationality, gender and cultural background. We know that no diamond is born polished, so our mission is to identify and support as many talented young individuals as we can, so that they can fulfill their potential and secure the future they deserve.
If you are graduating or have already completed a bachelor's degree, we are waiting for your applications for fully-funded Master's degree scholarships by the link below.
Congratulations to the winners:
| Rank | Competitor | Problems Solved | Penalty |
|---|---|---|---|
| 1 | DreamLolita | 6 | 211 |
| 2 | KrK | 6 | 235 |
| 3 | Sugar_fan | 6 | 259 |
| 4 | krijgertje | 6 | 268 |
| 5 | Temotoloraia | 6 | 272 |
Congratulations to the best hackers:
| Rank | Competitor | Hack Count |
|---|---|---|
| 1 | liouzhou_101 | 81:-35 |
| 2 | j_peters | 29:-16 |
| 3 | eR6 | 18:-19 |
| 4 | tonyli00000 | 14:-15 |
| 5 | phyzzmat | 8:-7 |
And finally people who were the first to solve each problem:
| Problem | Competitor | Penalty |
|---|---|---|
| A | sevlll777 | 0:00 |
| B | Aerosmith | 0:02 |
| C | DreamLolita | 0:03 |
| D | xb0nS | 0:14 |
| E | AaParsa | 0:17 |
| F | chemthan | 1:07 |
UPD: Editorial is out
Kudos. " You really went for it in the last Educational Round! We had an all-time high participation of 21750 people "
Lets cross 25000 this time!
Oh no. Think about CF servers.
On last div3 server works fine with 28k registration. So 25k is going to be regular participation.
I hope so.
But this is ‘rated for div.2’ so there will be less participants. Educational Codeforces Round 85 (Rated for Div. 2) has only 21750 people.
Div 3 isn't rated for many people. The no. of people who actually stay throughout the contest is very less. That might be the reason why 28k wasn't a problem.
Div3 has more official participants than educational round. On last div3 round rating changes for 16k people where rating changes for 11k people on last educational round.
Can someone please explain what's a difference between codeforces educational and normal rounds? Thank you.
You can find following difference
Normal codeforces round has a variable points for each problem(500,750,1000 and so on). Each problem has equal points on educational rounds.
In normal coforces rounds you can hack during the contest, in educational round there is 12 hours hacking phase after contest is finished.
Normal codeforces round has 20 penalty for wrong submission where educational round has 10 minutes penalty.
During contest successful submission gives verdict pretest passed where educational rounds gives accepted.
Normal codeforces round judges your last pretest passed solution for each problems and skip other solution for that problem. In educational rounds all your solution will be judged and 1st one will be counted which passes the system test.
In normal round final standing is given based on points earn from all solved problem. In educational round standing is given based on no of solved problem. If no of solved problem is equal then time penalty is used to break a tie.
NB: Div3 rounds follow the rules of educational rounds.
Thank you, sounds like these rounds are not too harsh and beginner friendly.
One other thing, How do you hack during a contest or after its over? After some research I found out it gives you points after successful hacks. What I don't found out how you do it?
In normal codeforces round you have to lock you problem first. When you lock your problem you can't resubmit that problem during contest time. After you lock your problem go to room tab and here you can see solutions of other participants who are in that room. You can hack or see solutions for those problem which you have locked.
Successful hacking gives +100 and unsuccessful attempts give -50.
In educational and div3 rounds you can see any solution you want. Then you can hack one from status page if you think that solution is not fine enough. This hack has no points.
Are there points for hacks in educational rounds?
No
In normal round you got -50 penalty if you passed the problem from pretests
As far as I remember educational rounds also have system tests after them, after hacking phase. So #4 is only about name of verdict, isn't it?
Yes it is only name of verdict.
Really? Or the main system tests are just the added hacked test-cases?
As far i know this also happen in codeforces rounds too.
Why does the educational round give accepted instead of pretest passed?
Normal codeforces round has 50 penalty for wrong submission afaik.
I have a doubt. If the round is rated for only people less than 2100 rating, why is the rank calculated considering all ratings. And also, is there the case with rating change as well ??
Just a doubt ...
Contestants with rating >=2100 are one final standing but rating doesn't change for them. Rating only change for them who have rating less than 2100.
yes, but if they are in the ranklist that means the ones who are below them will suffer rating loss and high ranks..is it the way educational round rating system works ?
Its a doubt !!
They will be not considered while calculating rating. Only rank of official participants will be considered.
thank..so many doubt are now clear..one last question ...is there time for hacking phase after the normal contest like div 1,2??
No. there is no hacking phase in div1,2 rounds. But you can hack during contest.
You can read about educational rounds here
Good Luck everyone
Good luck.Your photo is so cute.
SIMP!
I guess it's a fake profile photo. The photo is of an actress..
No wonder why my contest didn't go well.
But we should hope for short and simple problem statements.
Stronger pretests:)
we do but let's hope that in our hearts I don't think writing hope comments will actually affect the problem statements or how strong pretests are ... just an opinion maybe someone else has a different point of view
SARCASM
and one more "Simultaneously" -_-
I had a +242 in the previous edu round :)
Congrats buddy
I had +88 in previous ^^ I cant imagine how myself was when I solved C accepetedly ^^
Pretests have been extremely shit recently. Like seriously does it hurt to make good pretests and spare us from misery?
Why the educational round harder than normal div 2 round is it a lie or not
_ (Reference — Evro)_
Damn ,Stealing memes even in codeforces..
My intention was not to steal your content(Evro), I simply found it funny and quite relevant to Codeforces while surfing google. So, I simply posted it to make people relate and smile a little. Now, That I know you made it, I tagged you.
Peace
Educational rounds have never let me down.I hope everyone can enjoy this.Good luck and high rating!See you in the top list!
You had to edit your comment thrice to say this?
thrice !! English Language experts prefer to say 'once' and 'twice' instead of 'one time' and 'two times;' but the –ice suffix ends there, –'three times' is standard expression in today's world and not 'thrice. ... To answer the question (title) of this post, 'Yes, 'thrice' is a correct English word; and yes, it is dated! i copy this from google :)
not sure what you mean by "english language experts", but I definitely remember hearing thrice being used so it can't be that archaic
Bro i just search thrice on the google becuase ive never hear that before
Well, you must not be an expert then :p
:/
[removed]
Did you mean: "Codechef"?
Codeforces is one of the best!
It is the "BEST".
I completely agree but your username :p
Yeah!
What people think simultaneously means??
I'm sorry but this round is one of some rounds that mostly made me be confused by its statements :|
simultaneously really ? :( @awoo MikeMirzayanov
Till the last 10 minutes, I thought both of them have to end up at 0 together in a single step and then I see in the contest announcement that x=1 and y=0 become x=0 and y=0." simultaneously" didn't let me solve any further questions.
I feel for you, this took my 40 mins ... RIP Rating
Same here :( I didn't feel like solving any more questions after I wasted time on 'simultaneuosly'
This round should be unrated IMO because of the ambiguity of questions
And
01has period of 2 :| Omg :(that C killed me
I'm really confused that when I choose not to see unoffical participants I see load of yellow and red names in the first 100.How are the D2 participants' rank calculated?Does Codeforces calculate our ranks removing them?
Yes, they appear on the official scoreboard but don't count when calculating the rating distribution.
Sorry to say,but problem statement of A was not clear enough,which caused unnecessary penalty for many contestants.Also there were too many Announcement during the first hour.Hope,next time problem statement will be clear enough! :(
contest is still running(only 6 mins remaining) and i haven't been able to solve a goddamn single problem. wanna die.
that simutaneously word though!! I am irritated!
just realised my mistake, in first question i thought in second operation we're doing x+1,y-1 or x-1,y+1. I SHOULD HAVE READ THE PROBLEM CAREFULLY.
Same for me, I noticed after like 30 minutes.
[removed]
Bait or Naive?
like this
more interesting
XD!!
Your goal is to make both given integers equal zero simultaneously : this statement cost me 5 WA + 63 min to submit
Yeah , the term "simultaneously" is diverging from the actual question.
What is test 3 of C?
I can guess its something like this click
Am I the only one who dislikes problems like D where you need to print one of the solutions rather than just saying what the minimum value of best solution would be? Seems annoying to code.
I don't think it requires much additional coding: Just put the elements in a cyclic order into the output arrays:
https://mirror.codeforces.com/contest/1342/submission/78163277
It doesn't require much coding, but it feels like it was put there just to trip up contestants who didn't read carefully. (I'm also biased because I got tripped up as well)
Can we print the cyclic order starting from the smallest element? Thank you
yes
Sometimes I like that style; often (like today) it's a big hint to contestants that the solution to the problem is greedy and not dp.
I don't see how it's a "big hint" that it's greedy. Many dp solutions can be reconstructed and printed out in a batch like this too, like Thursday's Div1B/Div2D.
Problem C — test case 3. Can I have some example?
In problem A, the word 'simultaneously' has been used in a very wrong way. Because of this, I thought if we have states (0,1) first we have to go to (1,1) and then to (0,0). It cost me 3 penalties and complete waste of 1 hr.
How about using 'both' instead of 'simultaneously'?
We used this word to cover the fact that you cannot make, for example, $$$x = 0$$$, then make $$$x \ne 0$$$, and then make $$$y = 0$$$ without making $$$x = 0$$$. And the notes for the first example showed that $$$(0, 1)$$$ to $$$(0, 0)$$$ is possible.
I don't think that there is a perfect wording for such problems (''both'' implies some questions like ''can we make $$$x = 0$$$, then make it non-zero, and then make $$$y = 0$$$''). Perhaps a lot of inline-examples would help, but make the statement much more cumbersome.
Contest should be unrated as problem statement was really confusing
I too got 2 wrong submissions and it caused confusion to a lot of people, but simply because of that you cannot make whole round unrated!
I don't think so , i was able to understand problem statement very easily ,Although ,i am not a native english speaker.
I politely disagree with you. If you will see some other questions here, simultaneously implies that both reach together. The distinction is that of "simultaneously reaching zero" and "simultaneously being zero" I think, and in this question they meant "simultaneously being zero".
Though in contest one can always ask question and clarify, I did that. But rating suffers if one is not able to solve other questions.
Your example added more confusion.
exactly! instead of saying that the word simultaneously is not to be considered!The explanation was more confusing!
How though would it make a difference if you didnt cover up that fact?
The word "simultaneously" used in this context literally (in all sense) means that going from state 0,1/1,0 to state 0,0 is not correct
Why does it mean so? If we go from $$$(0, 1)$$$ to $$$(0, 0)$$$ then both numbers are $$$0$$$ simultaneosly.
Because "simultaneously" means "at the same time" or "at the same instant" (try googling it)
and making x and y to 0 simultaneously means making them 0 at the same time/instant
This is from the problem statement "Your goal is to make both given integers equal zero simultaneously". Here, you didn't make both given integers equal zero simultaneously because one has been already zero the other non-zero.
The last operation makes them both $$$0$$$ at the same time, so the condition is met.
Okay, there might be more than one way to understand it, but the example notes and the clarification system are working for exactly this reason — if you think that you don't understand something, ask a clarification.
Well, I thought I understood the problem as the way I explained, and sadly that interpretation of the problem statement works on the sample cases.
But it does not work on notes (which are part of the statement).
I don't think an explanation to a test case justifies an incorrect statement. Everybody is more likely to read the statement and the testcases rather than the explanation to the testcases, especially for problem A
It wasn't one of they way one could understand it. It was the right way to understand. Yes, one could have got the intended meaning by looking at the notes, so to demand that contest be unrated is not sensible at all.
But please refrain from using words you don't know the exact meaning of.
No, problem statement is correct. They are zero at the same time instant (simultaneously) at the end of the operations. That's it. The fact that one of them was zero beforehand does not matter.
in a way that is simultaneous (= happening or being done at exactly the same time):
this is from the dictionary, which clearly states being done at the same time. x and y would be 0 after the operation does not mean x and y became 0 simultaneously.
I am not disagreeing that it could have been worded better to avoid any confusion at all. But the author's usage of simultaneously is not wrong.
Regardless, the round should remain rated.
The author's usage of simultaneously is incorrect
The statement specifically mentions
"Your goal is to make both given integers equal zero simultaneously"
If it did not have the word "make" I would have accepted the problemsetter's interpretation of things, but adding the word "make" in the same sentence suggests that both x and y have to BE MADE equal to 0 at the same time and not that they have to both BE 0 at some time.
Regardless, the round should remain rated
I never said anything about the round being rated or unrated. Just wanted the authors to know that statement was misleading for some people which could have been avoided.
You're trying to make them both be 0 simultaneously, not change them to 0 simultaneously, and the problem statement obviously said the former way.
Exactly, making them zero at exactly the same time , that's what simulataneously means. And honestly if you are differentiating between make and change then by doing so even you are agreeing that it was ambigous.
the statement said "make both", not "make both be"
make both suggests changing them to 0 simultaneously
If you change one to 0 after the other, you're still making both given integers equal zero at the same time, not implying you have to change them at the same time. I don't get the confusion.
The debates reached maximal permitted depth Let us stop, we both are viewing it from different angles and thus it seems different to both of us.
yes both numbers are zero simultaneously, but the statement says "your goal is to make both numbers equal to zero simultaneously". This is a dangling modifier as it is unclear whether "simultaneously" refers to the numbers being equal to zero, or to making the numbers equal to zero.
I think removing the "simultaneously" actually makes the statement clearer. If you want to emphasize that both numbers need to be zero at the end, I would prefer phrasing it as "your goal is to make both numbers zero after all the operations"
(just sharing what I think people are complaining about, I understood the statement in one try because of the example)
You could perhaps say, at the end of all operations, $$$x$$$ and $$$y$$$ must both be $$$0$$$. The current statement wasn't optimal (the announcement could have been part of the problem statement), but I agree that the question itself wasn't ambiguous.
test 2 for problem A is just making me nuts..
I guess you missed "long long". The answer is overflowing integer limits.
I reduced the problem E to the following:
Distribute n distinct objects into n-k distinct bags such that each bag gets at least one object. This is solvable through Inclusion-Exclusion but how to do it efficiently? Is there any other way to solve the problem?
yes, i also reduced to exact same, but cant move ahead after that.
.
Another solution described here
The number of ways to put $$$n$$$ objects into $$$n-k$$$ bags is $$$(n-k)^n$$$. This also counts all the configurations with one empty bag, so we should subtract $$$(n-k-1)^n\cdot\binom{n-k}{1}$$$ (number of ways to choose the 1 empty bag, and put $$$n$$$ objects into $$$n-k-1$$$ bags). Now, this subtracts off too many configurations with two empty bags, so we should add $$$(n-k-2)^n\cdot\binom{n-k}{2}$$$. Continuing this gives the answer as
Thanks emma, I just saw your submission. Damn it! It didn't occur to me to use binary exponentiation to solve it. I just gave up after reaching the expression :(
After you've decided a distribution with positive integers $$$a_1,...,a_{n-k}$$$ and $$$\sum a_i = n$$$, you can arrange them in $$$\frac{n!}{\prod a_i!}$$$ ways. So the answer is coefficient of $$$x^n$$$ in $$$\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\right)^{n-k}=\left(e^x - 1\right)^{n-k}$$$. Now you can expand it with binomial theorem and extract answer in $$$\mathcal O(n)$$$.
Can you tell how you reduced the problem to this?
To attack every empty cells, either every row or every column contains a rook (both only if $$$k = 0$$$). Now notice that , if, say, you have decided to fill every column, you will have to group pairs of attacking rooks within the different rows. A row will consist of possibly $$$0$$$, or more rooks. $$$n$$$ rooks means $$$n-1$$$ pairs, for $$$n \geq 1$$$. Now we are almost there for the reduction. There will always be $$$n-k$$$ groups of row (or "used" row if you prefer). If less, it can be shown that there are too much pairs. If more, there are not enough. The $$$n-k$$$ rows are the "bags". The position of the rooks in the columns is important. That is why you have the forumla $$$(n-k)^n$$$ at the beggining.
At the end you also need to multiply by two if $$$k=0$$$ (because of what I said at the beggining) and... you have to take into account that you also have to ditribute the "bags" ($$$n-k$$$ of them) to the different rows ($$$n$$$ of them). This is yet another binomial coefficient.
I hope this was somewhat helpful, the editorial should be better at explaining the solution anyway :)
Thanks a lot for the great explanation
I would like to add an explanation for "why exactly n-k groups of row?" Let q denote the number of chosen rows. Assume our chosen rows are r(1), r(2) ... r(q). Let Cr(i) denote the number of rooks in each row. As the number of attacking rooks for each row is Cr(i)-1 , so we have this equation: Cr(1)-1+Cr(2)-1+ .. +Cr(q)-1 = k
From this we can get Cr(1)+Cr(2)+...+Cr(q) = k+q
So q = Cr(1)+Cr(2)+...+Cr(q)-k = n-k
for future reference
Video tutorials here for some of the tasks, you can also join my discord server for more insights
C
D
Wierd Runtime, please help! I am getting Runtime Error on submitting div2D on Codeforces on 1st sample, but same code & input runs & produces perfectly correct output on online IDE at Codechef.com/ide !
https://mirror.codeforces.com/contest/1342/submission/78209696
How is that possible? I have correct code but can't get accepted because of this. MikeMirzayanov awoo
When weird stuff like this happens, this usually means that your code has undefined behavior (like indexing an array with an invalid index or using the value of an uninitialized variable).
I cross verified, there seems no variable uninitilaized. set I am using, made sure to only erase if a value exists. That makes me believe, there is no undefined behaviour. Please point out if I am missing something. Thanks Be_dos
RTE is because you are looping through set and erasing from it both in the same loop.
for (auto cq: mem)andmem.erase(cq);. Mike might not be able to offer any help here.Shit! I am happy yet sad. Too much thanks for the catch! i_love_arya_stark
same thing happens to me also.
https://mirror.codeforces.com/contest/1342/submission/78207115
My code also gives a runtime error. I tried on CodeChef ide also, it works perfectly. But I can't find the reason.
"Your goal is to make both given integers equal zero simultaneously"
Why on earth did you have to use the word "simultaneously"? I thought it means we have to use operation 2 to go from 1 1 to 0 0 (to make it simultaneous) I wasted more than 20 mins on this until i read the description of the test case and asked the question to the setters
lmao same, just added to consider the case 'a' on both x and y and it got accepted
EDIT: sad thing is, i just noticed that problem statement says 'move from 0:1 to 0:0 is valid'
I missed placing exactly n rooks part in E and tried solving this problem for almost entire duration of the contest: placing some x rooks on the board such that either all rows are occupied or all columns are occupied (or both). :/
Is there a way to place less than $$$N$$$ rooks and cover each square? I don't think so.
Can place more though
how to solve F?
The word simultaneously in the text of Problem A was seriously misleading. It made it seem like the last operation must have been of type 2 so that both values would arrive at 0 simultaneously.
wait that wasn't what they meant?
Apparently the values could arrive to 0 at different steps, as well. They made an announcement stating that during the contest.
I misunderstood the term "simultaneously" and wasted 15 mins.
Problem A made me zoned out for 25 mins.
Upsolving C and D live on YouTube: https://youtu.be/XeK6lYKd8W4
So my code for problem 'C' decided to run correctly 10 seconds after the contest cool cool cool cool cool cool cool cool cool cool cool cool cool cool
https://mirror.codeforces.com/contest/1342/submission/78208967
what's wrong in this solution for C?
Try this .
1
3 4 1
12 12
Ans should be zero but your code gives 1 .
include
include
include
include
include
include
include
include
include
include
include
include
include
include
define endl "\n"
define pb push_back
define ll long long int
using namespace std; int main() { int t; cin>>t; while(t--) { ll a,b,q; cin>>a>>b>>q; if(a==b) { for(int i=0;i<q;i++) { ll l,r; cin>>l>>r; cout<<"0"<<" "; } cout<<endl; } else if(a<b) { ll k=0;
for(int i=0;i<q;i++) { ll l,r; cin>>l>>r; ll cnt=0; cnt=r-max(l,b)+1; if(b%a!=0) cnt-=b*((r/a)/b-(max(l-1,b-1)/a)/b); else { ll g=__gcd(a, b); cnt-=b*((r/g)-(max(l-1,b-1)/g)); } cout<<max(cnt,k)<<" "; } cout<<endl; } else { ll k=0; for(int i=0;i<q;i++) { ll l,r; cin>>l>>r; ll cnt=0; cnt=r-max(l,a)+1; if(a%b!=0) cnt-=a*((r/a)/b-(max(l-1,b-1)/a)/b); else { ll g=__gcd(a, b); cnt-=a*((r/g)-(max(l-1,b-1)/g)); } cout<<max(cnt,k)<<" "; } cout<<endl; }} return 0; }
how about now??
At least put your code in spoiler ....
1
9 12 1
1 192
Ans is 121 and your code gives 169 .
In problem A, the word 'simultaneously' confused me. Because of that, I thought if we have states (1,0) first we have to go to (1,1) and then to (0,0). It cost me 3 penalties and waste of 25 minutes.
just simple English, simultaneously means at same time. so A and B have to be zero at same time. you're not even supposed to have 1 0 in first place
Hi, I tried a greedy solution for D. I sorted an array and added tests from the smallest, for each of them checking how many more I could add to one testcase. It got WA on test 11.
What do you think is the counterexample?
Try this:
You can construct an answer with 3 multitests instead of 4 as given by your code.
I cannot understand why this test case would give WA for greedy, I think it works!
Thanks! This is what I missed. The greedy solution doesn't work for repeated elements.
Can you please explain why it wouldn't work?
You can make such testcases: {1 2} {1 2} {3} Whereas my solution would give: {1 1} {2} {2} {3}
Hey MikeMirzayanov, I got unnecessary 2 WA in problem A because I considered the condition to make both x and y simultaneously zero. Though I can't ask back the overall time lost due to this but if possible can those two penalties be removed! Thanks in Advance.
in correction too! it was not mentioned correctly that simutaneously is not to be considered! worst educational round!!
A and B again supersimple problems hidden in complecated text.
In A I needed half an hour to get it that we cannot use opposite signs in operation b. Of course the statements states so, but that was mostly invisible to me.
And D, sorry, simply to much words, I am not able to understand the sentences.
Usually posting like this get downvotes. I know. Thanks.
And your C is hacked now !
Yes, I was expecting that, the solution wasn't that great.
Check Mine it is accepted now!
What's wrong with my solution of F?
What's the meaning of "wrong answer 'to' position should be in [1, 14] (test case 4)"？
my submission
It looks like you print an auxiliary action somewhere in test case 2, so the numeration changes.
Well,I thought that I had printed the same answer as the example ouput,in test case 2.
Sorry,I made a mistake.
Can someone tell me where my greedy approach for D fails. Here is what I did I sort the tests with respect to their sizes. I pick the array with largest size and put it in first testcase. Now I pick the next largest array , say of size X and the testcase with minimum tests till now and check if No. of tests in this testcase + 1 <= c[X]. If the condition holds, I put this test in the chosen testcase, otherwise make a new testcase. I got a wrong answer on TC 11
try this test case :
8 4
1 1 2 2 3 4 3 4
2 2 1 1
Expected Output :
4
2 4 1
2 4 1
2 3 2
2 3 2
I couldn't understand how the greedy solution with your test case would give a different answer. Can you provide any other test case?
Kill me !! Kill me. My Greedy approach is correct . There was a single line I missed in the implementation. I used a min heap and I forgot to insert the previous topmost element(which I had popped) whenever I am creating a new testcase. It got accepted now and I am confused why could not I find this in more than an hour.
It happens...
In Problem C,
O(test * 3 * gcd(a, b)) times remainder calculation cost TLE on test 4. Does the remainder calculation cost this much?
:(
Your time complexity for solution 78195345 is O(test * q * a * b). For every test, for every query you iterate x at most len times (which can equal to a * b) so you have around 100 * 500 * 200 * 200 = 2e9 operations times constant. You also have remainder calculation so I guess it is a rather predictable verdict.
Ohh! Thanks. My Bad...
But how this solution passed 78177360? I think it is also O(T*q*a*b). The time limit was 3.5 sec though.
Then I was wrong and this solution passes because it has precalculated remainders and the previous one did not.
How is 78182933 doesn't get TLE?
It has linear complexity for every query or did I miss something?
As far i understand he calculates curr in the loop which is never used after that. As it is never used so compiler removes that loop as a part of optimization. As a result the loop doesn't get a chance to run so there is no tle.
Thanks, you were right. I don't know that compiler can skip unnecessary operation.
Question C: Which number $$$x$$$ in the range $$$[100,200]$$$ other than $$$141-149$$$ gives $$$(x \mod 7)\mod 10 = (x \mod 10)\mod 7?$$$ The answer is $$$91$$$, so there should be $$$10$$$ such numbers.
140
omg...........*cries in a corner*
Fail on 1605th number.
Oh cmon? How can I debug? 78209018
Here's your case:
1
21 14 1
291 823
Could you please tell 48011th number of test case 2? please.
1
48 32 1
16 99
How do you find the test cases?
Got no idea what's wrong with my C submission.
Could anyone take a look at it? https://mirror.codeforces.com/contest/1342/submission/78197703
Why do you post the link of this blog here?
You should've at least posted your submission (78197703) here and not the link of the blog entry.
Update the link to submission
one major thing is the for loop from l to r.
the range can be way orders of magnitudes over 10^9 .. so you'd get TLE even if your solution passed test 3.
is it possible to solve C without prefix sum / dp ?
There's a dp/prefix sum solution for C?
I just excluded the numbers from i*LCM(a,b) to i*LCM(a,b)+max(a,b) for i=0,1,2,3.. from the range l to r
Yes it can be solved. You can check my submission https://mirror.codeforces.com/contest/1342/submission/78176991
You can use the fact that x%a%b == x%b%a occurs at every multiple of lcm(a, b) for exactly max (a, b) times. You just get that and you have your answer in O(1) for each query, or log(n) if you consider GCD.
I've tried things similar to this but it's not working for me https://mirror.codeforces.com/contest/1342/submission/78229431
can you tell any counter case on which this will be failing ?
UPD: Just figured I was unnecessarily assuming that if a and b are divisible then the o/p will always be 0. thanks for the help tho
i also assumed the same and was getting WA on test 2 can you pls explain why that assumption is wrong my submission on c
I also put the same condition though, and mine is accepted, so it must be something else, I will try looking into test cases after system testing.
The problem was not the a and b divisible condition, but you did not take inputs when they were divisible. You just printed 0 q times. you should also take left and right inputs.
that fucking simultaneously word in problem A .......
I don't even understand what are you talking about.
they have mentioned that we have to convert x and y into zero simultaneously and later they made an announcement that it is not req.
I agree that it might be misleading but I didn't have any problem with understanding that word. I take it as the meaning of a simultaneous equation and didn't notice that word until I see this comment.
Pls don't take it as the meaning of a simultaneous equation...
Please never take it as the meaning of a simultaneous equation dude
simultaneously means at the same time, doesn't it?
exactly bro but then they later said that it is not req.
(https://mirror.codeforces.com/contest/1342/submission/78163668)
(https://mirror.codeforces.com/contest/1342/submission/78134634)
Exactly same solutions[user:MikeMirzayanov][user:pikmike] Disqualify both of them from contest
Hm, my idea for E was wrong, but I don't know how:
Something like, when $$$0 < k < n$$$, we know either all rooks will be on distinct cols or all rooks will be on distinct rows, (and not both since $$$k \neq 0$$$), since two rooks sharing a col and two rooks sharing a row would leave some row and some column untouched (and thus the square at their intersection untouched). Then, we can WLOG assume all rooks are on distinct rows.
Consider all the columns that contain a rook. If we consider all the rooks on that column a path graph, we see that it contributes exactly the number of edges it has to the number of pairs that attack each other. However, we also know that there will be $$$k$$$ edges in total, and since the whole graph is a forest, there should be $$$n-k$$$ components, i.e. $$$n-k$$$ columns containing rooks. So, the question then becomes how to partition $$$n$$$ objects into $$$n-k$$$ nonempty components (stirling # of second kind), and then multiply that by the $$$n-k$$$ columns that the rooks can occupy, and then multiply that by 2 to account for distinct columns cases.
Anyone know where the error in this logic is? I plugged the formula into wolfram (mod[2*stirlings2[1337, 1295]*(1337 choose 1295), 998244353]) for test 4 and it was incorrect.
EDIT: As BledDest pointed out, one just needs to multiply this final formula by $$$(n-k)!$$$ to index the columns for specific subsets, then it should be fine.
When you multiply the stirling # of second kind with a coefficient to choose $$$n - k$$$ columns, you should consider the fact that the subsets in definition of stirling numbers are not indexed.
Ah, good catch! Simple change to the formula. Thank you!
shouldn't answer be simply stirling(n,n-k)*chose(n,n-k)*2 ?
Stirling number would count all required possible arrangements. Let one such possible arrangement be set1. Set1 would contain n-k elements, each element would correspond to a valid arrangement for a column.
Then you have to select n-k columns from the board to place those valid arrangements (combinations), let the set of selected columns be set2.
Then each different function from set1 to set2 would correspond to a different way you can arrange the rooks. (The function needs to be one-one and onto i.e invertible). Number of different functions from set1 to set2 is (|set1|)! or (n-k)!.
You can also think of it as you have n-k diffrent objects and you need to put them in n-k different slots, how many ways are there to do it (permutations).
Hope it helps!
thanks bro!!!
https://mirror.codeforces.com/contest/1342/submission/78214455 what's wrong in this for C
a counter test case in case it helps : 1 248 12 2 491 1289 839 1234
o/p for this should be 551 243 .
Hope this helps !
Thanks.
The only contest u joined is an April Fools’ Contest. Why would u even expect it to be a rated round.
The first contest you took part in was April's Fools so it was unrated There is a 12 hour hacking phase after the contest so wait and you will get your rating tommorow.
My rating and confidence level is going down simultaneously....Thanks for problem A.
xD same happened with me too!
Time Limit of problem C was misguiding.
Why? You can answer each query in O(1)
For problem B, I approached the question the same way as others. Printing "01" up to s.length() times. But in the clarification panel, the value of k for string "0011" is 4 but it is 2 if we print "01" up to n times(n == s.length()). Can anyone explain what am I missing here?
I think you are right. The statement of B make me confused!
it just states the definition of a period. Explanation in clarification panel is not much related to original problem.
task A
Wait darn solved ABD and didn't get C...played around with gcds/mods and found some progress but whatever. Why doesn't O(ab(t+q)) pass? It's the naive solution but it seems to be well within the time limit of 3.5 seconds (2.4*10^7 operations -- i've had solutions with more operations and less time pass)
You can do it in O(t*(ab+q)) if you precalcutate a prefix array. Such solution of mine took 498ms.
This is one thing and the second is maybe Java is slower than C++.
Ah ok, I should have done prefix array, maybe the complexity would have been reduced by a constant factor and pass but yeah C++ is definitely faster than java too :(
can you please tell me how many max operation can be done in 1 sec
Not entirely sure but somewhere between 10^7 and 10^8 (since for some problems O(N^3) for N=500 passes and some other variants which have >=10^8 operations)
and also how mush time should i spend on C and then jump to D.
Yeah, I also didn't get why the TL. No idea why my solution failed. But in the end I managed to do O(1) per query. The main thing to notice was that every number from b to lcm-1 is good. So you don't even need to precalc anything first and can answer each query in constant time.
can you please explain
First you need to check how many numbers are there between 1 and lcm-1 that satisfies the property. Let's say a is smaller. Then any number X greater than or equal to b will satisfy. We can prove this as follows.
Let's say X = bq+r, Then (X%b)%a = r%a. Now we need to write (X%a)%b in similar form. Here notice that bq is less than X, and since X is less than the LCM, bq is also less than LCM. Therefore it can't have a as a factor.
So bq = aq'+r'. Therefore X = aq'+r'+r. Taking modules, we will get (r+r')%a.
Since r' is neither 0 nor a, therefore it is different than r%a. Thus any number greater than equal to b satisfies.(Upto LCM that is)
how are you comparing (r+r')%b and r%a???
(X%a)%b is reduced to ((r+r')%a)%b. If you notice, the second modulo by b is unnecessary as (r+r')%a is always less than b. So it reduces down to comparing r%a and (r+r')%a
You can answer each query in O(1).
I just excluded the numbers from i*LCM(a,b) to i*LCM(a,b)+max(a,b) for i=0,1,2,3.. from the range l to r. Mycode
Came up with the same logic during the round, but sadly my implementation was a complete garbage. :/
It is too hard to read the Problem D statement.
"Your goal is to make both given integers equal zero simultaneously"
If it did not have the word "make" I would have accepted the problemsetter's interpretation of things, but adding the word "make" in the same sentence suggests that both x and y have to BE MADE equal to 0 at the same time and not that they have to both BE 0 at some time.
This cost me 3WAs and almost 20 minutes
I'm disappointed
i ll change my username to "Simultaneously" next year as a reminder for today's problem A!
Why does life as well as codeforces keep on fucking with me simultaneously! Eh? Thanks to Problem A.
i tried solving question C using digit dp as I was recently studying this, while solving I realised it would tle as my dp was having high dimensions for modulus of a and b, can anyone tell me how to do it using digit dp if possible
I dont think so TLE. Because a,b<=200. Should have passed with 3.5 seconds. :)
their lcm can be as high as 40000 , so it might give tle if I set mod variable this high my dp looks like dp[position][tight][start][mod], here mod can be upto 40000, position upto 20, tight is bool, start is bool, plus 500 queries and 100 test cases
Please uphack my solution to F. I am not using any kind of bitmask dp.
UPD:Got hacked by one of the authors. That's kinda cool. Thanks Neon.
UPD2:Somehow I made it work in 1.5s just by reserving memory for vectors.
Am i the only one who felt much more easier with D than C? For me, D's approach was quite simple, which i can't say for C (and also TL for C kinda confused me).
For me ABCD was quite hard, and, well, E was to hard at all :/
Is C solvable with digit dp? If yes, it would be awesome if someone explain the solution with digit dp.
Thanks in advance. :)
Problem C can be solved in $$$\mathcal O(1)$$$ per query (assuming it takes constant time to compute GCD) without any preprocessing. Assume $$$a < b$$$ and take some $$$x = qb+r$$$ with $$$0\leq r < b$$$. Then $$$(x\bmod a)\bmod b = (x\bmod b)\bmod a$$$ translates to $$$x\bmod a = (x\bmod b)\bmod a$$$ and thus $$$qb+r \equiv r \pmod a$$$ implying $$$a$$$ divides $$$qb$$$. This gives us $$$\frac{a}{\gcd(a,b)}$$$ divides $$$q=\left\lfloor\frac{x}{b}\right\rfloor$$$. So given $$$l,r,a,b$$$ we're looking for number of $$$x$$$ such that $$$\frac{a}{\gcd(a,b)}$$$ divides $$$\left\lfloor\frac{x}{b}\right\rfloor$$$ which is easy to count solving an inequality or two.
Yes, that is exactly how I solved the problem. I didn't realise there is an easier solution.
According to A, everyone reached the finish line simultaneously.
Thanks for debugging my A.
Destruction level 100%
OK well, why the heck do people write this kind of obfuscated code? only to evade hacking? https://mirror.codeforces.com/contest/1342/submission/78201792
This seems to be a consistent obfuscator, his solutions look like this for three contests in a row. MikeMirzayanov awoo
what type of code is this ? i mean it doesn't look like normal c++ codes in english, and how did it got AC?
Why would greedy solution not work for problem D?
It works. Maintain a set that stores indexes of test cases ordered by their current size and iterate over the range $$$[1,k]$$$ in descending order (from $$$k$$$ to $$$1$$$).
In $$$i'th$$$ step, take the index of the test case with the smallest size from the set.
If it's size is less than $$$C_i$$$ then fill it with the current value $$$i$$$ until its size becomes $$$C_i$$$ or all the array with size $$$i$$$ become used.
Otherwise, create a new test case and fill it with current value $$$i$$$ until it's size becomes $$$C_i$$$ or all the array with size $$$i$$$ become used.
I find your solution very similar to mine except that i'm getting a WA on test 11. Can you check it why?
Your solution fails on following testcase
6 2
1 1 2 1 1 2
3 1
Your code prints 3 testcases whereas answer is
2
3 2 1 1
3 2 1 1
Thanks. It seems that I forgot to reinsert the popped element in set.
I was getting WA on test 11 too. Try your code on this input-
The correct output should be-
Why on earth did I solve A for any whole x, y (including negative) ?
I just realized that I solve it for the negative too after seeing your comment. There is a negative number in the example of the question when it introduced the operations (not the test case). That was so misleading.
https://mirror.codeforces.com/contest/1342/problem/A
meetoo
i am with you init bro.
Because it was problem A and most people just want to solve it ASAP without giving it much time.The people who faced problem due to the word simultaneously would not have faced the problem if they read the samples. But people generally want to solve it as quickly as possible without even reading it completely xD
why there are so many successful hacks on C
Maximums of hack submissions of problem C are Time Limit Exceeded(TLE). Because worst cases are not available in the pretest.
Am I the only person who didn't even notice the simultaneously word in the contest time but successfully pass the pretests?
You are not alone buddy XD
Maybe because of my poor English, I just read it but did not pay attention to it and passed the pretests.
Statement of problem D is difficult to understand + printing the actual answer was really annoying
I thought so many different useless way to print the answer and in the end I just used V[i%Test].push_back(M[i]) after sorting M. Here Test is the Min number of tests.
Yeah I did exactly the same thing (after the contest though lol) But that was annoying I got the min number of test cases like 30 min before the end of the contest
It's actually not hard to print the actual answer. If you just sort the array sizes and assign it to all tests turn by turn greedily, by exchange argument, it will satisfy the condition
Does anyone have any idea on Test #16 in D? I can't see why am I getting TLE in my presumably linear desicion: 78188697
Look at this case:
n = k = 200000, m[i] = i, c[i] = 1For every i = k...1 you will iterate from 0 to n-i.
Wow, thanks a lot.
Problem C https://mirror.codeforces.com/contest/1342/submission/78221117 My code fails on testcase 2..please give some test cases..on which my code fails..
Input:
1 4 7 1 6 8Output:
3Correct Output:
2https://mirror.codeforces.com/contest/1342/submission/78225763 can someone give me a testcase where my code fails?
Input:
1 2 3 1 7 10Output:
4Correct Output:
2Thanks a lot man
Doh! Just now saw that problem E specified "n rooks". I was trying to solve it for an arbitrary number of rooks, which is much, much harder :-(
How would you solve it if you can have ANY number of rooks? I also didnt read the 'n rooks' condition at start. To make it a bit simpler lets say the constraints arent a problem. How can we calculate the answer in the best possible time complexity?
Ok, here's about how far I got. Let's start by giving a number of rooks X; we'll come back later to which values are valid.
Let f(r, c) be the number of ways to fill an r×c grid (1 <= r, c <= n) with X rooks such that every column has at least one rook. I think this can be computed with inclusion-exclusion in O(n³). Next let g(r, c) be the number of ways to fill an r×c grid with X rooks such that every row and column has at least one rook. Again, I think inclusion-exclusion can compute this (from f) in O(n³).
There must be either a rook in every row or in every column (or both) to attack all empty squares. Let's consider the "every row" case, and assume exactly c columns are occupied. Then K=2X-n-c so we can solve for X, and take g(n, c) times a suitable binomial coefficient. Repeat for all values of c, and treat the all-columns case similarly.
That should give O(n⁴) time overall, assuming I haven't missed anything. I feel like there might be some clever way to reduce it to O(n³) but I'm not seeing it at the moment.
I missed n rooks part too. But I went back to reading the statement when I realized you can't even find out the number of ways of placing k rooks in an n x n board (without any constraints) in time better than $$$O(n^2)$$$.
I missed the statement 'each empty cell is under attack' and spent 30 minutes solving the task without it.
I'm trying to solve C by utilizing the fact that
x%a = (x%b)%aFor example if a is 4 and b is 6, then I'll find the count of numbers having remainder (0 with 4 & 0 with 6), (0 with 4 and 4 with 6), (1 with 4 and 1 with 6), (1 with 4 and 5 with 6)....(you get the idea).I find the count of numbers having some (p,q) remainders with (a,b) respectively by finding anyone such number, then every other number with same remainders will (I assume this) be situated at a distances of multiples of
LCM(a,b).I could get the sample tests to pass but failed the next test by an error of 1. Is the approach correct?
take x = 6 ,a = 4 ,b = 5 x%a = 2 x%b = 1 ==> 1%a = 1
so x%a != x%b%a
I'v made sure that a is less than b
https://mirror.codeforces.com/contest/1342/submission/78205413 can someone help me on why this code failed on large values (problem B)...I know i should have printed characters one by one rather than storing in string variable..but why can not a string variable contain 200 characters ??
it have to resize that t1 thats why it is giving tle
Thank you!!..I made a char array now instead of string with size more than maximum number of characters it should hold and it got accepted now.
Either resize t1 to necessary value or use push_back operation. Your t1 has size 0.
How to solve problem F?
Suppose we don't have any constraints on the order of elements, the resulting array just should not contain any duplicates. Let's build the result one element after another in ascending order, so each element we create is strictly greater than the previous. To create an element, just use some subset of elements and merge them into new element. This process can be efficiently modeled with the following dynamic programming: $$$dp_{cnt, mask}$$$ is the minimum value of the last element, if we merged all the elements from $$$mask$$$ into $$$cnt$$$ ascending numbers. To model transitions, we simply iterate on the mask of elements that will be merged into a new one, and check if its sum is greater than the last element we created. This runs in $$$O(n3^n)$$$.
Okay, how about maintaining the order? When we create an element by merging some elements of the original array, let's choose some position of an element we use in merging and state that all other elements are added to it. Then, to ensure that the result is ascending, the position of this element should be greater than the position of the element we chose while building the previous number. We can add the position we have chosen for the last element to the states of our dynamic programming, so it becomes $$$dp_{cnt, mask, pos}$$$ — the minimum value of the last element, if we merged the $$$mask$$$ of elements into $$$cnt$$$ numbers, and the last element originally had index $$$pos$$$ in the array.
Using some greedy optimizations (for example, we should not iterate on the position we are choosing to merge — it can be chosen greedily as the leftmost position after the position of previous element we are taking into consideration), we can make it $$$O(n^2 3^n)$$$, yet with a small constant factor.
I got $$$O(n 3^n)$$$ 78249435 because I conjectured that the minimum value of the last element can be implicit in $$$dp_{pos,mask} = $$$ (the minimum number of operations, the minimum value of the last element), What do you think ?
how many iterations is one second in codeforces?
1,2 or 3s are just to manage the constant factor. In general, if N is 10^6, then O(NlogN) solution will pass, given some caveat. There's a big hurdle of printing, which is the slowest part of the code. So if there's a lot of things to print like, maybe a matrix per test case, or answer to a lot of queries, then that can also affect the time.
In case of C, I think most of the TLs are because of that.
I agree with you but I would like to know how many iterations are approximately one second in codeforces because what runs on my PC in 5 or more seconds in codeforces gives me in 1 second what left me surprised. I always did the calculation with 1 second as 1e8 iterations and I think this is not the case.
I couldn't manage to solve C during the contest even though the recurring pattern was visible.
Here is my submission.
https://mirror.codeforces.com/contest/1342/submission/78232191
My logic was based around multiples of lcm+max(a,b). If someone can find something wrong in the solution please hack it. Thanks in advance!
I have logic for C plz indicate what is wrong with it. let a<b. now we can calculate the answer for range [1,b], now as the modulo function is periodic now we can easily manipulate this to get and for the given range.
I submit to problem C a solution in O (T*(Q + log( max(a , b) ) ) ) and it accepted. You can see it here: https://mirror.codeforces.com/contest/1342/submission/78217111 . I would like to be told if it is correct or not.
78195754 Can someone help me know why this soln exceeds the Time limit. Thanks.
Your LCM can be around 40000, so in worst case, you'll have this much iteration per query.
your complexity is $$$O(tq\operatorname{lcm}(a,b))$$$ which can be $$$O(100\times 500\times 40000)=O(2\times 10^9)$$$, which could easily exceed time limit.
So a prefix sum based solution should work right?
my prefix sum based solution passed.
I did many unsuccessful hacking attempt will it result in any negative points? Please guide me!
No
Thanks bro!
By mistake I downvoted.... sorry..
No.
Thanks bro!
I was trying to solve Prob.D using priority queues , but I'm getting TLE
https://mirror.codeforces.com/contest/1342/submission/78239810
I tried keeping time O(N) but maybe because I'm copying entire pq.top() in temp each time I'm getting TLE. But how do I avoid this ?
I simply tried using (pq.top()).push_back(A[i]) but it throws some error saying "passing ‘const value_type’".
can someone help me resolve this ?
You can check out my solution: Soln
The priority_queue does not allow you to change the values inside (because it might change the order), so it only returns a const reference with
.top()and you have to pop and then push the elements again.To fix it, you could e.g. use
vll*orshared_ptr<vll>inside your queue, which is cheap to copy.I have seen many solutions for problem D failing on 11th testcase .What was that can anyone tell me??
Maybe, It's like this
What was the answer for this isn't the answer is 3??
The answer is as follows
How does https://mirror.codeforces.com/contest/1342/submission/78244632 pass but https://mirror.codeforces.com/contest/1342/submission/78244302 fails? There is only one line change, and that line never gets executed. The 'cout << "???"' line never gets executed, since the test passes.
https://mirror.codeforces.com/contest/1342/submission/78250930 whats wrong in this solution for C
We need to find such numbers x from the range such that a divides x and b divides x..for that condition you took m=a*b but in fact lcm(a,b) would be minimum number which is divisible by a and b. So, m should be lcm(a,b) and not a*b.
no difference in taking lcm or a*b. they will both cycle https://mirror.codeforces.com/contest/1342/submission/78247102
Can someone explain why greedy works for problem D? I have a hard time wrapping my head around it.
Is it still going to be rated?
A lot of users were affected by the incorrect English in problem A
тогда rated для РУССКИХ!
Yeah i think they should not have mentioned the word "simultaneously". I too was confused. But seeing the number of submissions in first few minutes i think it was clear that there was no need of overthinking.
"But seeing the number of submissions in first few minutes i think it was clear that there was no need of overthinking."
I disagree with this. Quite frankly, I would have to overthink to interpret it the way the problemsetter did. I'll continue to stand by my claims of the author's interpretation being incorrect given that none of my points have been addressed.
Maybe this was a result of a lack of testers(nobody's been mentioned on this post)?
awoo, for future edu rounds, could you at least get more testers(or even people to read over the problem statements)?
IMO, if we make this round unrated, it'll be unfair for people performed well.
Problem A itself is mainly correct, with a minor(maybe?) mistake
The word "simultaneously" is not specially marked with bold,that means we don't have to pay much attention to it,although it's a bit misleading.
However, since the sample explanation is added soon after the contest started, it would be clear what "simultaneously" really means.
Hope there'll be less confusing statement like this in the future
Can someone explain the first test case of Div2E?
What are the 6 arrangements? Isn't this a valid arrangement?
xare the rooks,.is an empty cell.k = 2, it s invalid
ok got it.
I'm new to educational rounds! My solution to B problem was accepted during the contest but now its gone red and i wasn't rewarded for that Question and now its again green. Can anyone explain why so
your solution was incorrect, someone found test where it fails :(
If you made a failed submission for a problem,then the problem will become red during systest.
But don't worry, once your solution passed the systest, it will become green again.
Is Problem F the real-life application of Problem D?
78261468 can someone please provide a test case where this code fails
You can see the test cases now.
when will ratings update??....i am eager to see my new rating
Ratings will be updated soon
me too. Waiting for rating changes
You are python but you solve problem in c++ :p
The educationals have never been friendly to me :-(
78242194 78234298 Wubba-Lubba-Dub-Dub MOAE gj genius
can anyone please help me what's wrong in my code for C,I checked for numbers of type k*lcm(a,b)+max(a,b) which are in range. https://mirror.codeforces.com/contest/1342/submission/78265046
Can anyone understands me the div2D. Mainly i don't understand the test 2 first line output . Why that is 2.plz anyone explain. Sorry for poor english.
2 means minimum number of test cases you must have,to satisfy the given condition. And next there will be two line describing those test cases.
In case you don't understand the question: You can assume the problems like this,
Given N items with weight [1,K]
Given C1,C2,..,Ck which means the item with weight >= K in 1 packet must be at most Ck
The task is to separate the items so that the rules no.2 in fulfilled with the number of packets as minimum as possible
Test case 2:
6 10
5 8 1 10 8 7
6 6 4 4 3 2 2 2 1 1
N=6 K=10
Items = {1,5,8,8,7,10}
C = {6,6,4,4,3,2,2,2,1,1}
Answer:
You can separate the items into {10,8,1} and {8,5,7} or {10,7,5,1} and {8,8} or even {10,8,5,1} and {8,7}.
You can check my solution : https://mirror.codeforces.com/contest/1342/submission/78196440 (it's kind a mess tho)
In overall, my greedy solution goes with:
-Put the highest weight as the priority
-While it is available to put them in the packet 1, put 'em. else go to packet 2 and so on.
EDIT:
For every weight, while it is available to put them in the packet 1, put 'em. else go to packet 2 and so on.
System sent me a letter,it said that my code is similar to another person, so I write this comment. I solved 1342D quickly, and then, I had had been thinking about how to solve problem E, but my math ability is not very good, so I can't solve it. train2004 is my friend, all right. After contest, we talked a lot. His opinion is same to me, but I didn't see his code. I haven't thought about the case now. Through this experience, I konw that I should add some personal codes to try to avoid these cases. Thanks for reminding me, I'll notice these by now! Thanks!
Nice problems! Everytime I can learn a lot from educational round! Thinks a lot to codeforces!
I found out that I would be more likely to drop rating in edu-rounds.
Where is the editorial?
I have done problem D using greedy approach and I think time complexity is (n+k)log(n+k), but still I am getting TLE on test 16 78266716???
I seen all have almost same approach for Problem C. Can anyone tell me how we reached to that approach ? I mean what topic knowledge is required to think for that approach?
just print x% a % b and x % b % a and same or not, for the given example a=4,b=6 and choose like l=1, r=100 you can see the pattern and you can conclude you need the lcm, then it's basic stuff from here.
After this contest,system sent me a message:"Your solution 78191609 for the problem 1342D significantly coincides with solutions 78180150".However,I wrote my code by myself,and our code are different.Even if some part looks same,but that is a very common way for solving greedy+priority_queue problems.What can I do? Sorry for poor english.
Ask awoo or MikeMirzayanov for help
Sorry but I have to say... you're so "lucky"
awoo Could you please check this?Thanks.
No offense but code looks very similar.
Well,if you think this problem like this"greedy is ok.if I can add this m[i] into the smallest set,then do it;otherwise,make a new set",then write code.It's easy to look like others who have the same idea.(And we are classmates,so we have similar code style...)
But after all,our code really looks very similar.
So I think I should change my code style to avoid this situation next time. Sorry for my poor english.
Why all task were on one topic?
I don't know how to solve problem E. Could you help me?
Why not to post editorials just after the contest ends (learn from atcoder, codechef ) ,if problems and solutions are already prepared ,then why let others wait for so long ... I am checking after every hour from yesterday for editorials but they are still not posted...
This seems to be limited to Educational rounds and Div. 3s, (most of) the other problem writers seem to have it ready straight away and it's pretty disappointing when it isnt ready hours afterwards.
why the editorial is still not uploaded ? (i need hints for problem D)
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Hello, Orange!
Congrats ANZ
Can anyone help with TL on problem F?) https://mirror.codeforces.com/contest/1342/submission/78328093
Changed my DP to forward DP and TL was gone.
Doesn't it mean that TL is too tight?
I've solved it