### vepifanov's blog

By vepifanov, 22 months ago, translation, ,

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.

Editorial

UPD. 6

Photos from the onsite event. ### Nizhny Novgorod

### Saint Petersburg

#### Winner of the Intel Code Challenge — Evgeny Kapun (eatmore)

•
• +316
•

 » 22 months ago, # |   +98 Hope better English statements:D
•  » » 22 months ago, # ^ |   +29 Hope I can keep my purple!Thanks!
•  » » » 22 months ago, # ^ |   +18 I wish for you !
•  » » » » 22 months ago, # ^ |   +3 Thank you for you wish.
•  » » » 22 months ago, # ^ |   +10 I get it.
•  » » » » 22 months ago, # ^ |   -21 NO... wrong English... say... "I did it"... By the way congratulations
•  » » » » » 22 months ago, # ^ |   0 wow
•  » » 22 months ago, # ^ |   +89 Hope better English comments
•  » » » 22 months ago, # ^ |   -21 her English comment is not correct . But everyone has understood her expression . I will not downvote her for her bad english .
•  » » 22 months ago, # ^ |   0 yeah not like the last round please!!
 » 22 months ago, # | ← Rev. 6 →   -45 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?
 » 22 months ago, # |   +35 please provide better problem statement in english.
 » 22 months ago, # | ← Rev. 2 →   -10 Hope the scoring distribution can be announced a little earlier。:D
 » 22 months ago, # |   +83 Will the problems be harder than the problems from the intel elimination round ?
•  » » 22 months ago, # ^ |   +157 Problemset is designed to satisfy participants of all skill levels.
 » 22 months ago, # |   -16 Hope I solved the problem better!
 » 22 months ago, # |   0 Hope it will be an awesome contest with some awesome problems.
 » 22 months ago, # |   +3 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 :) :) :)
•  » » 22 months ago, # ^ | ← Rev. 6 →   +8 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 !
•  » » » 22 months ago, # ^ |   0 I m participating but just wanted to know about rating system...
•  » » » » 22 months ago, # ^ |   +8 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 :)
 » 22 months ago, # |   +47 Why does every comment in the form "Hope [noun/pronoun] verb ..." get downvoted? I don't understand...
•  » » 22 months ago, # ^ |   +57 Does anyone ever understand the reason for downvotes on codeforces?
•  » » » 22 months ago, # ^ | ← Rev. 3 →   +59 Red coders get Upvote By the way
•  » » 22 months ago, # ^ |   +127 Hope this comment won't get downvoted :)
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +30 Red Coder _ / \ _. Comment upvoted without even reading
•  » » » 22 months ago, # ^ |   +29 The "Red coders get Upvote" theory has been proven.
 » 22 months ago, # |   +8 Good luck for all (:
 » 22 months ago, # |   +7 Hope to become cyan finally, I need +22 good luck and have a good contest ...
•  » » 22 months ago, # ^ |   +5 hoping same just need +31
•  » » » 22 months ago, # ^ |   -15 Advice from little bro- Try solving from reverse. like , if you solve a,b,c thn solve today c,b,a :D
 » 22 months ago, # |   +28 Timings are getting bad for me. Will we have a contest on usual time any day soon?
•  » » 22 months ago, # ^ |   0 me too :(
 » 22 months ago, # | ← Rev. 3 →   -8 glad to know that all divisions coder will be participant. thanks a lot for the rated contest :) hope so, it will be a great contest as elimination round :) all the best to all :)
 » 22 months ago, # |   +13 Will the problems be significantly harder than the first round??
•  » » 22 months ago, # ^ |   0 I think not so.
•  » » » 22 months ago, # ^ |   +3 And you were wrong. :PAwesome problemset!
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 22 months ago, # ^ |   0 A simple but good idea.
 » 22 months ago, # | ← Rev. 2 →   +5 hope same kind of problem but of course with better statement. last round was awesome with the problem statement..... __
 » 22 months ago, # |   -26 I hope to raise my rating
 » 22 months ago, # |   -134 give me some downvotes
 » 22 months ago, # | ← Rev. 2 →   -41 Good Opportunity to gain something new... :)
•  » » 22 months ago, # ^ |   -15 why downvote his comment just because he is Asian.Or he is telling about a useful competition that dosent concern you.Or people just love to downvote if someone is not red. Now downvote me.
 » 22 months ago, # |   +21 This is my last codeforces round before flying to Dalian,wish to learn new skills!Thank you,vepifanov!
•  » » 22 months ago, # ^ | ← Rev. 2 →   -6 It is my last round before going to Hangzhou and Shenyang.
 » 22 months ago, # |   +2 Good luck to all and thanks vepifanov for this contest !!
 » 22 months ago, # |   -13 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.
 » 22 months ago, # |   -8 unusual is the new usual
 » 22 months ago, # | ← Rev. 3 →   -26 Hope, This round will be lot of excitement means hacking others code. :)
 » 22 months ago, # |   +7 wish to see a programming contest not a hack contest and better English statements GOOD LUCK FOR ALL :D
•  » » 22 months ago, # ^ | ← Rev. 2 →   +12 dude you don't have to comment the same phrase each contest xD
 » 22 months ago, # |   +6 Contest start delayed?
 » 22 months ago, # |   +36 (score[2] == score[3]) && (score[4] == score[5]) && (score[5] == score[6])? This is a strange distribution......
•  » » 22 months ago, # ^ |   -11 (score[2] != score[3])
•  » » » 22 months ago, # ^ |   +32 It's 0-indexed.
 » 22 months ago, # |   +10 delay 10 minutes
 » 22 months ago, # |   +14 Why Delayed -.-
•  » » 22 months ago, # ^ |   0 May be change of server or something :)
 » 22 months ago, # |   0 First 3hr long rated round of my CF life. Wish a different result then usual :)
•  » » 22 months ago, # ^ |   -6 Lol)
 » 22 months ago, # |   -6 Is the contest delayed because they want more participation ( 6k+ ) or because of some technical problem ?
•  » » 22 months ago, # ^ |   0 Neither I think.
•  » » 22 months ago, # ^ |   0 i think they want more people to participate
•  » » 22 months ago, # ^ |   +68 We are waiting for the onsite participants to be ready to start.
•  » » » 22 months ago, # ^ |   0 Ohh.. cool. I didn't thought of that.
•  » » » 22 months ago, # ^ |   -17 May be, they are not free. Because it's unusual time
•  » » 22 months ago, # ^ |   0 maybe they are giving a chance to those who missed to register in time :p
•  » » 22 months ago, # ^ |   0 I don't think 10 min would become a huge impact on participation...
 » 22 months ago, # |   +25 This is my first contest. Feeling scared and excited at the same time !
•  » » 22 months ago, # ^ |   +1 after a while it will be boring to wait until the contest starts! :/
 » 22 months ago, # |   0 Why I can't unregister? :/
•  » » 22 months ago, # ^ |   +16 Your rating will not change if you don't send any solution
•  » » » 22 months ago, # ^ |   0 ok, thank you
•  » » 22 months ago, # ^ |   0 No need to.just don't submit anything during the contest and you will be fine.
•  » » 22 months ago, # ^ | ← Rev. 2 →   -9 If you don't submit a solution during the contest your rating won't get affected, so there's no need to unregister.
 » 22 months ago, # |   +10 I hope I can Change to Blue
 » 22 months ago, # |   -9 Strange Scoring distribution: 500-1000-**1500-1500**-_2500-2500_-2500.
 » 22 months ago, # |   0 Gl hf
 » 22 months ago, # |   +5 My submission for D has been running pretest 10 for close to 10 minutes now with no final verdict. Can anyone help me out?
•  » » 22 months ago, # ^ |   0 Never mind, this just resolved.
 » 22 months ago, # |   +23 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.
 » 22 months ago, # | ← Rev. 7 →   +5 How to solve 2A?Edit: Nevermind, my solution passed.
 » 22 months ago, # |   +2 This was a very difficult contest for us DIV-2'ers :|
 » 22 months ago, # | ← Rev. 2 →   0 how to solve C? I tried a approach like making a equation with 2 variables but didnt have enough to solve it
 » 22 months ago, # |   0 How to solve G? I thought of bicconected components with Gauss elimination but could not work out the whole solution.
•  » » 22 months ago, # ^ |   +18 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)
 » 22 months ago, # |   0 What are the hacks for A and B?
•  » » 22 months ago, # ^ |   0 B 3 3 3 2 1 2 3 1 1 3 2
•  » » » 22 months ago, # ^ |   0 what is the expected output for this?
•  » » » » 22 months ago, # ^ |   +5 NO(My sol passed systets)
•  » » » 22 months ago, # ^ |   0 Should NO be the output?
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 I hacked B with 2 44 3 2 14 3 2 1
 » 22 months ago, # |   0 Div2C I forgot to use long long and spent 40min debugging...
•  » » 22 months ago, # ^ |   0 "long long case" was included in pretests for C?
•  » » » 22 months ago, # ^ |   +13 I failed on case #10, and got AC after using long long
 » 22 months ago, # |   0 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?
•  » » 22 months ago, # ^ |   +1 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.
•  » » » 22 months ago, # ^ |   +3 Then how do you increase count of all the sensors that come in the path on one increment?
•  » » » » 22 months ago, # ^ |   +3 I stored a map from the endpoints of a diagonal to a vector of the sensors on it.
•  » » » » » 22 months ago, # ^ |   0 could you please explain a bit more in detail i didn't get your idea.
•  » » » » » » 22 months ago, # ^ |   0 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.
 » 22 months ago, # |   -8 Just realized that n and m in problem C is only upto 105my overkill problem C solution using successive_substitution, theoritically (if free of bug) can solve for n and m upto 2×109.
•  » » 22 months ago, # ^ |   0 My solution's complexity is O(k) and it's 25 lines long. Is there a shorter slower solution that works?
•  » » » 22 months ago, # ^ |   0 Actually, O(k+h)
•  » » » » 22 months ago, # ^ |   0 Can you give me some hint about your solution?I get tle.
•  » » » » » 22 months ago, # ^ |   +1 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.
•  » » » 22 months ago, # ^ | ← Rev. 3 →   +1 There is some solution with complexity O(k+n+m) and IMHO the code is a bit longer, but faster to code.
•  » » » » 22 months ago, # ^ |   0 Tried this and got TLE (in python though). How do you check what the input when it's so long they put "..."?
•  » » » » » 22 months ago, # ^ |   +1 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++?
•  » » » » » » 22 months ago, # ^ |   0 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.
 » 22 months ago, # |   -8 saturday
 » 22 months ago, # |   +1 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 ?
•  » » 22 months ago, # ^ |   -20 I did it this wayfirst 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 waythis way O(n^3) but n is only up to 20 xd #include int n, m; int data[30][30]; bool ans; void change(int a, int b) { int i; for(i=0; i
•  » » 22 months ago, # ^ |   0 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.
•  » » » 22 months ago, # ^ |   +16 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.
 » 22 months ago, # |   0 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.
•  » » 22 months ago, # ^ |   +1 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=50You cannot transfer from town 0 to town 1 before transferring it to town 2.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   0 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: 3 2 3 1 0 0 0 4 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.
 » 22 months ago, # |   +3 Good thing that pretest were strong this time. Made me realize my mistake!
 » 22 months ago, # |   +5 So fast system testing
 » 22 months ago, # |   +9 At least I got the taste of being yellow (orange) for a while! :(
•  » » 22 months ago, # ^ |   +4 wow!! masteri cant get out of green island xd
•  » » » 22 months ago, # ^ |   +24 Candidate master now :DDon'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! :)
 » 22 months ago, # |   +8 AC D at 2:52,got 600 pts,:D FST B,lose 900 pts,:( gg my friend,return to div.2
•  » » 22 months ago, # ^ |   +9
•  » » 22 months ago, # ^ |   +4 Congratulations!! You are still in Div 1!
 » 22 months ago, # | ← Rev. 2 →   0 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.
 » 22 months ago, # |   +35 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...
•  » » 22 months ago, # ^ |   0 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 ...
•  » » 22 months ago, # ^ |   0 sry for necro-posting but how is this editor/IDE called. Ty in advance
•  » » » 22 months ago, # ^ |   0 Sublime Text3
 » 22 months ago, # | ← Rev. 2 →   0 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
•  » » 22 months ago, # ^ |   +3 The idea is correct, the implementation is wrong.
•  » » » 22 months ago, # ^ |   0 Can you tell what is wrong?, I can't figure it out.
 » 22 months ago, # |   +91 . lol
 » 22 months ago, # |   0 Questions were good...
 » 22 months ago, # |   0 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)
 » 22 months ago, # | ← Rev. 2 →   +45 is there any place to make a bug report?
•  » » 22 months ago, # ^ |   0 Same happened to me (OSX 10.12. Firefox and Chrome)
•  » » » 22 months ago, # ^ |   0 Yeah...I just want to know why. I got the correct answer on Windows10 and Windows8 .But wrong on codeforces...
•  » » 22 months ago, # ^ |   +5 You have already reported it :D
•  » » » 22 months ago, # ^ |   0 I didn't understand.Can you tell me in detail?Thank U very much...
•  » » » » 22 months ago, # ^ |   0 it seems the variable k in solve() will be -1 in that case
•  » » » » » 22 months ago, # ^ |   -8 OMG,I made a very stupid mistake...Thank U very much...
•  » » » » » » 22 months ago, # ^ |   +3 You would have been better more cautious... :)
 » 22 months ago, # | ← Rev. 2 →   -16 Deleted
 » 22 months ago, # |   0 How to solve D? and How to solve C using CRT ?
•  » » 22 months ago, # ^ |   0 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 21299508The 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.
•  » » 22 months ago, # ^ |   0 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 (7x, 4y). Note that the path of the ball is then equivalent to y = 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, so mk = 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 on x = y, we can use the 4 congruences We find the minimum such a, and check if it's  ≤ lcm(m, n).
 » 22 months ago, # |   0 Any ideas on how to solve D?
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 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!
•  » » 22 months ago, # ^ |   0 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).
•  » » 22 months ago, # ^ |   +4 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
•  » » » 22 months ago, # ^ |   +5 your comment is the best SandorGarcia
•  » » » » 22 months ago, # ^ |   0 Thanks, just trying to help.
•  » » » 22 months ago, # ^ |   +3 I think your solution is the best.
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 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
 » 22 months ago, # |   0 Unable to find the error. Please help. Got WA test 28. Code is readable I think. http://codeforces.com/contest/724/submission/21290857
•  » » 22 months ago, # ^ |   +8 consider this test: 2 aba Answer : aa
•  » » » 22 months ago, # ^ | ← Rev. 4 →   0 UPD: Done
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 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
 » 22 months ago, # |   0 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.
•  » » 22 months ago, # ^ |   0 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
 » 22 months ago, # |   0 Any ideas on how to solve E?
•  » » 22 months ago, # ^ | ← Rev. 2 →   +95 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 ≤ n and 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 has O(n2) edges and they will all TLE probably.But maximum flow is equal by value to minimum cut, which we can actually find in O(n2) time and O(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 exactly k vertices into S from 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 from l to 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]).
•  » » » 22 months ago, # ^ |   +14 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!
 » 22 months ago, # | ← Rev. 2 →   0 The same code submitted from different c++ versions gives different verdicthttp://codeforces.com/contest/724/submission/21301362http://codeforces.com/contest/724/submission/21299482 . any guesses why?
•  » » 22 months ago, # ^ | ← Rev. 3 →   +14 You have a bug in function next_point. y2 does not initialize. Likely you confused y1 to y2. ll x2, y2; if(dir == 1) { if(n-x1 > m-y1) { x2 = x1 + (m-y1); y2 = m; dir = 4; } else { x2 = n; y2 = y2 + (n-x1); //BUG dir = 2; } } P.S. Sorry for the bad English skills
•  » » » 22 months ago, # ^ |   0 Thanks :) !!
 » 22 months ago, # |   +28 why is a page like http://codeforces.com/ratings still blocked so long after the contest is over?
•  » » 22 months ago, # ^ |   0 Its working now!
 » 22 months ago, # |   -7 MY color changed
•  » » 22 months ago, # ^ |   0 And then u cheated and you are back.
 » 22 months ago, # |   0 Ratings have been updated but the user rating graph is not updated.
•  » » 22 months ago, # ^ |   0 And now the ratings have been reverted back too. Whats happening?
•  » » » 22 months ago, # ^ |   0 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.
•  » » » 22 months ago, # ^ |   0 Yes! I guess they are re-calculating the ratings after removal of unfair participants.
•  » » » 22 months ago, # ^ |   +1 Back to normal now. :)
 » 22 months ago, # |   0 After given rating why unrated me. http://codeforces.com/profile/Alhelal_WA Please check..............................
•  » » 22 months ago, # ^ |   +8 cuz you must have cheated lol
•  » » 22 months ago, # ^ |   0
•  » » » 22 months ago, # ^ |   +4 bruh y u not sweg lyk me
 » 22 months ago, # |   0 Editorial delay again
 » 22 months ago, # |   +8 Quite a long time for the next round :D
 » 22 months ago, # |   0 Any ideas on how to solve F and G? thx!
 » 22 months ago, # |   0 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.
•  » » 22 months ago, # ^ | ← Rev. 4 →   +1 consider bound as mirrorthen every action can be performed on another side. therefore, all points' coordinates are (x,x) (x )
•  » » » 22 months ago, # ^ |   +1 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.
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +1 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 (x, y) (x, 2*m-y) (2*n-x, y) (2*n-x, 2*m-y) 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 (x' mod 2*n = x OR x' mod 2*n = 2*n-x) AND (y' mod 2*m = y OR y' mod 2*m = 2*m-y) 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: val e1 = arrayOf((n*2 to x), (n*2 to (n*2 - x))) val e2 = arrayOf((m*2 to y), (m*2 to (m*2 - y))) for ((m1,v1) in e1) { for ((m2,v2) in e2) { 
•  » » » » » 22 months ago, # ^ |   0 Thanks a lot!
 » 22 months ago, # |   0 Can somebody tell me the algorithm of problem b
 » 22 months ago, # |   0 editorial?
 » 22 months ago, # |   +5 How to solve G ????
 » 22 months ago, # |   +2 roses r red violets r blue codeforces is unusual just like u
 » 22 months ago, # |   0 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.
 » 22 months ago, # |   0 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 2According 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...
•  » » 22 months ago, # ^ |   0 Make 1 3 2 in every row and swap columns.
•  » » » 22 months ago, # ^ |   0 Ohh. .Thank You. I was only checking the columns first and then rows.
 » 22 months ago, # |   -6 Hope better English statements,I also hope that my Rating can rise as well.
 » 22 months ago, # |   0 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
 » 22 months ago, # |   0 Could anyone tell me the reason that greedy is wrong in problem E ? Thanks ~:)
 » 22 months ago, # | ← Rev. 2 →   +3 Nice photos and Nice contest.