Intel Code Challenge Final Round will take place on Saturday, 8 October 15:05 MSK.

**All users of the Codeforces can participate in it as in an usual round. The round will be rated and both divisions can participate. Pay attention to the time of the beginning of the round.**

There will be 7 problems with statements in english and russian languages and 3 hours to solve them. Scoring distribution will be announced closer to the start of the round.

The problems were prepared by me — Vladislav Epifanov (vepifanov). I want to say thanks to Alexey Shmelev (ashmelev), Alexander Fetisov (AlexFetisov) and Vladislav Isenbaev (winger) for testing the problems, coordinator of the Codeforces Gleb Evstropov (GlebsHP) for his help with the contest preparation, and Mike Mirzayanov (MikeMirzayanov) for the Codeforces and Polygon systems.

**UPD.** Scoring distribution: 500-1000-1500-1500-2500-2500-2500. Since the round will be 3 hours long, the number of points for each task will decrease slower than in usual round.

**UPD. 2** Due to some issues on one of sites for official participation in Intel Code Challenge we shifted the beginning of the round for 10 minutes. Sorry for the inconvenience.

**UPD. 3**

Final rating changes will be available after removing unfair participants.

Editorial will be published on Sunday, 9 October.

**UPD. 6**

Photos from the onsite event. ### Nizhny Novgorod

### Arkhanglesk

### Volgograd

### Kazan

### Moscow

### Saint Petersburg

Hope better English statements:D

Hope I can keep my purple!Thanks!

I wish for you !

Thank you for you wish.

I get it.

Hope better English comments

how can (all users of the codeforces) participate in round (with div_1 and div_2 participants and 7 problems and unusual time of the beginning) as in an usual round?

please provide better problem statement in english.

Hope the scoring distribution can be announced a little earlier。:D

Will the problems be harder than the problems from the intel elimination round ?

Problemset is designed to satisfy participants of all skill levels.

i have a doubt ... As div1 contestants are participating along with div2 contestants...will this affect ratings for ppl in div2 differently as compared to when div1 ppl participate out of the competition ... Thanks in advance :) :) :)

you can make virtual participation later. the problemset is good for all contestants so every one would compite in this kind of rounds , do not worry about rating just enjoy and Good luck for all .. sorry for bad english !

I m participating but just wanted to know about rating system...

Don't worry man Everybody will satisfied after the contest.. you will get what you deserve. I think it will be better of solving problem rather than thinking about rating changing process :)

Why does every comment in the form "Hope [noun/pronoun] verb ..." get downvoted? I don't understand...

Does anyone ever understand the reason for downvotes on codeforces?

Red coders get Upvote By the way

Hope this comment won't get downvoted :)

Red Coder _ / \ _. Comment upvoted without even reading

The "Red coders get Upvote" theory has been proven.

Good luck for all (:

Hope to become cyan finally, I need +22

good luck and have a good contest ...

hoping same just need +31

Advice from little bro- Try solving from reverse. like , if you solve a,b,c thn solve today c,b,a :D

Timings are getting bad for me. Will we have a contest on

usualtime any day soon?Will the problems be significantly harder than the first round??

I think not so.

And you were wrong. :P

Awesome problemset!

I can't solve problem C during the contest and I got the idea 10 hours later after referring to JIBANCANYANG's code ;)

Very interesting problems though.

A simple but good idea.

hope same kind of problem but of course with better statement.last round was awesome with the problem statement.....__This is my last codeforces round before flying to Dalian,wish to learn new skills!Thank you,vepifanov!

It is my last round before going to Hangzhou and Shenyang.

Good luck to all and thanks vepifanov for this contest !!

In combine competition the div2 contestant participate a lower one. only div2 rated contest participate >=5000. But div1+div2<5000 and participate of div1 is high. so if distribution rating are seperate div1 and div2 contestant will be increase div2 but decrease div1.

wish to see a programming contest not a hack contest and better English statements

GOOD LUCK FOR ALL :D

dude you don't have to comment the same phrase each contest xD

Contest start delayed?

(score[2] == score[3]) && (score[4] == score[5]) && (score[5] == score[6])? This is a strange distribution......

(score[2] != score[3])

It's 0-indexed.

delay 10 minutes

Why Delayed -.-

Is the contest delayed because they want more participation ( 6k+ ) or because of some technical problem ?

Neither I think.

We are waiting for the onsite participants to be ready to start.

Ohh.. cool. I didn't thought of that.

This is my first contest. Feeling scared and excited at the same time !

after a while it will be boring to wait until the contest starts! :/

Why I can't unregister? :/

Your rating will not change if you don't send any solution

No need to.

just don't submit anything during the contest and you will be fine.

If you don't submit a solution during the contest your rating won't get affected, so there's no need to unregister.

I hope I can Change to Blue

Strange Scoring distribution: 500-1000-**1500-1500**-_2500-2500_-2500.

Gl hf

My submission for D has been running pretest 10 for close to 10 minutes now with no final verdict. Can anyone help me out?

Never mind, this just resolved.

After a long time, I loved a contest on Codeforces. Nothing could have been better about the contest except my performance. Thanks a lot vepifanov.

How to solve 2A?

Edit: Nevermind, my solution passed.

This was a very difficult contest for us DIV-2'ers :|

how to solve C? I tried a approach like making a equation with 2 variables but didnt have enough to solve it

How to solve G? I thought of bicconected components with Gauss elimination but could not work out the whole solution.

Hint: If you can solve the problem on tree, edges that create a cycle with that tree can be processed separately (they affect every path the same way)

What are the hacks for A and B?

B

3 3

3 2 1

2 3 1

1 3 2

what is the expected output for this?

NO(My sol passed systets)

I hacked B with

2 4

4 3 2 1

4 3 2 1

Div2C I forgot to use long long and spent 40min debugging...

"long long case" was included in pretests for C?

I failed on case #10, and got AC after using long long

http://codeforces.com/contest/724/submission/21292757 Can anyone tell me what optimisation I could've done so I wouldn't get TLE for C?

Not increment or decrement x and y by 1 or -1, but by more at once. For example, always increment it enough to make x == n || x == 0 || y == m || y == 0, which is not that hard to do.

Then how do you increase count of all the sensors that come in the path on one increment?

I stored a map from the endpoints of a diagonal to a vector of the sensors on it.

could you please explain a bit more in detail i didn't get your idea.

It's not hard to calculate for any point in which primary and secondary diagonal it's located, and what the endpoints of those diagonals are. It's also simple to calculate the time needed to get from an endpoint to any point on the diagonal. You store the index of the sensor along with its distance in the map entry for that diagonal, in both directions since the distance is different. Then you track the movement of the laser from one edge to the other and each time process all the lasers in your path, clear the list of sensors and increase the time elapsed. If you don't understand, you can take a look at my code.

Just realized that

nandmin problem C is only upto 10^{5}my overkill problem C solution using successive_substitution, theoritically (if free of bug) can solve for

nandmupto 2×10^{9}.My solution's complexity is O(k) and it's 25 lines long. Is there a shorter slower solution that works?

Actually, O(k+h)

Can you give me some hint about your solution?I get tle.

Instead having a room, I assumed the laser continues forever. Than, for each sensor there are positions that if the beam reached them it would have reached the sensor position if there were walls.

There is some solution with complexity O(k+n+m) and IMHO the code is a bit longer, but faster to code.

Tried this and got TLE (in python though). How do you check what the input when it's so long they put "..."?

No, i can't. If the input is not too long but get trimmed "..." you can see it with simple program: print the input at position a to b, and b-a<512 bytes.

btw, python is slow language, you might consider to move on to C/C++?

I should move on, but I really thought python would be able to handle O(k+n+m). Tried what I thought was a similar input (also n,m,k = 100000,99999, 100000) before submitting and it was ~1 second which is why I am curious to try their exact case on my computer.

saturday

can some one explain how to solve B . my approach was to count how many operation i can do in optimal way to get the 2D array sorted ..so i was thinking in that i tried a lot test cases and i couldn't figure how to determine the optimal number of operations and check if this number is <=n+1 ..my problem was how to use columns to make optimal number of swaps ? could somw one help ?

I did it this way

first see if the array can be sorted without changing in rows -> (change in each line==0||change in each line==2)

then, change each rows with n^2 and check all the same way

this way O(n^3) but n is only up to 20 xd

OK , so we go.At first you must see that row may be already sorted , it needs one swap , two or more. 1)If some row needs more than two swap , answer is NO as with this operations we can get at max two swaps in one row . 2) if in none of these rows need more than one swap , answer is of course YES , because we don't need to use "column swap" at all .3) We have some rows than need two swap , so it have 3 numbers not in correct place , than we don't need to do about sorted rows , also we don't need to do anything about "one-swap" rows before "column swap" because. and so we have to consider only two-swap rows . It's not hard to see that all different positions for two-swap rows must be at max 4 . and it's the case , than we check all column swap , at most 6 =) hope it helps ! Feel free to ask.

Bounds are small to try all O(M^2) possible column swaps. I think it's better than considering all these cases, the more complex your code is the higher the chance of making a bug.

Problem E. Goods transportation — Why is this O(n*n) approach incorrect?

0.1. i goes from n-1 to 0:

1.1. trans = min(prods[i], sells[i]); // Sell as much as possible at the current i-th city.

ans += trans; sells[i] -= trans;

1.2. j goes from i-1 down to 0:

trans = min(sells[i], c, prods[j]); // Transfer as much as possible from the j-th city.

ans += trans; prods[j] -= trans; sells[i] -= trans;

1.3. Output the ans.

I think you need to transfer in such a way that the largest amount of excess goods is minimized. Consider the case where each town can sell 100 goods. Then for case: 150 150 0 with maximum transfer between any 2 towns=50

You cannot transfer from town 0 to town 1 before transferring it to town 2.

Dear meeeep,

Edit: In your example, 50 goods are transferred from cities 0 and 1 to 2. Then there will be 100 goods in each city — my code covers this sample case.

But I have made an example, which will break my code:

Here, 3 goods will be transferred to 2-nd city: 2 from 0-th, and 1 from 1-st.

A better way is to move 1 unit of good from 0-th to 1-st city, and then move 2 goods from cities 0 and 1 to city 2, that is 4 goods in total.

I supposed that there should be only direct transfers, that the same goods couldn't be transferred from city 1 to city 3 via city 2.

Hope to read the description more thoroughly and do better next time.

Good thing that pretest were strong this time. Made me realize my mistake!

So fast system testing

At least I got the taste of being yellow (orange) for a while! :(

wow!! master

i cant get out of green island xd

Candidate master now :D

Don't worry, you will get through it if you keep practicing. At this time last year I was cyan for a while (but actually my level was around 1700-1800, I believe) so good luck! :)

AC D at 2:52,got 600 pts,:D FST B,lose 900 pts,:( gg my friend,return to div.2

Congratulations!! You are still in Div 1!

Is the same seed random different number in different machine ? Because i used this code to generate hack case and it output differently in cf and local. I tried to run it in ideone and it gives the same as local and different in cf.

(http://codeforces.com/contest/724/hacks/261983/test)

(http://ideone.com/siTEFD)

I check my program again and again,but I don't realize that I have edit my header code before somt time ago,when I write another problem...

hmmm , I afraid of that and always I change name of define after changing it's definition. because it's the last thing that we notice it ...

sry for necro-posting but how is this editor/IDE called. Ty in advance

Sublime Text3

For 2B why wouldn't switching a pair of columns in every possible way and then checking if for each way if it is possible to get a valid solution by making at most 1 swap for each row work?

http://codeforces.com/contest/724/submission/21298730

The idea is correct, the implementation is wrong.

.

lol

Who can help me find why I got WrongAnswer with this code(http://codeforces.com/contest/724/submission/21298755)...

I got the correct answer on my computer but wrong answer on codeforces...

(Maybe I don't know something about codeforces? :D)

is there any place to make a bug report?

Same happened to me (OSX 10.12. Firefox and Chrome)

Yeah...I just want to know why. I got the correct answer on Windows10 and Windows8 .But wrong on codeforces...

You have already reported it :D

I didn't understand.Can you tell me in detail?Thank U very much...

it seems the variable k in solve() will be -1 in that case

OMG,I made a very stupid mistake...Thank U very much...

You would have been better more cautious... :)

Deleted

How to solve D? and How to solve C using CRT ?

Well, I don't know about CRT, but if you are looking for a solution based on Number Theory then you can check out mine 21299508

The 4 linear diophantine equations represent the four types of points you get when you expand your rectangle to account for reflections (see this problem's discussion in the blog for further explanation 241C - Mirror Box, it redirects you to this: Codejam problem), and you need the minimum solutions with both x and y positive to find the closest of the points of that type having x == y.

I failed during contest to solve those diophantine equations properly (a, b negative and getting the min x), do you know any other problem where I confirm if now I know how to manage such tricky requirements?? Notice I don't want to practice finding the equations, I just want to test my solver, although the problem being nice/hard is always a plus.

Reflect the box over the top and right sides, with the bottom left corner at (0, 0). So in the 3rd sample, all the boxes have left corners (7

x, 4y). Note that the path of the ball is then equivalent toy=x. We can find the stopping point, which is the top right corner of some box, in the form (mk,nl) for some (k, l). It's also on the path, somk=nl, and the first hit is at (lcm(m,n),lcm(m,n)).With some experimentation, you can see that for some point (

x,y), it's also equal to all the points ( ±x+ 2nk, ±y+ 2ml) for some (k, l). (In each box, there's 1 point). And because it's onx=y, we can use the 4 congruencesWe find the minimum such a, and check if it's ≤

lcm(m,n).Any ideas on how to solve D?

Notice that if the greatest letter used is P, then all occurrences of letters 'a', 'b', ..., P-1 and some (possibly all) occurrences of P will be used in the answer. We can find P easily in O(N*ALPHABET_SIZE). Let's insert the positions of letters 'a', 'b', ..., P-1 into a set and then loop over all intervals ([1,M], [2,M+1], ..., [N-M+1,N]). If the current interval [L,R] has no 'a', 'b', ..., or P-1, then we should choose some of the occurrences of P in this interval [L,R] and insert it into the answer. It's easy to see and prove that it's always optimal to take the rightmost one. Everything I explained can be done

~~with set~~linearly, don't look at my code, please! PLEASE!Consider the sorted version of the input string. The most crucial observation is that the best answer must be a prefix of this string.

Let's binary search the length of the answer, the only problem is how to check it fast. An useful insight is that any prefix contains every positions of the same character, except one. So the problem reduce to this: Given the picked positions, select some more positions in order to fulfill the requirement, this can be done greedily in O(N).

First notice that if you where to take only the smallest letter, then the solution is the least number of positions with that letter on the string fulfilling the "every m..." condition.

To solve that problem a simple greedy works: go from left to right only taking a position if you passed over m positions without taking any, and take the last you have seen (remember this is only considering the smallest letter ie. 'a' if it existed), if there is no last seen position closer than m to current position then we can't solve it using the lowest letter only.

Now back to the full problem is easy to prove that if we are using >= 2 types of letters is optimum to take all the positions of all but the greatest of the types of letters. Because inserting them before the greatest character makes the solution string smaller.

Full solution is iterate over the greater character c to use and then perform the greedy described but taking all positions of the characters smaller than c.

Link to my solution: 21281704

your comment is the best SandorGarcia

Thanks, just trying to help.

I think your solution is the best.

I solve D with the 2- pointers technique. Fix the m first "window" ( interval from 0 to m-1). It must be covered by any of this characters. Then, we get the most right and most lexicographically smaller character (on position x). When we get this, we repeat the same problem in the (x+1,r+m-1) window. To do this we keep a structure pont[i] that keep the most right position of character i and update this with 2 pointers. After do that we have to add to the solution all character which is lexicographically smaller than your "bigger character". Sorry for my bad english ;/ My solution: 21297160

Unable to find the error. Please help. Got WA test 28.

Code is readable I think.

http://codeforces.com/contest/724/submission/21290857

consider this test:

Answer :

`aa`

in line 65 you 'erase' too many positions, and besides you cannot guarantee last will become 0 neither (line 67).

In the example huansuz1 provided you find a problem in position 1 (the one with the b) and it can be fixed, but last would become 1 not 0, and you cannot 'erase' the position 2.

fixed solution: 21301915

Spent the whole time trying to figure out an efficient solution to problem B :/ Didn't see n, m, were only 20 and could be solved by brute-force. Read TooDifficult's solution and it is what O(nm^3)?!!

Anyways, any tips/hints for an optimal solution that can solve for large values of n. What I thought was to make a list of potential swap-able columns depending on number of unordered elements in rows (3, 4) and then eliminating them.

My solution is m*n Find all the possible pairs to swap Max 4 elements can be in wrong place For 4 elements in wrong place, there should be only 2 pairs For 3 elements in wrong place there will be 3 pairs For 2 elements in wrong place 1 pair I made all these possible pairs and at last checked if every row gas some common pair then ans is yes else no This solution is of course an overkill. I wrongly computed brute force so wrote this solution

Any ideas on how to solve E?

We can model that problem as network flow as follows : create a source node (let's call it 0) and sink node (let's call it n + 1). Then we are asked to find maximum flow in network with edges

`0 -> i, cap = p_i`

for 1 ≤i≤n,`i -> n + 1, cap = s_i`

for 1 ≤i≤nand`i -> j, cap = c`

for 1 ≤i<j≤n(you can't get more than that because of the way network is constructed, you can get exactly this value, because this graph is DAG and you can always push flow in order of topological sorting). We could use any algorithm to find maximum flow, but this graph hasO(n^{2}) edges and they will all TLE probably.But maximum flow is equal by value to minimum cut, which we can actually find in

O(n^{2}) time andO(n) memory. Every cut in this network can be expressed as , . Now we can find value of`dp[l][k]`

— minimum total sum of already cut edges if we have taken exactlykvertices intoSfrom vertices 1, ...,l. Then it can be recalculated as follows:`dp[0][0] = 0, dp[0][i] = inf if i > 0`

,`dp[l][k + 1] = min(dp[l][k + 1], dp[l - 1][k] + s_l`

,`dp[l][k] = min(dp[l][k], dp[l - 1][k] + p_l + ck`

(in first case only one edge is cut and this is edge fromlto sink, in second case edge`0 -> l`

is cut and so are edges`i -> l`

for . Of course, we need to keep only last two layers of this dp. Answer is`min(dp[n][0], dp[n][1], ..., dp[n][n])`

.Good solution! I modeled the problem as maximum flow correctly in the contest, but I just forgot about the minimum cut. The problem is very nice!

The same code submitted from different c++ versions gives different verdict

http://codeforces.com/contest/724/submission/21301362

http://codeforces.com/contest/724/submission/21299482 . any guesses why?

You have a bug in function

`next_point`

.`y2`

does not initialize. Likely you confused`y1`

to`y2`

.P.S. Sorry for the bad English skills

Thanks :) !!

why is a page like http://codeforces.com/ratings still blocked so long after the contest is over?

Its working now!

MY color changed

And then u cheated and you are back.

Ratings have been updated but the user rating graph is not updated.

And now the ratings have been reverted back too. Whats happening?

Don't worry, I'm sure they'll update them back. They've probably finished with the cheating testing. The ladder changed a bit, so our ratings will too.

Yes! I guess they are re-calculating the ratings after removal of unfair participants.

Back to normal now. :)

After given rating why unrated me. http://codeforces.com/profile/Alhelal_WA Please check..............................

cuz you must have cheated lol

Because

bruh y u not sweg lyk me

Editorial delay again

Quite a long time for the next round :D

Any ideas on how to solve F and G? thx!

Can someone explain the logic behind problem C. What I could think of is mapping the room in both directions till it becomes a square of lcm(a,b)*lcm(a,b) and then map the corresponding points and check if it lies on the line y=x. Thanks in advance.

consider bound as mirror

then every action can be performed on another side.

therefore, all points' coordinates are (x,x) (x )

Thanks for the explanation. I had figured out this but couldn't find a method to solve for the time. Can you brief me on it.

I can suggest you to draw an image and select one random point (sensor), which you will reflect after each passing through border. Then you will see that point with coordinates (x,y) reflects to (x, 2*m-y) or (2*n-x, y).

After some experiments you can notice that going through sensor equals to going through any of points like

AND points like mentioned above, but with +k*2*n to first coordinate, or +l*2*m to second coordinate.

It looks like this:

In other words, you should find a first point (x',y') such that

Consider all four combinations and solve an obtained system of equations. I can suggest my code for reference, but I think it's not clear and mostly devoted to solving of Diophant equation: http://codeforces.com/contest/724/submission/21292371 All I said you can see in these lines:

How to solve G ????

roses r red violets r blue codeforces is unusual just like u

Can problem D be done using this approach: starting from index 1, for each window of length 'm', we find the smallest character and add it to the answer. For checking the smallest character, set can be used with the element stored being (character,index). As we move the window, we remove the first element of the previous window and insert the new element of current window, then check if the new smallest character is the same as previous. If it is not, we can add it to our answer. Let the answer be 'ANS'.

At the end, we can iterate through the string and for each character that is not added in the answer, check whether it is less than the largest character that exists in 'ANS'. If yes, we can add it to answer and continue.

Hi, Can anyone explain why test case 49 for Div2. Batch Sort Problem is "YES". 3 3 1 2 3 3 1 2 1 3 2

According to my code, I'm getting it as "NO". Is there a way we can get the required 1 2 3 permutation in every row.

Please help...

Make 1 3 2 in every row and swap columns.

Hope better English statements,I also hope that my Rating can rise as well.

BTW, there was very similar to 724F - Uniformly Branched Trees problem in Gym: 100125C - Chemistry. Solutions for both problems differ in one small if-clause (ignoring modular arithmetic functions). See difference: 21344515 and http://pastebin.com/Gp0RKzmG

Could anyone tell me the reason that greedy is wrong in problem E ? Thanks ~:)

Nice photos and Nice contest.