### Um_nik's blog

By Um_nik, history, 4 years ago,

Hello!

I'm glad to invite you all to Round 485 which will take place on Tuesday, May 29 at 18:35 UTC+3.

There will be 6 problems in each division, 3 of them are shared between divisions. 2 of div.2 problems created by KAN, 7 others created by me. The contest duration is 2 hours. My problems were originally used in HSE Championship.

I would like to thank Merkurev and GlebsHP with whom I discussed the problems, I_love_Tanya_Romanova for testing, KAN for round coordination and Codeforces and Polygon team for these beautiful platforms. I would also like to thank HSE for organizing the event. Oh, and kb. for writing great legend for one of the problems (he will be surprised).

For those who for some reason like to know score distribution in advance:
div.2: 500 — 1000 — 1250 — 1750 — 2250 — 3000
div.1: 500 — 1000 — 1750 — 2500 — 2750 — 3000
But I didn't properly discuss it with KAN so this is subject to change :)
UPD: Discussed with KAN, scores for C and D in div.2 increased by 250.

Good fun, have problems, read all the luck. As usual.

Oh, and if there will be no bad things, round will be rated. I hope.

I'm very sorry for issues with queue. I understand that it could ruin the contest for many of you. But please be understanding. Bad things happen. It could be some network problems or some electricity problems. MikeMirzayanov, KAN and other people behind Codeforces trying their best to provide good service. But sometimes it's very hard for some reasons. I hope that you enjoyed the problems despite all the bad things.

We decided that round will be rated.

Editorial will be posted tomorrow.

div.1 winners:
1. tourist
2. MiracleFaFa
4. webmaster
5. LHiC

div.2 winners:
1. sminem
2. Fortza_Gabi_Tulba
3. cheburazshka
4. Lomk
5. 2ez4me

Editorial is up.

• +656

 » 4 years ago, # | ← Rev. 2 →   +37 Good fun, have problems, read all the luck. As usual. Love how the words were jumbled and at last as usual :P.
 » 4 years ago, # | ← Rev. 2 →   -28 Meow ! :)
•  » » 4 years ago, # ^ |   -13 bow wow XD
 » 4 years ago, # |   +34 And also thanks to MikeMirzayanov for systems Codeforces and Polygon:)
 » 4 years ago, # | ← Rev. 14 →   -149 SpoilerBot test comment . Spoilermeooow hello. SpoilerDont forget to add me in contributors.md
 » 4 years ago, # |   0 KAN is my favorite
 » 4 years ago, # |   +22 If KAN didn't invent easy tasks, we would have div 1 only round :D
•  » » 4 years ago, # ^ |   +327 No, you would have bad div.2 round :)
 » 4 years ago, # |   0 B and C in div2 have the same score ,Will they have the same difficulty ?
•  » » 4 years ago, # ^ |   +58 SpoilerSpoilerSpoileryes
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +13 too many spoilers
•  » » » » 4 years ago, # ^ |   -169 SpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerI don't think so.
•  » » » » » 4 years ago, # ^ |   +121 For those wondering, there are 31 spoilers.
•  » » » » » » 4 years ago, # ^ |   +6 I counted 32...
•  » » » » » » 4 years ago, # ^ |   +49 Spoiler limit exceeded
•  » » » » » » 4 years ago, # ^ |   +5 thanks
•  » » » » » » 4 years ago, # ^ |   +12 it is 32
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 Huseyn_Hajiyev You really spoiled the thing.
•  » » 4 years ago, # ^ | ← Rev. 2 →   -35 Good Question. And nice observation.
 » 4 years ago, # |   -28 so excited <3
 » 4 years ago, # |   -95 could you please make the start time a 1 hour earlier (at 17:35 Moscow time) . we in egypt have fast breaking at (19:35 Moscow time) as we fast in this month from dawn to sunshine every day so we won't be able to compete :-). like if you agree
•  » » 4 years ago, # ^ |   +69 Every hour there is muslims have fast breaking , not only in Egypt, i think that is the main reason for ones who downvoted your comment
 » 4 years ago, # |   -17 GOOOOD LUCKK 4 EVERYONE :з
 » 4 years ago, # |   +48 on 11-th line it is incorrect to say i didn't discussed because did is always followed by a verb in PTS(present tense simple)
•  » » 4 years ago, # ^ |   +5 *in infinitive
•  » » 4 years ago, # ^ |   +26 Nice catch. Thanks. Fixed.
•  » » » 4 years ago, # ^ |   +2 discuss not discusse :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +50 Ok then, you should say "If there are no bad things, round will be rated", cause it's first conditional.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -12 2 of div.2 problems created by KAN, 7 others created by meshould be2 of div.2 problems were created by KAN, 7 others were created by me
•  » » 4 years ago, # ^ |   +43 successful hacking attempt +100
 » 4 years ago, # |   -57 after 3 years of codingi still fight in #Div_2 -_-
•  » » 4 years ago, # ^ |   -55 U still lose* in Div2Lol NOOB
 » 4 years ago, # |   -61 My comments will have more downvotes than upvotes on this post. Do Down Vote.
 » 4 years ago, # |   +42 Two hours and we have problems worth 1750, 2500, 2750 and 3000. Is that best choice of duration?
•  » » 4 years ago, # ^ |   +139 I just think that standard distribution is bad because you usually solve C on 0:30 and E on 1:55 -> they give the same points. Also we added easy problem so we had to increase scores of other problems. So, yes, I think that the difficulty is comparable to "average round" whatever that means. But I may be wrong :)
•  » » » 4 years ago, # ^ |   +27 That's the answer I wanted to hear (y)
•  » » » » 4 years ago, # ^ |   0 I think you read it :)
•  » » » » » 4 years ago, # ^ |   -29 but he wanted to hear
•  » » » » » » 4 years ago, # ^ |   -36 you know you are on CF, when the red gets +40 for stealing your joke, while you get -20. you guys really don't know how to apply your logical reasoning outside solving useless problems
•  » » » » » 4 years ago, # ^ |   +38 But maybe I wanted the very Um_nik to whisper it gently to my ear, but somehow stopped desiring it the moment whe he replied here to me? Hm? Have you ever thought about it?
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   -22 I just wrote my opinion: I think you read it :)
•  » » » » » » » 4 years ago, # ^ |   -39 I'm just writing my opinion: I think you should shut the fuck up.
 » 4 years ago, # |   -72 KAN gives t-shirt winner in the contests.
 » 4 years ago, # |   -33 So rating 1953 will be rated in division 2?
•  » » 4 years ago, # ^ |   +6 No, purple coders will be rated in Div1 as before. Nothing has changed for Div1 rounds.Just that purple coders can now officially participate in Div2 — only rounds (today's round is Div1 + Div2 so they are rated in Div-1).
 » 4 years ago, # |   -86 I hope there are no problems from Graph Theory.
•  » » 4 years ago, # ^ | ← Rev. 2 →   -8 Really??? I hope all problems will be related to Graphs. They are great!
•  » » » 4 years ago, # ^ |   +1 Indeed , I love Graphs !
•  » » » » 4 years ago, # ^ |   +9 Very, very true ! I think all the problems will be great, not only the graph ones ! Anyway, there is no perfect contest if no graph problems or problems that are solved using data structures based on graphs are included !
 » 4 years ago, # |   -19 Oh, and kb. for writing great legend for one of the problemsHope that's the only problem with legend :(
 » 4 years ago, # |   -11 Finally Codeforces round. Really the point distribution is great. Goodluck to everyone.
 » 4 years ago, # |   -7 Oh, and if there will be no bad things, the round will be rated. I hope. :D :D :D Nice statement.
 » 4 years ago, # |   0 Where can I see problems of past HSE editions?
•  » » 4 years ago, # ^ |   +12 HSE is the university I attend. I made a championship for its students. As far as I know that was the first one.
•  » » » 4 years ago, # ^ |   +16 Happy to see you in the list of top contributors.
 » 4 years ago, # |   +21 I hope tourist will regain His position after this contest
•  » » 4 years ago, # ^ |   +5 I also feel so.
•  » » 4 years ago, # ^ |   +10 Petr rlz!
 » 4 years ago, # |   0 i cant registration ...
 » 4 years ago, # |   0 hacks window not opening. -_-
 » 4 years ago, # |   +77 terrible queue :(
•  » » 4 years ago, # ^ |   0 20 pages of queue...
•  » » » 4 years ago, # ^ |   0 30 now ... :(
•  » » » » 4 years ago, # ^ |   +2 50 now
•  » » 4 years ago, # ^ |   +1 What happened?
•  » » » 4 years ago, # ^ |   +3 smells like unrated round :'(
•  » » » » 4 years ago, # ^ |   +12 That's terrible!
•  » » » » 4 years ago, # ^ |   0 should be
 » 4 years ago, # |   +10 queue:(
 » 4 years ago, # |   +1 Extend the contest.
 » 4 years ago, # |   +10 So Long Queue I guess Codeforces need to work on that, so that it occurs less often... Please See to that Admin.
 » 4 years ago, # |   -18 queue is gone
•  » » 4 years ago, # ^ |   0 in div1 still 5+ pages
 » 4 years ago, # |   +20 After waiting 10 minutes for my solution to be judged I found out, I printed "um_nik" instead of "Um_nik".
•  » » 4 years ago, # ^ |   +4 And I declared array of size of 10^5 !!!
 » 4 years ago, # |   0 Submissions in queue!
 » 4 years ago, # |   +65 Oh, and if there will be no bad things, round will be rated. I hope.Yeah, you jinxed it right then...
 » 4 years ago, # |   +5 if there will be no bad things, round will be rated. I hope.
 » 4 years ago, # |   +31 After waiting for 20 minutes my solution starts being judged, passes 9 pretests, and then...Voila!!! It's "in queue" again!!! WTF is that???
 » 4 years ago, # |   +10 So, we have to wait more than 20 minutes for verdict, but time is extended only 10 minute. Is it fair?
 » 4 years ago, # |   +29 Codeforces is crashed again and again and again. In queue ........ (20+ minutes later) Compile Error (because of different version of C++)
 » 4 years ago, # |   +5 Another semi-rated round? lol
 » 4 years ago, # |   +56 is it rated?
•  » » 4 years ago, # ^ |   +21 It should not be rated as many submissions(more than 40 pages) remained in queue even at the end of the contest.
•  » » 4 years ago, # ^ |   +13 after a long time i see a comment "is it rated?" and that have upvotes (Wow)! :D
 » 4 years ago, # |   +64 Nothing personal, but round must be unrated
•  » » 4 years ago, # ^ |   0 Submissions after 1:30 was in queue even after a long time after contest’s end
 » 4 years ago, # |   +9 Longest queue ever -_-
•  » » 4 years ago, # ^ |   0 I beleive u r new to cf
•  » » 4 years ago, # ^ |   +3 I beleive u r new to cf
•  » » » 4 years ago, # ^ |   +43 I believe you have poor internet connection.
•  » » » » 4 years ago, # ^ |   +8 No, but my laptop is lagging too much today.
 » 4 years ago, # |   +55 The most stupid thing ever:Ouputted "Alex" instead of "Um_nik".
•  » » 4 years ago, # ^ |   +19 Aaaaah, so this is why I got WA #3. Shit :D
 » 4 years ago, # |   +6 How to solve E?
•  » » 4 years ago, # ^ |   +2 Basically the question is about checking whether a permutation is odd or even. If there are c disjoint cycles in a permutation, then the permutation is even if n-c is even, and odd if n-c is odd.(Source)
•  » » » 4 years ago, # ^ |   0 My solution was on based on the fact that if that if there are n swaps to change an array then we can't do the same with x swaps if parity_x != parity_n. So I counted the number of swaps in bubble sort same as number of inversions in an array and checked its parity with n. If same, ans if Petr else Um_nik
 » 4 years ago, # |   +2 The round was really good until Problem E appeared, it is bad problem and made the queue completely full
 » 4 years ago, # |   +9 I thought I (most probably) solved four problems (Div 2 A,B,C,D) and would be blue within this month but this is how my hope is dashed :'(
 » 4 years ago, # |   0 seems unrated to me :(
 » 4 years ago, # |   +5 CF don't feels so good
 » 4 years ago, # |   +1 how to solve Div2-D?
•  » » 4 years ago, # ^ |   +5 A multisource BFS will do the job.
•  » » » 4 years ago, # ^ |   0 can you please explain it a little more?
•  » » » » 4 years ago, # ^ |   0 Just push every starting vertex into queue, and do normal bfs.
•  » » » » 4 years ago, # ^ |   +1 In a normal bfs, you put initially in the queue just one nod. In this problem you must put all nodes that have the same color, and run the bfs for each color.
•  » » » » » 4 years ago, # ^ |   +3 I am unable figure out the intuition behind it. If u don't mind can you please elaborate? thanks !
•  » » » » » » 4 years ago, # ^ |   0 We can get the distance from every point to it's nearest source of each color. After that, sort it for every point and add the first s elements together.
•  » » » » » » 4 years ago, # ^ |   +1 You need to compute a matrix like this: dmin[i][j] -> minimum distance from node i to the closest node with color j.If this matrix is computed, we can find the anser by sorting each vector dmin[i] and taking the first s values.This matrix can be computed using the bfs described above ;)
•  » » » » » » 4 years ago, # ^ |   0 I based my solution on the fact that k is small (<=100), so an O(n*k) or similar solution is feasible. Basically, we can just let an array least[n][k] be the minimum distance to node n for good of type k. We can fill these array by using k BFS, one for each color. Then for each node i, we can just take all the distances least[i][k] for 1..k and then select the s smallest.
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   +7 Note that k is at most 100. Therefore, we can try the following:Denote dist[i][j] as the minimum cost of town i to get a good j from any town.For each type of good i, push all x such that ax = i into a queue, and set dist[x][i] = 0. Then, we do normal BFS to update the dist array. This has O((n + m)k) time complexity.Then we find the sum of s smallest elements in dist[i] for each i from 1 to n, which can be done by sorting.
 » 4 years ago, # |   +11 It's now the end of the contest but my solution from 1:38 is still in queue now. I did Mo's algorithm and how can I be able to now if my block size is not optimized? And how can I even debug my solution if I get a WA. I spent my whole contest doing this...
•  » » 4 years ago, # ^ | ← Rev. 5 →   +8 UPD : I got RTE with the very first sample test which ran fine on my computer now. :/ UPD2 : I should write idx[NP + 1] instead of idx[NP]. Really...
 » 4 years ago, # |   +12 Should a k*(n+m) solution pass Div 2 D?If so, could someone tell me what's wrong with mine?Solution here (in Java): http://codeforces.com/contest/987/submission/38744336
•  » » 4 years ago, # ^ |   -10 I think 'Collections.sort' is too slow to pass tests with big constraints.
•  » » » 4 years ago, # ^ |   0 Dang, I was hoping klog(k) in the sort wouldn't matter that much. How could I get the s smallest values in the list without sorting?
•  » » 4 years ago, # ^ |   +1 You are sorting the costs. -> therefore you have an additional log factor.
•  » » » 4 years ago, # ^ |   0 How do we get the k smallest without sorting the costs?
•  » » » » 4 years ago, # ^ |   +1 The selection algorithm does it in linear time.
•  » » » » » 4 years ago, # ^ |   0 Thanks! Even partial_sort is good!
 » 4 years ago, # |   0 Was it slow or my internet connection became slow at the last few minutes??? :oBTW. How to solve problem C?
•  » » 4 years ago, # ^ |   0 I used dp there.State of my dp were dp[n][2],dp[i][0] tells me what is the minimum cost in which I can select two displays(k and i) such that s[k]
•  » » 4 years ago, # ^ |   +3 CF was slow for me also! C can be done by Dynamic Programming.
•  » » 4 years ago, # ^ |   0 what I did is for every element, have 2 priority queues and add the cost[i] to pq depending upon the font size. Now the size of both pq has to be greater than 1 for answer to be present. check for the min. As the value of n was 3K, I think this should pass.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 For every display i (i from 2 to n), find the display x[i] (x[i] from i + 1 to n) that s[x[i]] > s[i] and has the smallest price (you can do it with 2 'for' iteration. Then you run 2 'for' iteration (i = 1 to n - 2) (j = i + 1 to n - 1), update res with min(res, c[i] + c[j] + c[x[j]]). res is the result.
 » 4 years ago, # |   +109 Sorry, guys :(I completely has no idea what happened. One network service unexpectedly started to be slow (first time ever!). Probably, because of network/system issues. I worked hard since noticed an issue, but without any progress.This fail is completely surprising for me (Sorry, Um_nik. I hoped as much as you to host a great round. Very upset about the situation.I continue to investigate the situation.
•  » » 4 years ago, # ^ |   +29 is it rated?
•  » » 4 years ago, # ^ |   0 Make it unrated .
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # |   +6 "Oh, and if there will be no bad things, round will be rated. I hope."are system down and long queue considered as bad things?
 » 4 years ago, # |   +48 Woah! Hey, Nobody mentioned that ranklist will be frozen during the last hour. Was away from cf for sometime, when did they introduce that?
 » 4 years ago, # |   +2 My question is still in queue!??
 » 4 years ago, # | ← Rev. 4 →   0 Lol my hack is still in queue. Just a suggestion, for div2C a bonus problem can be included where n<=10^5. Just like Round 350. How to solve it in O(nlgn)?
•  » » 4 years ago, # ^ |   +3 I don't know about O(n) but u can do O(nlogn) using Segtree
•  » » » 4 years ago, # ^ |   0 Sorry edited my comment. O(n) might be impossible. How to do it in nlgn using segment tree?
•  » » » » 4 years ago, # ^ |   0 U got the n^2 dp ri8? dp[i][j <= 3] = min cost with j elements in increasing order.So dp[i][j] = c[i]+min(dp[k][j-1]) where a[i] > a[k],i > kMake a segment tree for each j, keep updating seg[leaf a[i] or whatever] by c[i]. Now take min 1..a[i]-1 as query
•  » » » » » 4 years ago, # ^ |   0 Can the dp be formulated as dp[i][j] = minimum cost obtained upto position i with maximum size being at index j?I tried doing this way but got WA on pretest 7. Am I doing some mistake?
•  » » » » 4 years ago, # ^ |   0 You can use Fenwick tree with minimums
 » 4 years ago, # |   +49 54 pages of queue right now. Make it Unrated please.
 » 4 years ago, # |   +18 For D, I understand the solution is basically "find the smallest power of 3 >= N, N/2, N/4". But how can I find that power for constraints that are this insanely large? Even if I know the exponent and want to check if N isn't just a little bit larger/smaller than that power of 3, it seems impossible with these constraints...Also, I can't post this comment, CF is broken again.
•  » » 4 years ago, # ^ |   0 Fast exponential + FFT for multiplication seem reasonable.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +10 So that's plus the not-very-great constant factor of FFT? Note that I wrote "with these constraints".
•  » » » » 4 years ago, # ^ |   0 Well okay, fair enough. At least there are accepted solutions like that. Also my solution works in >10 sec. and I hope that's not the intended solution.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 You should estimate logarithm by something like length * log(10) / log(3) and check constant number of integer values close to it (by computing this power for smallest of numbers we want to check, let it be (length — 1) * log(10) / log(3) — 1) and then try multiplying it by 2, 3, 4 in desired manner. You should group digits in some blocks to make it pass in TL with FFT exponentation (what I haven't done).Complexity of this is something like multiplying two polynomials on degree 200000 once. Note that in binary exponentation, in terms of complexity I can ignore all multiplications except last one because length grows two times with every step.
•  » » » 4 years ago, # ^ |   +20 Yes, I know I should estimate log, so I can check only ceil(log) and possibly ceil(log)-1 if the fractional part of ceil(log) is close to 0. Note that I wrote "want to check if N isn't just a little bit larger/smaller than that power of 3".If FFT exponentiation is actually the official solution, then this problemset would have massively benefited from having D removed from it. In that case, there wouldn't be any problems with stupid constraints, any boring problems (AFAIK), any problems that are only hard because of bigints, any FFT (AFAIK), the contest difficulty would be more appropriate for 2 hours...
 » 4 years ago, # |   +5 I tried submitting in the last 20 minutes . but it only showed queued . Make the contest unrated. Its not fair .
 » 4 years ago, # |   +13 I cannot understand the statement in Div1D.. :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 ID is not a number, it — is an array of [a1, a2, .. am]. good luck.For example: n = 36, m = 3 b[] = { 3, 3, 4}so number of different arrays are: { 1 , 1, 1 }{ 1, 1 , 2 }{ 1, 1, 3 }{ 1, 1, 4 }{1, 2, 1}..........{3, 3, 4 } Total number of such arrays equal to 36.
•  » » » 4 years ago, # ^ |   0 It might be better give an example as usual in other problem. I really confused what ID refers *_*
 » 4 years ago, # |   +16 How to solve Div2-F or div1-C?
 » 4 years ago, # |   +35 Still queuing the contest should be unrated.
 » 4 years ago, # |   +10 I feel stupid... for not solving B. Don't think I even have a valid clue -___-
 » 4 years ago, # |   +27 D is easy to reduce to calculate ceil(log3(101.5e6)). Is it well-known?
 » 4 years ago, # |   +66 Round is still rated? That's unfair. 30+ minutes queue at the end. Atleast make it "semi-rated".
•  » » 4 years ago, # ^ |   0 yep, yep, you are right it must be FunRated
 » 4 years ago, # |   +9 And people started to think it "unrated". Then came the announcement! ;)
 » 4 years ago, # |   +28 No, it's not like D was everywhere million times, no. However this time with bonus in form of bigints. Yesterday I was making fun of Radewoosh reminding him how he got TLE on bigints because he used them in base 10 last time when Um_nik was a problemsetter. Today I did the same in D...
•  » » 4 years ago, # ^ |   +167 Me trying to understand this comment
•  » » » 4 years ago, # ^ |   +16 Some nutella things
•  » » » » 4 years ago, # ^ |   +21 i hope to live enough to discuss a problem with them
•  » » » » » 4 years ago, # ^ |   +11 We all hope :(
•  » » » » 4 years ago, # ^ |   -14 so you have self f***ed
•  » » » 4 years ago, # ^ |   +45 OK, slowly. Um_nik set this problem in the past: http://codeforces.com/contest/756/problem/E and it required bigints. Radewoosh more or less did this problem, but calculated bigints in decimal base instead of base 1e9 what led to significantly slower time of execution and he got TLE. He whined about this in comments and because of that he was kinda ridiculed by Um_nik for using base10. I reminded this situation yesterday to Radewoosh and laughed about it, but today I did the very same mistake.
•  » » » » 4 years ago, # ^ |   +73 if i never solved the problem, this can't happen to me
•  » » 4 years ago, # ^ |   0 Maybe I just hate you guys :)I hope that it didn't ruin the contest for you (maybe some other things did haha).
•  » » » 4 years ago, # ^ |   +15 This is not a very glorious problem, but I think I am more angry at myself than at you. I think F is a very good problem, too bad I didn't have time to fully appreciate it. And B and C were cool as well.
•  » » » » 4 years ago, # ^ |   +1 Thanks :)I agree that D is not very fresh, but bigints also require some small ideas (but yeah, more implementation).
•  » » 4 years ago, # ^ | ← Rev. 2 →   +18 So you wrote this comment not to let Radewoosh write it?
 » 4 years ago, # |   -29 Is it correct for E? print('Petr') 
•  » » 4 years ago, # ^ | ← Rev. 5 →   +8 n = 2 2 1 ans should be "Um_nik"
•  » » » 4 years ago, # ^ |   0 N can be 1000 at least
•  » » 4 years ago, # ^ |   +8 Key to solve this problem:Parity of a permutation
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Can parity of a permutation be computed using this method: Count minimum number of swaps required to make the array sorted and if it is odd we can say that the permutation has odd parity else even parity. If not then can anyone provide some test case to counter this?
•  » » » » 4 years ago, # ^ |   0 I think your method is correct (Since only the number of swap matter).
•  » » » » » 4 years ago, # ^ |   0 http://codeforces.com/contest/987/submission/38747479 Can you tell me whats wrong with this solution ??
•  » » » » » » 4 years ago, # ^ |   0 The problem was with indexing of arrays :( :(
•  » » » » » 4 years ago, # ^ |   0 So if (3*n-x) is even then answer is Petr else Um_nik. Is it?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 xuanquang1999, dheeraj_1997 Can you please explain me how did you reduce the problem to finding Parity of Permuation?
•  » » » » 4 years ago, # ^ |   +1 To be honest, this is just experience. I learned about parity of permutation in a TopCoder problem. When I meet this problem, I noticed that the parity of the number of swap in Petr and Um_nik are always different, and get reminded of this.
•  » » » » » 4 years ago, # ^ |   0 I didn't get this. Can u please explain me how parity for Petr and Um_nik are different, with an example?
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +2 Assume that n = 2k + r (k is integer, r is 0 or 1).Then the parity for Um_nik minus parity for Petr is:(7n + 1) - 3n  = 4n + 1  = 4(2k + r) + 1 = 8k + 4r + 1which is always an odd number.
 » 4 years ago, # |   +36 Very end of the contest?:| Really?
 » 4 years ago, # |   +52 If the test is generated via Alex's method print "Um_nik" Cool trick bro!
 » 4 years ago, # |   +23 Is it even possible to solve Div2D in Java? Very few Java solves on it, and I saw people submitting in Java and then switching to C++ with the same code get accepted.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +1 I had to change my graph representation from List[] to int[][] and change sorting algorithm to Egor's ArrayUtils.sort() and it passed systests.Before doing that I had TL6 like many others. Here is my accepted code: 38738273.
 » 4 years ago, # | ← Rev. 2 →   +22 I tried to solve B in the last 30 minutes after trying to solve C all contest. Not getting any feedback was not nice :/Well at least I can participate in Div2 contests now.EDIT: the reason my original submit didn't pass was that somehow I thought 3 * n was always even, and compared number of inversions % 2 against 0 instead of n % 2. Well this one is on me.
 » 4 years ago, # |   +8 Despite the issues during the round, i enjoyed the problemset a lot. Thank you guys!
 » 4 years ago, # |   -54 plzz don't make it unrated i got +154 this time ploxx
 » 4 years ago, # |   +7 It was a good contest. The problem sets were cool. (Though I was unlucky and completely ruined my contest). Anyway I submitted C n D at the very end n I wish I could know if anything was wrong coz surely i think i could have corrected it. (even with weak pretests as they dont have any corner cases in my opinion)I think it will be unfair to keep the contest rated (i dont know when the system started to become slow but i submitted my C on 1 hour 40 min n still no verdict).
 » 4 years ago, # |   +35 Are 40 minutes considered as the VERY end of the contest in which the actual rank of the contestant is decided and matters a lot in his rating
 » 4 years ago, # |   +142 General announcement ***** We discussed the issue with the queue and decided that the round will still be rated because the queue only appeared in the very end of the contest. Of course all submissions in queue will be judged. We apologize for the issue and thank you for participation in the round, I hope you liked the problems.Yeah, right, around 1 hour 35 minutes mark is VERY CLOSE to the ending of a 2-hour contest. Nice!!! Really nice!!!
 » 4 years ago, # |   0 Can Div 2 C be done better than O(n^2) ?
•  » » 4 years ago, # ^ |   0 You can optimize it with Segment Tree or Fenwick Tree, but O(N^2) is enough.
•  » » 4 years ago, # ^ |   0 O(N log n) using the segment tree and compression
•  » » 4 years ago, # ^ |   0 this may help...
•  » » 4 years ago, # ^ |   0 Precompute (Si < Sj), adjust Si (smaller in range [1..3000] — I dont know how its called in English). in Si, mark the node[s[i]] in segmen tree as Ci, then Query from [Si — 3000]. Every not-filled nodes, mark them as INF.
 » 4 years ago, # |   +38 How can this round be rated? Submissions were not evaluated for more than 30 mins towards the end of the contest. This is really sad.
 » 4 years ago, # |   0 for problem f, can we do it by creating binary trie? we insert each element in trie (by representing each element in 23-bit format). then for each element, we traverse trie bit by bit. if current bit of current element is set to zero we go either zero edge or one edge, else if it is 1 we can only go towards only zero edge(this way we traverse for all 23 bits of element). if we reach end of trie (while representing elements at last bit, i stored indexs) we can make a pair . then after all elements are done we can do a dfs to check connected components. will it work ?
 » 4 years ago, # |   0 Lol, the linear algebra class I attend this semester helped me to solve div2E/div1B easily:) Was literally looking into my linear algebra book during the contest
•  » » 4 years ago, # ^ |   0 How to solve E?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +4 It's about sign of permutation. Use the fact that the evenness of number of swap for generating a specific permutation from identity permutation is consistent(i.e.if a permutation is 3 swap away from identity permutation, it can never be generated by even number of swap from identity permutation) a cycle of length k in permutation is equivalent to k-1 swap (by "cycle", I mean, consider ith number in permutation as "the next node for ith node" like in a graph question)
 » 4 years ago, # |   +21 How to solve C? My brain kinda stopped working after spending nearly entire contest thinking about it.
•  » » 4 years ago, # ^ |   0 We can simply rephrase the property "X&Y==0" into "X is submaask of inverted Y". Then simply for each element go through all of it's submasks :)
•  » » » 4 years ago, # ^ |   +5 I think that number of edges is still too big.
•  » » » » 4 years ago, # ^ |   0 Yes, but in the end you go through only O(2^N) states, if you remember the ones you already visited.
•  » » » » 4 years ago, # ^ |   0 We dont need to use DFS or BFS on graph to count answer. Just using DSU and DFS on the mask is fine.
•  » » » » » 4 years ago, # ^ |   0 If the number of edges is big, DSU or DFS is still too much.
•  » » » » » » 4 years ago, # ^ |   0 I agree.But we are using DFS on the mask, not on the graph. So edges number is about 22 * (2 ^ 22), and vertex number is 2 ^ 22.
•  » » » » 4 years ago, # ^ |   +5 I think we can improve it by dividing the vertices in a similar manner to SOS DP
 » 4 years ago, # |   +43 I even cannot submit ( no respond when clicking on the submit button, refreshed a number of times ) during the last minute......
 » 4 years ago, # |   -449 Hi, we apologize for the queue. We discussed the situation with Um_nik and decided to make the round rated because The round was going to end — it's very unlikely for a participant to solve two more problems since then, so he can test his only problem throughly. There are plenty of rounds and the rating always goes up and down, so you shouldn't worry about a slight change that may be caused by the issue. Thanks Um_nik for great problems and thank you all for participation!
•  » » 4 years ago, # ^ |   +95 I think it's unfair.There're a lot of solutions for Div.1 E which has a complexity that can tightly fit into the time limit (such as O(n^1.5logn) and O(nlog^2n),even O(nlog^3n)).We don't know whether it fits into TL and can't decide whether to make the program run faster or change to another problem.It will affect participants a lot.
•  » » » 4 years ago, # ^ |   +48 Same for D. I do not know how much this queue affected Div2 Participants, but it was significant for Div1 participants.I have 4 submissions in Div1D because I did not know whether my solution was efficient enough and I did not get the verdict for a single one.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +13 I even lost my E for being RTE on sample test. What should we do with these undefined behavior cases of compiler without being able to resubmit it?
•  » » » 4 years ago, # ^ |   +17 There are also cases when someone got compilation error and learnt about it long after contest's end xD
•  » » 4 years ago, # ^ | ← Rev. 2 →   +38 I think Rated is an acceptable result. But I don't like your first reason. It has been stuck for over half an hour. I waited for a long time and receive a MLE, eventually I had no time to fix it. Meanwhile, for those who stuck in the first or two problems, they are very likely to solve two problems in the blocking time if the queue is normal.Anyway, I think these problems are interesting and Thanks Um_nik and Codeforces.
•  » » 4 years ago, # ^ |   +68 1) Больше 40 (!!!!!!!) минут не было вердиктов по сабмитам. На кф теперь такие правила? Почему не предупредили перед началом контеста?2) Может тогда время от времени рандомно давать +-100 к рейтингу каждому, ведь "есть много раундов и рейтинг постоянно меняется"?
•  » » 4 years ago, # ^ |   +5 I wanted to try D using python (which might be TLE), and in case of TLE I would implement a C++ solution. And I saw lot of people submitting D in python. I think the long queue affected in this way many people...Beside this, it was a really nice set of problems.
•  » » 4 years ago, # ^ |   +13 so30 minute of queue and system down are not considered as bad things.nice to know it
•  » » 4 years ago, # ^ |   +17 I remembered similar case happened in round# 449(the long queue was like 30-40 minutes if I remember correctly) and the final decision is to make the round semi-rated. So why is the decisions inconsistent and how to distinguish when to be rated, semi-rated and unrated.
•  » » 4 years ago, # ^ |   +94 "There are plenty of rounds and the rating always goes up and down, so you shouldn't worry about a slight change that may be caused by the issue.". This was the worst justification I've ever seen LOL
•  » » » 4 years ago, # ^ |   +41 Agreed. I can't believe that I heard this from a large coordinator on Codeforces.
•  » » » 4 years ago, # ^ |   +46 I think that logic can be applied the other way. There will be plenty of contests in the future so it won't matter that much if this one is made unrated.
•  » » 4 years ago, # ^ |   0 I submitted 4 solutions (if I had more 5 minutes, it would be 5) at last 30 minutes, and for all of them I didn't see the verdict. Now I see that my F got WA :(
•  » » 4 years ago, # ^ |   +131 Why so afraid of unrated round? Is it fair to submit several minutes after queue fuckup and receive RE1 because of UB, which can be fixed in 10 seconds? Point on rating going up and down is ridiculous, how the participant should estimate what problem to code if he doesn't know on which point the system is gonna go down? The rating of the comment shows what the audience feels about this, hope CF won't ruin the fun for participants this time.On the first point: in the announcement it was intended that the queue would resolve before the end of the contest, wasn't it? This ruins completely your first point.
•  » » 4 years ago, # ^ |   +15 I got MLE on test 15 in div1C. I submitted ~3min after the end of the standard 2 hour round. This is fixable in a minute, but I had no idea it would happen until ~2hrs after the end of the round.One could argue I couldn't have submitted before the contest ended had the queue worked normally. One could also argue I could have checked if 22·222 > 256·10242. That's irrelevant — I'm arguing that a slow queue for a non-negligible part of the round makes the round unfair.A few minutes before the end? I could accept your argument (although squinting a lot) because it doesn't mess up a round significantly. Half an hour before the end, or more? No.
•  » » » 4 years ago, # ^ |   0 Actually there will be at max 12*(2^22) edges, which is nearly 200Mb. What is even bad is that it was really close to memory limit and maybe reusing some vectors would had solved the problem easily.
•  » » 4 years ago, # ^ |   +25 "so he can test his only problem throughly" — There were quite a few problems with tight TL, and then it's very important to test the running time on CF with the custom invocation. I was impossible because of the big queue.The decision isn't terrible but I suggest making it unrated next time with similar circumstances.
 » 4 years ago, # |   -55 দ্য হেক!!!!!! কন্টেস্ট রেটেড!!!!???????আপনাদের কি রোজায় ধরসে?
 » 4 years ago, # | ← Rev. 3 →   +27 I have a question. Will we face a penalty for extra submissions, when we didn't know the verdict of previously submitted codes ??EDIT : I have submitted three codes for E in intervals of 5-10 minutes with some optimization, starting at 1:38, and the first solution has passed pretests. If a non empty subset of the other two pass as well, will it be skipped in system tests with a penalty??
•  » » 4 years ago, # ^ | ← Rev. 2 →   +23 Obviously (not that it makes sense, but it's definitely how the system works). I even think that technically they don't have the means to store the time when you saw the judgement result.
•  » » 4 years ago, # ^ |   0 Surely, we will. This is like this on Topcoder in every contest.
•  » » 4 years ago, # ^ |   0 His last submit got tle on pretests. And second last got pretests passed. So will it be judged in system tests? Atleast in tc, it won't be.
 » 4 years ago, # |   +17 I'd be fine with round being rated if you hadn't announced that long queue will be resolved shortly tbh.
 » 4 years ago, # |   +65 Very last period= 1:30+ I think it should be unrated becasue the influence is really big
 » 4 years ago, # |   +27 In Div1 there was queue for around 25 minutes in the end (35 including the extended 10 minutes) , I think that's significant to not keep it rated.
 » 4 years ago, # |   +2 Anyone solve C div2 using DP?
•  » » 4 years ago, # ^ |   +5 Is there any other way of solving it ?
•  » » » 4 years ago, # ^ |   +5 add left and right in a heap and pop from them. the answer would be minimum when done for all elements. The added complexity of adding into a heap comes into picture with this but I think it should pass.
•  » » » » 4 years ago, # ^ |   +3 There are two ways: Brute Force + RMQ (DP) or DP (LIS variation).Brute Force preprocess for each position i the minimum cost of any j > i such that ai < aj and fix i and j in a double for to get something like this: ans = INT_MAX; for(int i=0; i
•  » » » 4 years ago, # ^ |   +5 Yes there is ! Fix j and then iterate over elements in interval 1-(j-1) and find the best of them(the c[i] minim that so v[i] < v[j] and i < j) and then the same with k(find c[k] minim that so v[k] > v[j]) and then update the global solution so you have a O(N^2) solution. Sorry for the bad english !
•  » » 4 years ago, # ^ |   0 What the complexity of your code?
•  » » 4 years ago, # ^ |   +3 I think it is supposed to use DP.
•  » » » 4 years ago, # ^ |   +3 My solution used an offline approach using segment tree with O(nlogn) complexity :) Don't know if it will be AC, but it passed pretest.
•  » » » » 4 years ago, # ^ |   +3 Mine is O(n^2) :) I think it will pass
•  » » » » » 4 years ago, # ^ |   +3 It won't get TLE that we can be sure (y)
 » 4 years ago, # | ← Rev. 2 →   0 This was the easiest div2 CF round I have ever participated in.
 » 4 years ago, # | ← Rev. 2 →   +2 The submission for questionB in div2 stuck in the queue for the last half an hour,Why couldn't you fix it?I was vey dissappointed. It still says the the code is in queue -_-
 » 4 years ago, # |   +36 Worst div2A I have ever seen -_-
•  » » 4 years ago, # ^ |   0 Definitely
•  » » 4 years ago, # ^ |   -8 Very, very true ! The story just didn't have anything to do with the other problems ! I think the writers focused on the harder problems because they knew that an Div. 2 A or B can be made in under a minute, so they didn't pay attention to make it good
 » 4 years ago, # |   +8 I think System testing will be over after 6 hours, any one thinks more??? let's see who can guess correctly :D
•  » » 4 years ago, # ^ |   +3 I'll bet for 3:15(UTC+8)
•  » » 4 years ago, # ^ |   0 It's still in queue. Guess Codeforces servers are working perfectly fine :-p
 » 4 years ago, # |   0 35 minute queue..... Do you want anymore??
 » 4 years ago, # |   +11 Please leave it rated, round was great!
 » 4 years ago, # |   +253 This is what happens when you forget to thank MikeMirzayanov
•  » » 4 years ago, # ^ | ← Rev. 11 →   +17 yeah,it's seems that there are always some incidents occur when setters forget to do that.
 » 4 years ago, # |   0 Is the pretest always contain tests with maximum test data?
•  » » 4 years ago, # ^ |   0 Usually
•  » » 4 years ago, # ^ |   +15 Yes or No, depends on the interest of writer.
 » 4 years ago, # |   0 For the last 15 minutes of the contest, I've waited for my verdict of D. But it's still in queue after half an hour of the contest. Even the hack page was not responding. And you're saying it's rated! Although, rating is not the purpose of the contest but making this contest rated is not fair.
•  » » 4 years ago, # ^ |   0 I also did not see the results of my submission + hacks did not work.
•  » » » 4 years ago, # ^ |   0 Same here :(
•  » » 4 years ago, # ^ |   +10 Many of us agree, but there are too many comments of the same thing on this page ! Stop it ! There should be only one comment of this posted and the rest of us just upvote it ! Are you just farming upvotes or what ?
 » 4 years ago, # | ← Rev. 2 →   +115 Real reason why round is rated: SpoilerSo tourist can become number one again
•  » » 4 years ago, # ^ |   +1 yeah,that's a interesting take.
 » 4 years ago, # |   0 In div2E/div1B (I will be getting WA but still in queue) why is this wrongFind min number of swaps required to sort the array. let it be x. then if 3*n — x is divisiblle by 2 then Petr else Um_nik.
•  » » 4 years ago, # ^ |   0 I've done the same thing, but got Pretest Passed.
•  » » » 4 years ago, # ^ |   0 I checked on some sample with OO0OOO00O0OOO0O00OOO0OO code and it gave wrong for meMaybe my implementation is wrong? I took the min swaps from geeks for geeks.
•  » » » » 4 years ago, # ^ |   0 I've done simply that iterated over 1 to n and put the ith number on ith index.Well also i guess for minimum swap u need to appy merge sort.
 » 4 years ago, # |   0 Can anyone explain Div2 D ...??
•  » » 4 years ago, # ^ |   0 For each type of product, do a bfs and find minimum distance between any node with type i and each other node Knowing costs for all the types, you can just sort each of the n arrays and take the smallest k values
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 Try to find the minimum distance between every node i and a specific kind of good j,let's make it mind[i][j].all you need to do is run BFS for every j and sort mind[i] out. (maybe some stupid grammar mistakes,forgive me for that,please.)
 » 4 years ago, # |   +2 Contest status queue is stuck again.
 » 4 years ago, # |   +34 Too long queue to keep it rated. Everyone who submitted between 1:30-1:55 has a very big disadvantage because they have to check their solutions otherwise they can fail at PRETESTS AFTER THE CONTEST. Who didn't submit this time of the contest just gained 10 extra minutes to solve 1 more problem. This is unfair. Make the contest unrated.
•  » » 4 years ago, # ^ |   0 Agree ! But there are too many comments of the same thing on this page ! Stop it ! There should be only one comment of this posted and the rest of us just upvote it ! Are you just farming upvotes or what ?
 » 4 years ago, # |   0 Can anyone give me hints or solution for Div2 D and E. The best I could think for Div 2D was brute and I'm clueless for Div2E
 » 4 years ago, # |   +14 Still my submission is in the queue and they want the contest to be rated.
•  » » 4 years ago, # ^ |   0 Mine too ! But there are too many comments of the same thing on this page ! Stop it ! There should be only one comment of this posted and the rest of us just upvote it ! Are you just farming upvotes or what ?
•  » » » 4 years ago, # ^ |   0 Now there are too many comments from you about the same thing on this page! /s
•  » » 4 years ago, # ^ |   +6 Same condition here .. 50 minutes still waiting for the submission to be evaluated
 » 4 years ago, # |   +97
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 It's "after the world closed to the end" :v
 » 4 years ago, # | ← Rev. 3 →   -20 emmm
•  » » 4 years ago, # ^ | ← Rev. 4 →   -24 ahh
 » 4 years ago, # |   +33 It seems round was unfair to java users..
 » 4 years ago, # |   +16 Did anyone else also find time-limit too strict for problem div2 D? got TLE with N*K*logK solution.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +3 Er,I think the best solution is O( K*(N+M)+ N*(KlogK)(that is for sort) ) by using BFS.
•  » » » 4 years ago, # ^ |   0 yes, I also had done the same. I had used heap(priority_queue) instead of sorting.But finally got accepted with (N+M)*K.
•  » » 4 years ago, # ^ |   0 Yeah happened to me . I would like to know if this is a problem specific to Java. I didn't use ArrayList for adjacency list , maybe PriorityQueue caused the issue. I think using just arrays everywhere instead of Collections could speed things up.
 » 4 years ago, # |   0 It passed 1h after the contest,but my solution for Problem E(Submit at 123min after the contest starts) is still in queue...
 » 4 years ago, # |   +15 Why does life have to suck so much? I got tle at problem E because of a stupid mistake i make,instead i have to wait till the end of the contest not know anything about my mistake. If the queue isn't retarded today i would have AC problem E. Thanks so much life.
•  » » 4 years ago, # ^ |   +2 And why is cf so laggy nowadays,after the contest i can't get into the website for 2 hours.Stupid.
 » 4 years ago, # |   0 Thanos's glove dissipated my rating.
•  » » 4 years ago, # ^ |   0 i have no idea why my code was showing wrong answer on pretest 1 even when locally the answer was right
 » 4 years ago, # | ← Rev. 2 →   0 sorry my good sir,i just wanted to point out that my C got MLE on test 1 that i couldn't fix because i got the verdict after the contest ended :) .AND NOW I AM TRIGGERED :) .
 » 4 years ago, # |   +75 spoilerconst string top3[]={"tourist", "MiracleFaFa", "Radewoosh"};
•  » » 4 years ago, # ^ |   +4 good job Radewoosh
•  » » 4 years ago, # ^ |   +124 no chance to beat Gennady:/
•  » » » 4 years ago, # ^ |   +44 I know your pain :/
•  » » » » 4 years ago, # ^ |   +45 I am trying to know your pain...
•  » » » 4 years ago, # ^ |   0 HI, I could help you :)
 » 4 years ago, # |   0 Div2E, is it enough to consider only num_components % 2? I submitted when the queue was too long, and can not see how result is.
 » 4 years ago, # |   +15 in div2E\div1B why was it given that permutation was random, or that n>1e3? it confused me so much :D
•  » » 4 years ago, # ^ |   0 So that you think twice before submitting. And It should look like it is div2E\div1B problem.
 » 4 years ago, # |   0 asymptotically my submission for problem Div2 D looks right can someone point out why I got TLE my submission
•  » » 4 years ago, # ^ |   +1 You did it in Java. There's your mistake. :^)I had a Java solution with an O(K*(N+M)+N*(KlogK)) running time that TLE'd. I'm wondering what the running time of the expected solution was.
•  » » » 4 yea