Hello Codeforces!
On Sep/19/2019 17:35 (Moscow time) Educational Codeforces Round 73 (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.
Good luck to all the participants!
Our friends at Harbour.Space also have a message for you:
Hello Codeforces,
We want to know what you think about Harbour.Space’s involvement in the Codeforces community, and how you believe we can improve.
So we created this short, 5 question survey to hear your thoughts about how we can provide you with more stuff that you’re interested in, so that we can improve your experience on Codeforces.
We really value your feedback, so it would mean a lot if you could take a minute and fill out the survey. Thanks in advance!
Congratulations to the winners:
Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|
1 | 244mhq | 7 | 192 |
2 | jiangly | 6 | 152 |
3 | betrue12 | 6 | 187 |
4 | I_love_Tanya_Romanova | 6 | 196 |
5 | pekempey | 6 | 198 |
Congratulations to the best hackers:
Rank | Competitor | Hack Count |
---|---|---|
1 | achi_basadzishvili | 129:-46 |
2 | apoorv024 | 87:-4 |
3 | Abdelrahman_Elhawary | 73:-31 |
4 | phyzzmat | 52:-7 |
5 | Sherrrkhann | 15:-1 |
And finally people who were the first to solve each problem:
Problem | Competitor | Penalty |
---|---|---|
A | talant | 0:01 |
B | talant | 0:02 |
C | YahiaAglan74 | 0:04 |
D | sys. | 0:08 |
E | 244mhq | 0:31 |
F | Benq | 0:35 |
G | Benq | 1:02 |
UPD: Post about the issue
UPD2: Editorial is out
Are the educational rounds a bit on the tougher side ?
Hahaha you are so funny.
awoo your Educational Contest are great <3 !!
You must be new here...
awoo gives us so many good rounds, we are very grateful <333333
Great way to farm karma eh?
I agree with you :)
Finally a contest with a 12 hour hacking period Hope to turn purple this contest
I hope all of you who is >= master can register for the round unofficially. Shouldn't take part in with new account. Not nice! Thanks!
You are absolutely right!
is div2 harder to raise rating for CM than div1 or div1+2 because of new accounts?
thanks codeforces for preparing several contests with low time interval. hope to have a great contest !
or is this just fantasy?
Caught in a landslide, no escape from reality
Thanks for the contest awoo
I don't want to become a specialist again.
same to you...
All the best to you!
Good luck everyone!!!! I wish everyone to rise!!!
I hope the pretest is strong enough because it's the first time I have solved 4 problems in a live contest. Thanks God!
but round is unrated now :(
who said so?
did they announce anything about that?
see the anouncement under problems
It is rated. My rating has changed.
i think unrated for who solved B wrong
you should've used quotations ( 'X' , '.' ) in problem E, It would be simpler to read
So many unbalanced rounds these days!
How to solve E?
Hint: If there exists segment of length x, where b<=x<a. B can always win.
So for a, we need to to prioritize decreasing length by a+b-1 always?
Not really. You can find a countertest for that. You can check the comments below, there is a spoiler to E.
ok got it!
Yes, the problem G was correct...
how to solve D with DP? i keep thinking about back tracking...
it's easy to see that each element should increase at most 2 times
I thought same but then I made this case.
$$$a=3 \enspace 3 \enspace 4 \enspace 4$$$
$$$b=5 \enspace 1 \enspace 5 \enspace 7$$$
This case made me feel there might not be limitation in height increase.
I guess the answer is 6 $$$(a = 3 \enspace 4 \enspace 5 \enspace 4)$$$, and none of them increase more than twice.
You never add more than 3 to a single position
2 or 3? got AC with the same insight but for 2.
2 is correct aparently. I used 3 just to be sure. Some submissions even use a few more
Here is the argument for 2. Suppose you've done everything you want with all but the i-th board. Now note that there are at most 2 boards next to the i-th board, so you never need to increase the height of the i-th board more than twice in order to make the heights unique.
but u need to use FAST IO, it was my mistake
Really confused in E...
How to solve E? Don't even know how to do it in $$$O(n^2)$$$.
Case $$$1$$$: When there's a segment with length $$$x$$$ where $$$b\leq x< a$$$, Bob always wins.
Case $$$2$$$: When there's at least two segments with length at least $$$2b$$$, Bob can always divide one fitting into case $$$1$$$ and thus win.
Case $$$3$$$: When there's no segment with length at least $$$2b$$$, the winner depends on the parity of number of segment with length $$$\geq a$$$.
Case $$$4$$$: When there's exactly one segment with length at least $$$2b$$$, enumerate over all possible moves for Alice with this segment, then it reduces to case $$$3$$$.
simply wow
How you came up with this solution?
B wins if in his move there is some segment with length at least 2b, because he can make a segment of length b, therefore he will have at least 1 more possible move than player A.
How did you come up with intuition of segment with length atleast 2b
Check wheter there exists segment of length x, where b<=x<a. If yes then B can always win. Otherwise let cnt be # of segments with length >=2*b and now we only take care of segments >=a. If( cnt>=2) Then B always win because no matter what A does he can split segment of length x, where b<=x<a. If(cnt==0) then all segments have length x, where a<=x<2*b, so only parity determines the winnner. If(cnt==1) A have to move in this segment first, so we can consider all his moves on this segment, and if any of them provides him a win, he can win, otherwise he cant.
My observation: in B move if there is some segment of size $$$>=2*b$$$ he can win.
At first consider only blocks with no less than b letters. If there is a block with at least b but less than a letters then second player wins. If it is a turn of a second player and there is a block with at least 2 * b letters then second player can create a block of length b and win. So, check at first if there is a block of length between b and a — 1, if there is, then second player wins. Then count amount of blocks of length at least 2 * b. If it is 0, then in every other block each player can make only one turn, so total number of turns is amount of blocks. If it is at least two, then second player wins. If it is one, bruteforce the move of the first player, and check if he can win(after his move all the blocks should be the length less than 2 * b so number of moves will be the number of blocks of length at least b).
How to solve E?
I thought I'd compute for every X from 1 to size(s) winAlice[X] and winBob[X].
winAlice[X] will be true <==> Alice can win a segment of size X if played optimally.
Then I'll be left with the segments of the give string(contiguous '.') and for each one(say it's length is X) I'll have 4 possible cases, depending the pair (winAlice[X], winBob[X]).
Anyone else thought like this?
Same thoughts, but can't figure out how to obtain the answer from those 4 values.
why my submission problem C is wrong? I tried greedy method.. submission
answer is 2.
1 team: c c m
2 team: c m m
I found counter example
answer is 10
The answer was simple min(a,b,(a+b+c)/3))
What is the intution behind this...? I mean to ask what guarantees that by doing this ; you always end up with that many teams satisfying all the constraints in the given question ( I am concerned obviouslsy only with the (a+b+c)/3 part ; i understand why other two terms 'a' and 'b' are in the min expression )...
Can you please present a formal proof for the claim... thanks...!
(a+b+c)/3 is a constraint because each team must consist of three members.
ok...
Doubt : How do you know that this ALSO returns you the number of teams with 2 coders and one mathematician ( Or 2 mathematicians and 1 coder )
Because a+b+c is the total number of people, including the coders and mathematicians.
Who knows problem B test 2??
never mind... sorry
how can this be a testcase of B?
i’m sorry
:) Btw i got wa on case 2 for this case :(
Input: 100 Apparently, the checker was buggy, so many wrong solutions passed during the contest and now they re-judged the solutions.
I am stupid enough because my brain cannot get the ways to solve the problem which everyone except me have been solved. :(
dude...
I feel the same :(
Can anyone tell where my test case in Perfect team go wrong here is my short code, It will be a great help!
Test case 1 1 0 No output in your code
I think this will be while(ans >= 0)
Can anyone tell test 2 for C? Really desperate to know
answer: 10
try 10 10 0
How to solve D ? I tried to solve it with dp but I couldn’t.
You can find an optimal solution where no border is increased more than $$$2$$$ units, so it can be solved by $$$dp$$$ using this observation.
Proof: If adjusting border $$$i$$$ to be finally of length $$$a_i$$$ will make it equal to some adjacent border, and adjusting it to be of length $$$a_i+1$$$ will make it equal to the other adjacent border, so for sure adjusting it to be $$$a_i+2$$$ will make it different from both adjacent borders, and there is no point in increasing it more than this.
Each elements in $$$a$$$ should increase at most $$$2$$$.
Let $$$dp(i, j), j \in [0;2]$$$ is the minimal cost to make the fence from $$$1$$$ to $$$i$$$ (inclusive) great.
Remember keep tracking the last element in previous state.
Let $$$prev[j], j \in [0;2]$$$ is the last element of the great fence after we increase $$$a_i$$$ with $$$j$$$ units.
Base case:
- $$$dp(1, 0) = 0$$$
- $$$dp(1, 1) = b[1]$$$
- $$$dp(1,2) = 2*b[1]$$$
and
- $$$prev[0] = a_1$$$
- $$$prev[1] = a_1 + 1$$$
- $$$prev[2] = a_1 + 2$$$
Recurrence:
Check my submission for more detail.
Can you check the checker of B? This submission seems incorrect (https://codeforces.me/contest/1221/submission/60861923)
deleted
Is it possible to solve E using grundy numbers ? If yes How ?
No, because game isn't impartial.
Is G $$$answer = 2^n - 2^c - 2*s+ 2$$$ ? ($$$c = # of components$$$ and $$$s = # of independent sets$$$).
No, you also need to take into account the number of bipartitions.
Let $$$f(C)$$$ be the number of arrangements such that none of the numbers in set $$$C$$$ appears. Then our answer is $$$2^n - f({0}) - f({1}) - f({2}) + f({0,1}) + f({0,2}) + f({1,2}) - f({0,1,2})$$$
$$$f({0})$$$ and $$$f({2})$$$ are the number of independent sets.
$$$f({1})$$$ is $$$2^{(\text{number of components})}$$$
$$$f({0,2})$$$ is the number of bipartitions.
$$$f({0,1})$$$ and $$$f({1,2})$$$ is $$$2^{ \text{number of isolated vertices}}$$$
finally $$$f({0,1,2})$$$ is $$$2^n$$$ if the graph has no edges and $$$0$$$ otherwise.
$$$f(0,1,2)$$$ should be $$$2^n$$$ in the no-edge case.
Oh yeah, thanks.
Is it possible for me to become unrated, as I was affected by G's wrong sample outputs. The announcement was too late and by that point I have already been too focused on debugging. If the announcement was done earlier I would have been able to complete the task.
Problem A is interesting.
In addition to using greedy algorithms (*), priority_queue data structures (**) can also be used. Solution (*): 60890951 Solution (**): 60890114
Actually, because it's guaranteed that all elements of the multiset are powers of two, you can solve it simply and directly just like this.
Can you give a proof of this?
I can't give strict proof, but imagine the worst situation, after some mergence there is 1 + 2 + 4 + ... + 1024 = 2047. You can get 2048 if any number appear once more, even if it's 1. Or you can get 2048 when get a number once more but lose those smaller numbers. All in all, it seems the answer just depend on the sum.
It can be proven inductively on 2^i.
Here's my thinking to problem $$$G$$$:
Clearly we should use inclusion-exclusion principle, then we need to count the number configurations without some certain sets of edges.
without $$$0$$$/ without $$$2$$$: Use meet-in-the-middle, together with SOS DP. The complexity should be $$$O(2^{n/2}m)$$$. Heavy code.
without $$$1$$$: answer is $$$2^c$$$, where $$$c$$$ is the number of connected components
without $$$0$$$ and $$$2$$$: the answer is $$$2^c$$$ if the graph is bipartite, $$$0$$$ if not, where $$$c$$$ is the number of connected components
without $$$0$$$ and $$$1$$$/ $$$1$$$ and $$$2$$$: answer is $$$2^s$$$, where $$$s$$$ is the number of singletons
without $$$0$$$ and $$$1$$$ and $$$2$$$: answer is $$$2^n$$$ if there's no edges, otherwise $$$0$$$.
However, this requires too much code... Is it intended? Or I think this problem can be solved in $$$O(fib(n))$$$ using some recursive searching approach after inclusion-exclusion?
The only long code is SOS DP though, so I don't really see much of a problem.
I think $$$s$$$ should be $$$c$$$ right?
I think not, in such case if the conneted component isn't a singleton, then there's only one possible way to color it, otherwise $$$2$$$.
You can flip the $0$s with the $1$s and it is still valid.
That's the case when there's no edge $$$1$$$. I'm talking about the case when there's no edge $$$0$$$ and $$$1$$$/$$$1$$$ and $$$2$$$.
Consider the graph $$$K_2$$$, there are two ways to paint the vertices so that there is no $$$0$$$ or $$$2$$$. One way is $$$(0,1)$$$ and the other is $$$(1,0)$$$
Oh, you mean that case. Corrected. Thanks.
How do you come up with this? Where does your idea come from? Could you please show your thinking flow? I just don't know where I should start with even though given enough time. Thanks in advance!
The condition says 'at least one edge with $$$0$$$, at least one edge with $$$1$$$ and at least one edge with $$$2$$$', which is a union of three sets, implying that one should apply inclusion-exclusion principle.
six six six
My B got accepted, and it doesn't even pass the sample. 60857895
I would have solved 6 problems if I had just submitted G, I had a working solution which didn't match the output on the 3rd testcase, and now I'm just pissed off. You should have made an announcement that the 3rd sample had a mistake and to refresh the page.
Is there anyone who also used INT_MAX instead of 1e18 in D and got wrong :(
Please explain to me logic for problem E? Thanks so much <3
Is there anything wrong with the checker of B? Many wrong solutions seem to pass the samples.
Problem B should be removed from problemset.
Checker in problem B is uncorrect. Solution passes tests even if answer wasn't true.
got ac : https://codeforces.me/contest/1221/submission/60869458
got wa on 2 : https://codeforces.me/contest/1221/submission/60891207
wtf
The checker was wrong apparently. They rejudged all the Bs i think. It shows WA for both your submissions now.
wait for some time, that one will get WA too
Well, they should have announced while changing the test cases and rejudged our submissions during the contests while we still had time.
This is somewhat an unexpected behavior from Codeforces :(
Does anyone notice that there are $$$>50$$$ participants who got AC in the last minute of the contest? It's amazing!!! Deadline is the strongest productivity.
Wonderful =))
the checker of problem B is wrong ,i got hack by the pretest,please unrated.
Got WA on 2nd pretest after the contest, problem B should be removed from the problem set or this contest should be made unrated.
please remove problem B and make it rated !
I think so. B is unpleasant
Me too. :(
Then it will be unfair for people who actually solved it.
second that
Unlikely to happen, what about participants who spent a significant amount of time on B?
I only see two realistic possibilities :
Also generally a problem is only removed if the answer is completely wrong. In this case it appears the checker has been fixed, so it'll probably remain in the contest/problemset. Anyway if a problem is removed, it nearly always entails the round becoming unrated.
is it rated?
Getting wrong answer on pretest after the contest ends, nice checker
you must do this contest unrate
Wrong answer on pretest 1 after the contest? WTF!
My solution was accepted during the contest. But astonishingly after, I saw my submission was not accepted and was also not hacked. That means the author's code was not correct. Either this round should be unrated for me or this problem should be removed from problem set.
It seems there was something wrong with the checker for problem B...
Checker for problem B was wrong so please make it unrated!
Problem B should be removed from the problemset.
Problem B is fine. Problem is with checker.
Then how I can understand if the problem with checker if already my solution passed during contest time and now I saw WA on test 1. How funny.
So the contest should be unrated. Problem should not be removed.
hack checker is faster than the pretest checker to tell me my solution in problem B wrong.
please make it unrated !
There is a bug, my second question was wrong on 2nd pretest, yet that was accepted, and they say wrong answer..... Now my rating is being highly deducted.... Huge bug This contest must be unrated....(atleast for me)
awoo or anyone else, can please let me know what's the problem with B??
It was accepted earlier during the contest, but now it is showing WA. I think the system testing has not been done yet, and the solution has not even been hacked.
Link to the Solution
My problem B was accepted in contest time and now it shows wrong answer on pretest 1. it's unfair for us(who face same issue)!
Wrong answer on pretest 2 after contest ? WTF!!
Problem B basically had really weak pretests. I do not find it very convincing to make the round unrated
actually, it has no pretests during contest
Educational Codeforces Round 73 [Rated for Div. 2] problem no.2 my solution got accepted initially but it was not able to pass even the testcase given in the question. That created confusion, If the at that time the contest would have said that it is wrong on testcase 1. I might have corrected it. This is wrong codeforces.
There were some problems with checker in problem B during contest. It showed that your solution is right, even if it is not. In my opinion it is not fair and round should be unrated, because during contest i thought that my B was right
So every round where there are hacks after contest should be unrated? These are preliminary results for a reason.
There was problem with checker during contest. Why do you say about hacks? If i knew that my B was incorrect, i would definitely submit it during contest and get AC
Nice Checker on B... Best one I've seen at Codeforces. Make it unrated. tlqkf
No point to make the contest unrated.
Assume it to be hacked instead of a WA.
This is Educational Round instead of a common round so there is no something can be called pretest. I have never seen so many people be hacked in a Educational Round.
Go check last education round's B
:eyes: I'm sorry for this wrong.
And even if there can be pretests in Edu Rounds, it's not even weak, it just literally can't be called a test.
Imagine you print out something you don't know what that is, and you get "Pretest Passed".
The checker of B is literally a joke. And the solution to this is just rejudging in several minutes AFTER the contest, I'm literally surprised.
I failed B after rejudging. Still think it should be rated.
I think than round should be unrated because there are problems with checker in problem B. And it influenced on results.
yes i agree with you
I understand people whose results have been impacted by the rejudge of B, but I suggest that you look at this from a different angle:
700-odd people have WA instead of AC after the contest.
There have been many times when a single problem had north of 1000 hacks and the round remained rated. (e.g. some problem about inversion had 1200 AC's during the round, which fell to under 200 afterwards.)
Therefore, the solution to make the round unrated for everyone would be a bit overkill (IMO), because it seems that the standings table will have changed less after the hacking phase than in some rated contests (pretests for all problems, except B, are very strong).
I know that I'm going to be downvoted to oblivion, but it's just an alternative point of view to consider.
B was trivial, I have -delta but still think it should be rated
I assume that the checker was maybe just checking whether the output is N*N? lol
We are really sorry for the issue with problem B checker. The contest will be definitely unrated for the participants affected by it.
Only for them?
Not for all?
Should be unrated for everyone! This does not make sense at all
There are people who solved it with correct method. Think about others. The decision taken by Codeforces is the best, I think. : )
Please unrated for all participants who have at least one submisson on problem B.
I don't think there was a submission on B which don't get accepted unless there is presentation error. :3
For all or not? ;D
I voted by mistake Sorry ;(
In Problem B: My solution was wrong and it give wrong answer for pretests also,still it passed the all Pretest. After the Contest Over I realized that my solution was wrong. Why This happened???
https://www.imageupload.net/image/d7ft
Read the comment section before asking please
Just putting forth a point. All participants affected by the checker of B are all not a specific group of people, either indirectly or directly. Kindly consider this point for the fate of outcome of this contest.
what do you mean they are not a specific group of people? You just specified who they are?
Rizu Bond
Probably riz_1_ has a point, but is getting ignored as the officials do not want to make this unrated, and hence the downvotes for the comment by other users are for making this comment to be ignored. BledDest should address the this point also.
P.S. Don't downvote me please for putting across a general point
Finally, someone who understands. Probably I was misinterpreted the first time.
Wtf, is this contest a joke? Making it unrated for only those who got affected by it isn't the solution. I did not give the contest from my official handle ( DunnoY ) to waste 2 hrs.
I hope Codeforces could give the affected participants the right of choosing if he/she will be rated when the similar sitiation happens again.
I want it to be rated for me even though my rating is decreasing.
Div3 is coming :p
Why not! Totally fair!
Remember,you won't get extra points for being good.
What is the difference between having really weak pretest and having a bad checker (if corrected before the main tests). I think making unrated for participants affected by problem B isn't the right decision, but it at least try to find a fair solution. Reading the comments I see a lot of people asking for unrated contest for everyone. I know, you are upset if you lose points, but there is no reason to make it unrated for everyone. The contest was interesting with lot's of good problems. An upvote from me, really not understanding the downvotes. Problemsetters are human too, they make mistakes. They made a lot of work to make this contest, but they get lots of downvotes because of 1 mistake.
There was also a mistake in problem G, don't forget that.
Problem G has affected only 2 participants at the moment of clarification. Moreover, the round wasn't rated for them.
Problem B and G had problems. I agree with you about the Contest overall, the tasks are really good, but, for me, it is clearly an unrated round.
I hope, BledDest and his friends will understand their fault and make this contest unrated for EVERYONE, because imho either contest should be rated for everyone or in seldom times, like this, it should be unrated. It's weird that they are trying to find the third way :/
Yeah, it's not like the ranking doesn't change when you remove a few hundred people.
Why it should be unrated for people who have not been affected? Why do you want to discount their efforts? Please, explain.
in this way your rating doesn't show your skill(in my opinion), it is just useless number not more
How did you come up with a thought that rating won't show the true skill of a participant, if the round is unrated for a specific group of people? Can you elaborate on that?
maybe because "rating delta" changes when you remove some participants?
Well, yes, it does. But it's not that tremendous to make the rating system useless. You can notice, that the predicted rating delta of most of the participants has changed by about 10, not more. Everybod knows, that such error in rating is just nothing
if you don't care about rating, every round is unrated
You are interested in the fact that the round was rated for you.
In my comment I didn't tell anyone that I want the round to stay rated. I was just trying to understand, what he said, so, your pretension doesn't make any sense.
Wait, what?? You solved a problem correctly and got the right verict, how doesn't this show your actual skill? You took more than 1 hour to solve D, because of which you are getting a rating change of -30. How would that have changed if the checker for B was right. I mean you anyways had done it right.
"How would that have changed if the checker for B was right" i will open the secret, my little Indian bunny, delta depends on the performance of all contestants, and my delta had changed when they removed some contestants.
Your point is right, but you took the effort to open someone's profile to see if he is Indian to make you sound more cooler? Why?
dude, that's a joke, i'm not trying to offend anyone
Ok. I know that russians are great mathematicians. But are you saying that before every contest you calculate your probability of winning with every other contestant, your expected rank and then decide your strategy and if a few people were removed, your strategy would have changed. Besides, the only change which happened in the verdict was from AC to WA. So your rank would have only been worse had those participants not been removed.
Btw I just read that cats eat bunnies. So I am sorry if I offended you.
But what about about the efforts of User who solved ABCD, and B is gone.
As long as sum of all rating changes is negative (recalculate rating over the set of people that passed, without taking any info into account from unrated users) it should be OK. Otherwise you get inflation and it devalues work.
UPD: actually I thought about it again based on below comments and my past experiences and I conclude it should be all unrated.
If you make contest unrated for affected users only, you discount their efforts. Such distribution does not show real skills, some of affected people could solve task correctly in short time after getting WA, so really they are stronger than people who overtook them because of wrong checker in B.
second that
Is hard to meassure if someone was "affected", because the ones that "got affected" could have scored better if there were no issues on problem B, and therefore affect to the contestants that "got not affected".
yes. that's what i want to say.
Ivan, let's be honest, you just don’t want to lose 30 rating points
Round should be unrated for everyone.
Please, read the rules: hacks don't give points on Educational Rounds.
Still unrating for everyone is a better choice. Everyone in the comment section is asking or this.
No. Some dozens are asking. More than 5 thousand participate in the contest.
Lol, what kind of metric is this. Technocup 2019 only 291 comments were made and there were 7500 participants. Should that have been rated?
https://codeforces.me/blog/entry/69868?#comment-543996
If you start taking people's opinion for deciding if a round is to be kept unrated, every round will become unrated.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Unrated.
starboy_jb unrated for everyone?
No, I am just requesting for that.
I am an affected user.
XD
Weaker pretests and many hacks doesn't justify make a round unrated.
Why is everyone forgetting about issues with problem G? ... I spent some time thinking about the Meet in the Middle and about the code ...
Because too little people were affected. And for those affected, the solutions were rejudged and problem G was the last.
Big lol !! You shouldn't have thought about meet in middle , in the middle of getting your C accepted xD . You want this round to be unrated becuase you get a negative delta that's what most believe we are all humans . Don't throw up things like , " I was affected by the issues with problem G because I spent time thinking about it".
hahaha, like if I care about my rating. Have u seen my rating history?
ok lord leonardo_paes you should now be going ahead with your meet in the middle solution for G the issues of which affected you instead of trying to reason if this round should be rated or not because hahaha like if you care about your rating .
Nice position at Round 585, btw
heard about bad days , kid ?
Yes, I am in one today :/ Sorry for the comment
I know mate. I have been in more bad days than the good ones on this platform .
There is literally nothing can be called pretests.
MikeMirzayanov What happen for people failed in problem B and their rating will be positive also?
unrated i believe :(
For the people who are affected by checker,it will be unrated for them. For the rest of people, it's rated. It looks fair to me!! Problems were nice and for one mistake, it seems unfair to problem setters and unaffected users to make round unrated.
:)
Can some one tell the proof that putting 'B' and 'W' alternatively is best answer in Problem B ?
Let's consider that cell (0;0) is white.
Is is true that cell with coordinates (i; j) is white if and only if ((i+j)%2 == 0).
From cell (i; j) you can reach the following points:(i+1; j+2),(i-1; j+2),(i+1; j-2),(i-1; j-2),(i+2; j+1),(i-2; j+1),(i+2; j-1),(i-2; j-1). Here you can observe that if you get from (i;j) to (new_i; new_j) the parity of (new_i+new_j) is always switching, so the color will switch as well.
On a checkered chessboard, a knight only attacks squares of the opposite color of the square it is currently on. Formally, the parity of the square, $$$(i + j) \mod 2$$$, always differs between a knight and the squares it attacks. Thus placing white knights on one parity and black knights on the other will always ensure that each knight is attacking as many opposing knights as they could, as there's no chance of "wasting" attacks on own knights.
There is no reason i could think that round should be unrated for all user.
Mistake was unfortunate but MikeMirzayanov and awoo found a good solution to handle this situation. Thanx
Keep it rated, at least for people not affected by B.
I can see/sense that many solutions for problem D are being hacked using the extreme inputs like queries count = 3*10^5, n = 1, and a = b = 1000000000. The solutions are getting TLE'd just because they haven't used fast I/O. I don't think this is the expectation of any Educational round problem to focus on using efficient I/O and get hacked if you don't.
EDIT : I myself have now hacked around 16 solutions using the same test mentioned above, purely on the basis of inefficient I/O
EDIT-2 : Have hacked 85 solutions now. Can go on and on but too tired to continue. Let the downvotes come while I sleep like a baby !
It should be a given that you should always use fast IO
Then such a test case should be a part of the pre-tests and not be used as a hack.
This is a sad day for me but yea I definitely learned that lesson
The same thing happens to me. Feel so sad.
you are so funny, bro
Why only 256mb in F? Are sparse segment-tree suppose to MLE?
ML for F is too strict..
The first time solving problem D. 60907231
idol gio?i qua' a. =))
:v
When will the editorial be published?
Why do we need to print inf as coordinates for F when the score is 0 ?
Hello admin, I have just thought of a test that some participants will get wrong, but they are still accepted in lesson A, how to fix the test
PikMike please reply me !
can you give me your test case??
1 3 1000 1000 48
The answer is NO, My friend issued YES but he is still accepted in problem A
"Every integer in this multiset is a power of two." Read the statement carefully.
oh, sorry
you can public AC solutions link^.^
;)
This statement is written in the question:- "It is guaranteed that all elements of the multiset are powers of two." 1000 and 48 are not powers of 2
Sorry, I did not read carefully
Sorry, I did not read carefully
https://codeforces.me/contest/1221/submission/60867022 Can anyone mathematically explain why this is failing for C?
You can try 6 6 0, your answer is 3, the best answer is 4 2 1 2 1 2 1 is your statrgy, The great statrgy is 2 1 2 1 1 2 1 2
Consider the scene after your n has become 0... and lets dive straight into the test where your code fails...
Test : 18 13 0 Your intent : you are now wanting to subtract 2*buf from the greater number ( 18 ) and buf from the smaller number...
Now you wonder how many times this subtraction you should be doing... And you answer this as : as many times so that both v[0] and v[1] remain positive... and till when this holds...? You answer this as min ( v[1]/2 , v[0] )...
Mistake : You forgot that in due course of subtraction... somewhere in between... the bigger at the moment might turn up getting smaller...
i.e. at the moment ; 18 > 13 ( lets call them a and b ) a > b ( Currently )
But after some subtractions ; since a is reduced by a greater amount at each step ( 2*buf ) than b ( buf ) ; so inequality might transform from a > b to a < b...
so you should pause at that moment ; and swap a and b again ; and then only continue the remaining steps...
So your deductions look like : 18 13 -> 16 12 -> 14 11 -> 12 10 -> 10 9 -> 8 8 -> 6 7 ( and now pause and swap )
7 6 -> ...
So you should start thinking about the third scene also while calculating buf... and it should be min ( {a/2 , b , a — b} ) ;
my code : https://codeforces.me/contest/1221/submission/60916409
Why did I join this game, the rate has not changed? my submission is "*name", what does * stand for?
'*' stands for U participated virtually. Maybe U registered after the start time of the game.
If you initially got AC on problem B, but the verdict was changed to WA later (which I think was the case), then it's likely that you were affected by a bug in the checker, and so this contest is made unrated for you.
You can read more about it here.
How to solve Problem F, I did not see a comment about it, Thanks!
Editorials?
Please publish the editorials. Thank You.
[Deleted]
This contest is gone from my profile. There is no such contest and submissions for any problem of this contest in my profile. How to know the verdict of my solution for this round?
If you initially got AC on problem B, but the verdict was changed to WA later (which I think was the case), then it's likely that you were affected by a bug in the checker, and so this contest is made unrated for you, which means that it's hidden from your profile.
You can see the problems by clicking the checkbox "Show unofficial" at the top of the problems page in your profile.
You can read more about the issue here.
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
the first time to get mentioned in round, very awesome ^_^
(After understanding the statement)Me:"Each board can be increased just once."
(After coding)"Oh, it's wrong!I can't pass the example.$$$1 * 2 = 2$$$ so maybe twice is right."
(got accepted)"First Blood!!!But......why??????"
The bravery leads you to obtain a first blood!
As for me... "no no no no, it can't be. let me just solve the problem F and have a good sleep."