Обратите внимание на необычное время старта раунда.
UPD: Мы не можем хорошо оценить сложность некоторых задач, поэтому рекомендуем вам прочитать все задачи и подумать над каждой из них.
<almost-copy-pasted-part>
Привет! В Dec/28/2019 20:05 (Moscow time) начнётся Codeforces Round 611 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</almost-copy-pasted-part>
UPD2: Разбор опубликован!
)
Three back to back contests today — AGC 041, Codechef December Lunchtime, CF Round 611. GLHF!
When I registered for this round my rating was less than 1600. But will this round be rated for me if my rating become 1600+ before starting the round (after updating rating based on Educational round 79)?
Haha but you're an LGM... XD
no(
Doubt that the scores will be updated before the next match.
No. It won't be rated for you.
??????THE BEST HAKER?????
Funny magic！
Huh, really friendly time for us:
For Chinese users.
Before yesterday's contest, I had a rate of 1599 and it was planned to have 0 rate change so that I could participate in today's div3 contest, and yes I am 1599 again :D
My plane now is to get +100 rate change, Can I achieve my goal again? :3 I hope sooooo
vovuh always have good contests so I hope it will be one of them. good luck everyone :D
)
Some experts are listed as official participant. Please fix it.
Checkout the magic option at your profile page. You can change your color from there (I am not an LGM :3). This feature gets activated around each new year. Maybe they are not experts, they just changed their color :3
I do know about that. That is not the case.
What does the post mean by "Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes." Does this mean 10 minutes is taken off your clock for a wrong submission?
yes (A wrong submission adds to your time penalty).
I took part in a competition yesterday that also had this penalty and nothing happened to my time when I submitted a wrong solution, what was happening there?
I checked your results in the last contest, your total time without counting the penalty for wrong submissions is 39 + 15 = 54. You had 3 wrong submissions -> 3 x 10 = 30. Therefore your total time penalty is 54 + 30 = 84 (This number is shown under penalty in the standings).
Oh i thought it meant you would have 10 less minutes to do the problems.
No! This mean that your penalty is increasing by 10.
0h5 — 2h5 AM I'm here :(( but i will try participate.
UPD: We cannot determine difficulty of some problems thus we recommend you to read all problems and think about each of them.
Hmm, something's fishy.
At last the fishy thing was Task-C. Weak pretests and some solutions don't make sense
Near one third of the solutions for c were hacked (including mine:( )
Today's leaderboard will be colorful :)
You're definitely misleading people with that photo...
The announcement for E was very late Costed me 2 wrong submissions Pls look into it
"For example, let the initial positions be x=[1,2,4,4]. The final ones then can be [1,3,3,4], [0,2,3,3], [2,2,5,5], [2,1,3,5] and so on. The number of occupied houses is the number of distinct positions among the final ones."
You could infer it from the statement.
Still the statement was pretty unclear. Look at statement now, its perfect
Nice F, thanks)
numberline forces
I couldn't understand problem F completely. Can someone clarify it more ?
Difficulty : A < B < C << D,E << F
I think E was a lot easier than D in Implementation. Though getting the idea was the main thing.
what is the 4th/7th/11th test case in problem E? or what can it be?
Yes I was also geting WA on tc 4 with my without DP approach I dont know what is wrong
try these cases:
ans: 1 5
ans: 3 9
Great Contest. Managed to solve 4 problems.
How to solve D within the time limit?
Greedy problem using a priority queue (min heap) and a flag checker.
you can keep minimum distances in the queue
For example, n = 2, m = 3, x1= 1, x2 = 5 Then initially, you need to push (0, 1) and (0, 5) // (dist, position) and set(1) = visited and set(5) = visited
If -pq,top.first != 0, then add this position to your answer array. and check whether you can insert position+1 and position-1 with your checker. If position+1 is possible, then push(-(dist+1), position+1)
until you gather m position
I did the same thing nearly but got wrong answer on test 3. Is it because of unordered map? It would be great if anyone can help me find my mistake!! my submission Thanks .
E was dp or greedy ?
dp i maintained 3 states, first calculate frequency array for input from 0 to n+1 and if it is greater than 4 make it 3 States are as follow: 1) idx : index of location or houses 2) x : number of friends previous location is asking to me 3) y : number of friends i will give to next location
Greedy af
Can we use bfs to solve problem D? i always get memory limit exceeded on test 12 :(
Yes. I managed to solve it using something like bfs. Submission : LINK
Yup, you can have a look at this — https://mirror.codeforces.com/contest/1283/submission/67841418
1283E - New Year Parties is similar to 1203E - Boxers .-.
I would say it is half-similar :) Btw I cannot understand how didn't I remembered this problem, lol.
Except for the fact that we couldn't go from 1 to 0 in the old problem
Thanks for the contest!
I had an hour after solving C. I looked D and thought set+pq naive. But I thought it's not the model solution, and gave up. 10 minutes left, I started to code naive, and I've done it after contest. Submit it, AC.
wtf
this happened with me in E , i solved very late and forgot to memoize the dp.Till then i memoize it time was over :(
$$$F$$$ was cool. Here's a fun fact: You can prove that number of trees in $$$n$$$ vertices is $$$n^{n-2}$$$ if you have a working algorithm for $$$F$$$!
Your algorithm is deterministic, so it generates exactly one output for each input. Also, as each output corresponds to a unique ordering of edge importance, each output will correspond to exactly one input. But number of different inputs with $$$n$$$ vertices $$$= n^{n-1}$$$ and number of different outputs $$$= nT(n)$$$ where $$$T(n)$$$ is number of undirected simple graphs in $$$n$$$ vertices which are trees. (We are multiplying by $$$n$$$ because same graph with different roots are considered distinct in the output.) Thus, as inputs and outputs have a bijection, $$$n^{n-1} = nT(n)$$$. Thus, $$$T(n) = n^{n-2}$$$!
This is kinda similar to other proofs of Caylee's formula like Prufer Codes and proof of Caylee's formula by double counting.
Can someone help me figure out what is going wrong in my submission for Problem E 67835042. Thanks in advance.
Try this:
output should be 1 3
HOW TO SOLVE E? PLS EXPLAIN IN BRIEF!
Max can be computed by sorting the array and greedily shifting elements as left as possible to maximise the houses occupied. My logic is going wrong on min (So I don't know)
There is also a possibility of you shifting to the right
Why should C problem this submission 67826496 should be ac? Something wrong with the judge program?
Looks like a good round is going to be unrated :(
WHAT????
Hacked it, thanks
Pretest data should have hacked this submission, the question is about judge program.
Yeah, I'm not 100% sure what the judge is doing. Here's the hack though https://mirror.codeforces.com/contest/1283/hacks/604551
It is not visible
How could one hack that if the judge was fucked up
The judge at least compares constants, I think?
https://mirror.codeforces.com/contest/1283/hacks/604551
What are the hacks for C ?
5
5 0 4 0 0 is what I used
I really liked this Div $$$3$$$ contest because
A great Div $$$3$$$ Contest to end the year !
mango_lassi I generally refer your solutions. How to solve $$$F$$$ ?
In C, can we also change the value which is not 0 ?
I also have the same doubt, eg 5 4 0 0 1 2 ans- 5 1 2 3 4 is also getting accepted
it is clearly stated that you have to fill unknown values(zeroes)..
then why the above soln. that I mentioned is getting accepted? And even I am not able to hack those solutions
How did this hack work? I'm confused.. https://mirror.codeforces.com/contest/1283/hacks/604551
problem D I used unordered_map but I got TLE. I instead of map is AC??? why? I think umap is faster than map. please explain for me, thanks!
I had the same issue!
https://mirror.codeforces.com/contest/1283/submission/67820013. Here you can see my first implementation using unordered_set. This submission received TLE on test case 6.
https://mirror.codeforces.com/contest/1283/submission/67838787. AC submission. In this submission I only changed the unordered_set to set.
Initially, I thought that this discrepancy was due to unordered_set having a very large constant factor, but the strange thing is that it seems that in general, unordered_set performs better than set for this implementation. For example, in test cases 3, 4, and 5 (which all have very big n), the unordered_set implementation has about 1.5 to 2.5 improvement over set in runtime. It seems that test case 6 is an outlier where unordered_set performs at least 5x slower than set.
I didn't know that unordered_set could be exploited. Is there a different reason that this may be happening?
same thing happened with me https://mirror.codeforces.com/blog/entry/72541?#comment-568565
My guess is that set has a tree underneath while unordered_set has a hashtable. The latter has O(n) worst case performance for basic operations against guaranteed O(log n) of the set.
umap uses an inbuilt hash function to map the values and as you all know that hashes are collision prone hence that TLE you got.umap is O(1) as long as it doesn't face collisions but as collision increase its complexity turns O(n), it's basic knowledge.
everything is basic for future LGMs
Its sad to see that we lost a one and only n(b)oobita of ours :(
Thanks, I had never gotten into this kind of situation before, so I was thinking the inbuilt hash functions are really efficient XD , I will be avoiding unordered stuff from now onwards XD
There is a chilli hash which i dont remember but is known to be quite efficient so its recommended to use chilli hash when using unordered map. IDK if any hacks of it have been found yet though
Yeah, because unordered_map can have a lot of collisions because it's implemented as a hash table...
For all who is surprised by why this was the accepted solution: I am surprised not less than you. Thank you badcw for noticing this.
I will try to explain why this happened: when I wrote the checker I forgot to check the stupidest thing — check that all $$$nf_i = f_i$$$ for such $$$i$$$ that $$$f_i \ne 0$$$. I don't understand how could I forgot to do this, but this happened. As you can understand, nobody noticed the mistake and during the round nobody informed me about such weird thing. The comment above is the first source where I found this issue.
I'm very sorry about my stupidity and I didn't want to ruin your fun from participating in this round. I apologize to everyone who was and will be affected by this mistake. I know that MikeMirzayanov who is the (usual) author of the whole problemset is upset by this fact and I understand that many of you are also upset by this fact. Now I cannot do anything with it and can only apologize.
We will make a decision to make or not make this round unrated a little bit later and will inform you as soon as possible.
P.S. I can't even imagine how many participants can be affected by this issue and I'm so scared to find out it :(
Rated!
It appears the person who you linked got hacked. Did anyone else get affected by this error?
If not, even if there was an error in the checker, nobody really got affected. I don't think the round should be unrated in this case.
In fact, all my checker does is check if the printed array is a permutation without fixed points. So any solution that prints any permutation without fixed points can be accepted. And, as I can see, we already had 400+ hacked solutions and... further — more.
Just out of curiosity, are most of the hacks occurring because of incorrect checker, or just because there was some case that people failed to check/some wrong idea that would have failed even with correct checker?
I cannot check all 550+ hacked solutions (wow, 150 hacks during several minutes) by hand but I think that there are not so many people who wrote absolutely incorrect solution on purpose. I think many hacks are because of some special cases, but because of incorrect checker it can happen that these cases appear in the test data but checker just didn't checked them.
And the second issue I forgot about (but compared to the incorrect checker this is a small issue): almost all 15 tests I add are useful, but this is not enough to cut off all incorrect ideas and possible bugs. I forgot to add test cases to this problem. But because of the checker it does not matter now.
So the issue is that the incorrect checker just made pretests weaker?
Because people who passed weak pretests still ended up getting hacked, so the checker didn't make incorrect solutions become correct.
In that case, no round should be unrated because of weak pretests. If that was true, CodeCraft should be unrated every year.
Yes, the mistake of the checker was false negative (correct me if I'm wrong in the terminology) (accept some incorrect solutions, but not vice versa).
But I don't sure we can say that this issue can be reduced to "bad pretests" because at least the solution I linked above cannot even pass the first example.
So this is the reason of so many hacks going on, thanks for confirming that anyways
Nope it's false positive. falsely label wrong solutions as right.
That's fair.
I still don't believe it should be unrated, because at least people could check sample, but it would definitely make sense if it was.
Thank you for confirming the issue.
We cannot even see the test case on which our solution failed. I even don't know the corrected checker is working fine or not.
Resubmit your hacked solution and you will definitely see the error in the output (and in that way you can make sure that the checker works fine now).
I didn't wrote wrong solution on purpose for problem c ! but if known during the contest I would have changed code ! submitted my code again and it shows WA on test 17 ! It's unfair. Please keep the round unrated !
@_@ your solution is WA :)) this case, you distribute into slot but don't check index == value :)) not relative!
nvm
I think your solution will be rejudge :3
I think you should make it unrated for only affected people, so every one wil be satisfied :D
The total amount of rating changes should be zero if I get it right, so everybody will be affected.
Rating is negative sum game, but your point still holds.
No it's not necessary.
The same thing happened in codeforces round 601 and they made a form for the affected people.
i solved abcde at the time of the contest but i've got c hacked. Despite that, i don't want that the round be unrated for me.
Will hacked solutions be rejudged?
Read this comment. All solutions that which are hacked are already "rejudged" in some way (after the checker fix).
Sir, Please let the round remain rated as the ones who got C accepted by wrong means will be hacked by the end of hacking phase.
yeah. I would love to end the year at blue rating
Rated!! It isn't the checker's fault if people randomly submit without testing sample cases.
vovuh you are a lucky guy! The round is rated!
Only 15 official participants have been affected noticeably by the issue in the problem C checker: I reviewed all the verdicts after the final testing and found such submissions that failed on the examples (but didn't fail on them while the contest). Only 9 of them have non-positive rating changes. So I excluded all of them from the official participants. They are:
Miracles happen! Happy New Year!
Thank you! You can imagine how glad I am when I got the top 750 for the first time and it's rated @@
I got stuck in C for about an hour and you just saved me from getting -100!
Thank you so much MikeMirzayanov and Happy New Year!
My approach for problem C is to sort the array containing not_occupied position. Iterate from 1 to n and if at any i ar[i] is 0 and i!=maximum_not_occupied_position ar[i] = max_not_occupied_position else ar[i] = min_not_occupied_position.
Still my soln gets hacked what is the counter case please tell
Well I think there is some problem in judge that is leading to all those hacks
3 0 0 1
in problem 3. if we print n 1 2 3 4 . . . n-1; for all n. will it be correct solution ??
I think it's wrong to change a value that's not 0.
Can we hack randomized solutions for C? https://mirror.codeforces.com/contest/1283/submission/67811299
The probability that a random permutation is a derangement is approximately $$$1/e$$$, and that is dense enough for randomised solutions to work.
What is the correct way to solve C ?
You can maintain two sets:
The one which are bad positions set (i.e Index = unfilled element in array) and the other good positions set(i.e are missing from array but no problem as their value != unfilled_position in array)
Now, you just need to handle the bad positions set first.
I did it in the following way, there can be various other ways.
for example, if my array was 3, 4, 6 of bad positions. I would circularly assign positions, example a[3] = 4, a[4] = 6, a[6] = 3;
and for the remaining 0's positions, you can assign as you wish from good_position set.
Here is my submission — https://mirror.codeforces.com/contest/1283/submission/67828215
I listed all the ones who did not give gift and all the ones who did not receive gift. sorted these 2 lists.
When i==1, swap shouldn't happen as now a[i]!=b[i] ?
oops i fixed it now.
Let s be the set of people who didn't give their gifts yet. Let t be the set of people who didn't receive their gifts yet.
For every person in s, assign to him any person (different from him) in t. Note that this is possible for all people in s except the last one (If we assign greedily). However, it's guaranteed that at most 1 person will be assigned to himself. Assume this person p exists. To fix this issue, choose any person (!= p) in s (This is guaranteed since it's given that the size of s is at least 2) and swap his answer with the answer of p. Done :)
Hello everyone... I need help >_<. Can anybody check what's wrong with my solution of problem C if you don't mind. (Although it's already hacked xD, but I don't know how to see the test case) https://mirror.codeforces.com/contest/1283/submission/67820446
I'm trying to figure out the correct way to solve this. Thank you!
Already found my mistake. :"D
Can you tell me on which testcase your code is going wrong as my solution for problem C is also been hacked but still I'm not getting my mistake. Thank You!
This should happen with me too
Very nice contest with interesting problems. Thank you vovuh.
Can anyone here tell why using unordered_set is giving me TLE on D , where as using only set is passing the tests?
unordered set solution,
set solution
the unordered set soln was working fine until test case 5, which is of same order as test case 6, but giving TLE in test case 6;
issue resolved -> https://mirror.codeforces.com/blog/entry/72541?#comment-568531
same E from past div3 round https://mirror.codeforces.com/contest/1203/problem/E
old version cannot become equal to zero and no more than n. but this not, max result can greater than with n + 1
https://mirror.codeforces.com/contest/1203/submission/67844337 this code solved both problems , just change variable prev initial value
case: n = 3 and a = [3 3 3]. result1: 1 2. result2: 1 3
https://mirror.codeforces.com/contest/1203/submission/67844337 https://mirror.codeforces.com/contest/1283/submission/67809780 different problems , same code
The procedure in F defines a bijection between set of all trees with labeled $$$n$$$ vertices with one vertex picked and set of sequences of length $$$n - 1$$$ with entries from $$$[1, n]$$$, which proves, that there are $$$n^{n - 2}$$$ labeled trees with $$$n$$$ vertices. Really nice :).
Press F for vovuh :(
For C task, were we aloud to change spots that weren't 0 or not? Cause the task says we need to fill in spots that have 0s in them, but during hacking phase I saw a solution that just printed sequence 2 3 4 5 ... n 1 (which was accepted).
Stop crying for that now . Lets see what vovuh ans mike decide .
It's Rated!
Can someone help me find the reason why my submission for problem D get TLE on 12, and it's memory is too large, it works pretty fast before test 12.
67830125
Thanks in advance :)
What is the probability tag for c?
Problem D is a beautiful application of all-sources BFS.
How to solve F?
Code Can Someone help I am getting WA on testcase-19 of Problem E
I think your solution will fail on this
Yes I got it thanks
How to find the first answer in problem E?
Can someone provide an explanation to the greedy solution for task E. I am able to calculate the max value ; however I am slightly missing something while calculating the min value
This is a fully commented code and explains what I am trying to do.
I think there is maybe some more ways to merge than I have taken into account. A deeper insight on the greedy approach to the problem would be appreciated. Thanks in advance.
well first of all thanks for the reply. But isn't it invalid input as numbers need to be less than or equal to n ( Mentioned in input format )!
Yeah. I didn't notice it. But it doesn't matter.
Oh thanks now I get it. Basically I am seeing 2 and 4 first ; dragging them to mid 3 ; and thus we will be left with 1 5 and lots of 10s.
Then that 1 5 increases the answer. The first thing that is coming to my mind is switching the order in which I wrote down the conditions. I don't know whether that will work or not... but I am going to try that.
Update : Oh ; that also fails. Now I need to do something clever I guess...
Could you give me some hints on :
1 : How could I correct that. 2 : How did you come up with that test case. I mean your thought process while test case design !
well i was stuck on max so i used your idea and got AC. here is what I did for min:
sort array and remove duplicates in array
then you count all unique numbers
Update : Done ! Code : https://mirror.codeforces.com/contest/1283/submission/67847724
Special Thanks to stefdasca and tribute_to_Ukraine_2022 for providing valuable inputs whether related to test cases or the code/approach itself !
I think stefdasca's idea to find min is really really simple ; both to think and prove ; those benefitting from this discussion should really look into his code https://mirror.codeforces.com/contest/1283/submission/67847914
I see too many hacks for C...wonder why??
https://mirror.codeforces.com/blog/entry/72541?#comment-568517
Code
Could anyone tell me what problem is in my code? (min part)
I merged 3 consecutive values to center one. (I marked flags)
And then I merged 2 consecutive values to right one. (I marked flags to avoid a wrong move)
Finally, I merged possible (exist none exist) cases to the center(none).
Thank you for helping me!.
Oh, I found the problem.
Here is my solution for problem C. It is been hacked but still I'm not getting any testcase where it is going wrong. Can anyone please look into my code and say where will it go wrong!
67816712
Thanking you in advance for your help
6
6 0 2 0 3 1
i don't know what the problem is, but here is a wrong test case.
okay, got it. Thank You!
Is the round rated?
Really weak pretests :(
So what's the result after about 12 hours of discussions. Is it rated?
Yes, only 15 official participants have been affected noticeably by the issue in the problem C checker. The ratings will be updated in 10 minutes. I unrated all the participants from this list who has non-positive rating change.
You seems to be a good guy
He is the best guy ever!
My first 1700+ !!
Hey, me too...
happy & lucky 2019~~
I hacked 7 people in open hacking phase but still didn't get any positive response on my rating or my total score, isn't it weird ??[user:vovuh][user:MikeMirzayanov]
In educational round & div 3 ,there is no point for hacking.
Nice contest, especially F problem))))
I understand that there are n lamps and n-1 wire And you need to chooce a root lamp and every lamp can connect max 2 other lamps.
What is the required, can you clearfiy it a bit ?