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. jqdai0815

3. Radewoosh

4. webmaster

5. LHiC

div.2 winners:

1. sminem

2. Fortza_Gabi_Tulba

3. cheburazshka

4. Lomk

5. 2ez4me

Editorial is up.

Good fun, have problems, read all the luck. As usual. Love how the words were jumbled and at last as usual :P.

Meow ! :)

bow wow XD

And also thanks to MikeMirzayanov for systems Codeforces and Polygon:)

SpoilerBot test comment .

Spoilermeooow hello.

SpoilerDont forget to add me in contributors.md

KAN is my favorite

If KAN didn't invent easy tasks, we would have div 1 only round :D

No, you would have bad div.2 round :)

B and C in div2 have the same score ,Will they have the same difficulty ?

SpoilerSpoilerSpoileryes

too many spoilers

SpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerSpoilerI don't think so.

For those wondering, there are 31 spoilers.

I counted 32...

Spoiler limit exceeded

thanks

it is 32

Huseyn_Hajiyev You really spoiled the thing.

Good Question. And nice observation.

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

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

GOOOOD LUCKK 4 EVERYONE :з

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)

*in infinitive

Nice catch. Thanks. Fixed.

discuss not discusse :)

Ok then, you should say "If there

areno bad things, round will be rated", cause it's first conditional.2 of div.2 problems created by KAN, 7 others created by meshould be

2 of div.2 problems were created by KAN, 7 others were created by mesuccessful hacking attempt +100

My comments will have more downvotes than upvotes on this post. Do Down Vote.

Two hours and we have problems worth 1750, 2500, 2750 and 3000. Is that best choice of duration?

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 :)

That's the answer I wanted to hear (y)

I think you read it :)

but he wanted to hear

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

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?

I just wrote my opinion:

I thinkyou read it :)I'm just writing my opinion: I think you should shut the fuck up.

KAN gives t-shirt winner in the contests.

So rating 1953 will be rated in division 2?

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 —

onlyrounds (today's round is Div1 + Div2 so they are rated in Div-1).I hope there are no problems from Graph Theory.

Really??? I hope all problems will be related to Graphs. They are great!

Indeed , I love Graphs !

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 !

Oh, and kb. for writing great legend for one of the problemsHope that's the only problem with legend :(

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

Nice statement.

Where can I see problems of past HSE editions?

HSE is the university I attend. I made a championship for its students. As far as I know that was the first one.

Happy to see you in the list of top contributors.

I hope tourist will regain His position after this contest

I also feel so.

Petr rlz!

hacks window not opening. -_-

terrible queue :(

20 pages of queue...

30 now ... :(

50 now

What happened?

smells like unrated round :'(

That's terrible!

queue:(

Extend the contest.

So Long Queue I guess Codeforces need to work on that, so that it occurs less often... Please See to that Admin.

queue is gone

in div1 still 5+ pages

After waiting 10 minutes for my solution to be judged I found out, I printed "um_nik" instead of "Um_nik".

And I declared array of size of 10^5 !!!

Submissions in queue!

Oh, and if there will be no bad things, round will be rated. I hope.Yeah, you jinxed it right then...

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

After waiting for 20 minutes my solution starts being judged, passes 9 pretests, and then...Voila!!! It's "in queue" again!!! WTF is that???

So, we have to wait more than 20 minutes for verdict, but time is extended only 10 minute. Is it fair?

Codeforces is crashed again and again and again. In queue ........ (20+ minutes later) Compile Error (because of different version of C++)

Another semi-rated round? lol

is it rated?

It should not be rated as many submissions(more than 40 pages) remained in queue even at the end of the contest.

after a long time i see a comment "is it rated?" and that have upvotes (Wow)! :D

Nothing personal, but round must be unrated

Submissions after 1:30 was in queue even after a long time after contest’s end

Longest queue ever -_-

I beleive u r new to cf

I beleive u r new to cf

I believe you have poor internet connection.

No, but my laptop is lagging too much today.

The most stupid thing ever:

Ouputted "Alex" instead of "Um_nik".

Aaaaah, so this is why I got WA #3. Shit :D

How to solve E?

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)

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

The round was really good until Problem E appeared, it is bad problem and made the queue completely full

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 :'(

seems unrated to me :(

CF don't feels so good

how to solve Div2-D?

A multisource BFS will do the job.

can you please explain it a little more?

Just push every starting vertex into queue, and do normal bfs.

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.

I am unable figure out the intuition behind it. If u don't mind can you please elaborate? thanks !

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.

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 ;)

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.Note that

kis at most 100. Therefore, we can try the following:Denote

dist[i][j] as the minimum cost of townito get a goodjfrom any town.For each type of good

i, push allxsuch thata_{x}=iinto a queue, and setdist[x][i] = 0. Then, we do normal BFS to update thedistarray. This hasO((n+m)k) time complexity.Then we find the sum of

ssmallest elements indist[i] for eachifrom 1 ton, which can be done by sorting.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...

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...

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

I think 'Collections.sort' is too slow to pass tests with big constraints.

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?

You are sorting the costs. -> therefore you have an additional log factor.

How do we get the k smallest without sorting the costs?

The selection algorithm does it in linear time.

Thanks! Even partial_sort is good!

Was it slow or my internet connection became slow at the last few minutes??? :o

BTW. How to solve problem C?

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]<s[i] and k<i. Now my dp[i][1] tells me the minimum cost in which i can select three displays such that the condition is satisfied therefore dp[i][1]=min(dp[k][0]+cost[i]) for all k<i such that s[k]<s[i]. Hope that it helped a bit :)

CF was slow for me also! C can be done by Dynamic Programming.

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.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.

is it rated?

Make it unrated .

"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?

Woah! Hey, Nobody mentioned that ranklist will be frozen during the last hour. Was away from cf for sometime, when did they introduce that?

My question is still in queue!??

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)?

I don't know about O(n) but u can do O(nlogn) using Segtree

Sorry edited my comment. O(n) might be impossible. How to do it in nlgn using segment tree?

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 > k

Make 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

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?

You can use Fenwick tree with minimums

54 pages of queue right now. Make it Unrated please.

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

Nisn'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.

Fast exponential + FFT for multiplication seem reasonable.

So that's plus the not-very-great constant factor of FFT? Note that I wrote "with these constraints".

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.

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.

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...

I tried submitting in the last 20 minutes . but it only showed queued . Make the contest unrated. Its not fair .

I cannot understand the statement in Div1D.. :(

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.

It might be better give an example as usual in other problem. I really confused what ID refers *_*

How to solve Div2-F or div1-C?

Still queuing the contest should be unrated.

I feel stupid... for not solving B. Don't think I even have a valid clue -___-

D is easy to reduce to calculate

ceil(log_{3}(10^{1.5e6})). Is it well-known?Round is still rated? That's unfair. 30+ minutes queue at the end.

Atleast make it "semi-rated".

yep, yep, you are right it must be

FunRatedAnd people started to think it "unrated". Then came the announcement! ;)

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...

Me trying to understand this comment

Some nutella things

i hope to live enough to discuss a problem with them

We all hope :(

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.

if i never solved the problem, this can't happen to me

Maybe I just hate you guys :)

I hope that it didn't ruin the contest for you (maybe some other things did haha).

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.

Thanks :)

I agree that D is not very fresh, but bigints also require some small ideas (but yeah, more implementation).

So you wrote this comment not to let Radewoosh write it?

Is it correct for E?

n = 2 2 1 ans should be "Um_nik"

N can be 1000 at least

Key to solve this problem:

Parity of a permutation

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?I think your method is correct (Since only the number of swap matter).

http://codeforces.com/contest/987/submission/38747479 Can you tell me whats wrong with this solution ??

The problem was with indexing of arrays :( :(

So if (3*n-x) is even then answer is Petr else Um_nik. Is it?

xuanquang1999, dheeraj_1997 Can you please explain me how did you reduce the problem to finding Parity of Permuation?

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.

I didn't get this. Can u please explain me how parity for Petr and Um_nik are different, with an example?

Assume that

n= 2k+r(kis integer,ris 0 or 1).Then the parity for Um_nik minus parity for Petr is:

(7

n+ 1) - 3n= 4

n+ 1= 4(2

k+r) + 1= 8

k+ 4r+ 1which is always an odd number.

Very end of the contest?:| Really?

Cool trick bro!

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.

I had to change my graph representation from List<Integer>[] 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.

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.

Despite the issues during the round, i enjoyed the problemset a lot. Thank you guys!

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).

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

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 CLOSEto the ending of a 2-hour contest. Nice!!! Really nice!!!Can Div 2 C be done better than O(n^2) ?

You can optimize it with Segment Tree or Fenwick Tree, but O(N^2) is enough.

O(N log n) using the segment tree and compression

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.

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.

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 ?

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

How to solve E?

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)

How to solve C? My brain kinda stopped working after spending nearly entire contest thinking about it.

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 :)

I think that number of edges is still too big.

Yes, but in the end you go through only O(2^N) states, if you remember the ones you already visited.

We dont need to use DFS or BFS on graph to count answer. Just using DSU and DFS on the mask is fine.

If the number of edges is big, DSU or DFS is still too much.

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.

I think we can improve it by dividing the vertices in a similar manner to SOS DP

I even cannot submit ( no respond when clicking on the submit button, refreshed a number of times ) during the last minute......

Hi, we apologize for the queue. We discussed the situation with Um_nik and decided to make the round rated because

Thanks Um_nik for great problems and thank you all for participation!

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.

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.

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?

There are also cases when someone got compilation error and learnt about it long after contest's end xD

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.

1) Больше 40 (!!!!!!!) минут не было вердиктов по сабмитам. На кф теперь такие правила? Почему не предупредили перед началом контеста?

2) Может тогда время от времени рандомно давать +-100 к рейтингу каждому, ведь "есть много раундов и рейтинг постоянно меняется"?

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.

so

30 minute of queue and system down are not considered as bad things.

nice to know it

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.

"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 LOLAgreed. I can't believe that I heard this from a large coordinator on Codeforces.

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.

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 :(

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.

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·2

^{22}> 256·1024^{2}. 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.

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.

"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.

দ্য হেক!!!!!! কন্টেস্ট রেটেড!!!!???????

আপনাদের কি রোজায় ধরসে?

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??

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.

Surely, we will. This is like this on Topcoder in every contest.

I'd be fine with round being rated if you hadn't announced that long queue will be resolved shortly tbh.

Very last period= 1:30+ I think it should be unrated becasue the influence is really big

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.

Anyone solve C div2 using DP?

Is there any other way of solving it ?

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.

There are two ways: Brute Force + RMQ (DP) or DP (LIS variation).

Brute Force preprocess for each position

ithe minimum cost of anyj>isuch thata_{i}<a_{j}and fix i and j in a double for to get something like this:DP uses a LIS variation such that

`memo[i][k]`

has the value of the minimum cost of using a valid sequence of lengthkending in the positioni:Finally, get the minimum valid value from each memo[i][3].

Both complexities are

O(n^{2}).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 !

What the complexity of your code?

I think it is supposed to use DP.

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.

Mine is O(n^2) :) I think it will pass

It won't get TLE that we can be sure (y)

This was the easiest div2 CF round I have ever participated in.

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 -_-

Worst div2A I have ever seen -_-

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

I think System testing will be over after 6 hours, any one thinks more??? let's see who can guess correctly :D

I'll bet for 3:15(UTC+8)

It's still in queue. Guess Codeforces servers are working perfectly fine :-p

35 minute queue..... Do you want anymore??

Please leave it rated, round was great!

This is what happens when you forget to thank MikeMirzayanov

yeah,it's seems that there are always some incidents occur when setters forget to do that.

Is the pretest always contain tests with maximum test data?

Usually

Yes or No, depends on the interest of writer.

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.

I also did not see the results of my submission + hacks did not work.

Same here :(

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 ?

Real reason why round is rated:

SpoilerSo tourist can become number one again

yeah,that's a interesting take.

In div2E/div1B (I will be getting WA but still in queue) why is this wrong

Find 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.

I've done the same thing, but got Pretest Passed.

I checked on some sample with OO0OOO00O0OOO0O00OOO0OO code and it gave wrong for me

Maybe my implementation is wrong? I took the min swaps from geeks for geeks.

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.

Can anyone explain Div2 D ...??

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

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.)

Contest

`status`

queue is stuck again.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.

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 ?

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

Still my submission is in the queue and they want the contest to be rated.

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 ?

Same condition here .. 50 minutes still waiting for the submission to be evaluated

It's "after the world closed to the end" :v

emmm

ahh

It seems round was unfair to java users..

Did anyone else also find time-limit too strict for problem div2 D? got TLE with N*K*logK solution.

Er,I think the best solution is O( K*(N+M)+ N*(KlogK)(that is for sort) ) by using BFS.

yes, I also had done the same. I had used heap(priority_queue) instead of sorting.

But finally got accepted with (N+M)*K.

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.It passed 1h after the contest,but my solution for Problem E(Submit at 123min after the contest starts) is still in queue...

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.

And why is cf so laggy nowadays,after the contest i can't get into the website for 2 hours.Stupid.

Thanos's glove dissipated my rating.

i have no idea why my code was showing wrong answer on pretest 1 even when locally the answer was right

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 :) .

spoilerconst string top3[]={"tourist", "jqdai0815", "Radewoosh"};

good job

Radewooshno chance to beat Gennady:/

I know your pain :/

I am trying to know your pain...

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.

in div2E\div1B why was it given that permutation was random, or that n>1e3? it confused me so much :D

So that you think twice before submitting. And It should look like it is div2E\div1B problem.

asymptotically my submission for problem

Div2 Dlooks right can someone point out why I gotTLEmy submissionYou 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.

can you please tell why I am getting TLE my code complexity is O(k*(n+m))

One asymptotic issue I see is that you're sorting each city.cost, which bumps up the complexity from O(nk) to O(nk log k).

A linear-time selection algorithm like C++'s nth_element keeps the complexity at O(nk).

FML, seriously (ignore D, I'll be ranting about E)

Once I saw MLE I got rid of #define int long long and changed a few "int" to "LL" and submitted. After 15 minutes I saw that I got compilation error,

facepalm(because I didn't have macro #define LL long long). I typed "make E" and saw that it doesn't compile locally, so I quickly added "#define int LL" instead of #define LL long long" and submitted once again, not compiling locally again and you can see the result. I learnt that I got second CE a few minutes ago. .#profitsoflongqueue #plsunratedI'll just leave this here 38749776

Not related: You got the coolest template ever!

Yeah, I just got AC by resubmitting my code with correct macro xD. And this is going to be rated. Ridiculous.

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

well predicted Um_nik .