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 | Heltion | 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 | lollihunter | 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://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://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://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://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://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://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://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://codeforces.com/contest/1342/submission/78163668)
(https://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://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://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://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