### Zlobober's blog

By Zlobober, 5 years ago, translation,

Hi everybody!

Tomorrow at 09:35 UTC there will be Codeforces Round #376 that is dedicated for the second division. At the same time there will be a Moscow School Team Olympiad, and, as a nice tradition, we bring you a CodeForces round based on its problems. Unfortunately, this time we weren't able to come up with a good problemset for a first division contestants, but, as usual, we invite first division to participate unofficially in this round.

Problems were prepared by timgaripov, platypus179, wilwell, Flyrise, ipavlov and vintage_Vlad_Makeev under my control. We would like to thank members of jury of the Team Olympiad: Endagorion, Helen Andreeva and GlebsHP, who also works as a coordinator from the CodeForces side. Also we are very grateful to MikeMirzayanov for a Polygon system that makes problem preparation and coordination of many involved people much simpler, and for a great CodeForces community that we are all part of.

We suggest you 6 problems for 2 hours. Good luck!

UPD The contest is over, results are final, thanks for participating! The editorial will be published later

UPD2 I'm sorry for an editorial delay. It's finally available here.

Congratulations to contest winners:

• +226

 » 5 years ago, # | ← Rev. 3 →   +61 An automorphic Round (376)376 * 376 = 141 376
 » 5 years ago, # |   -32 Am I the last AC submission ?
•  » » 5 years ago, # ^ |   +16 No,you are the last PP submission. 0.0
•  » » » 5 years ago, # ^ |   -6 Oh I have passed main test :).
 » 5 years ago, # | ← Rev. 2 →   -44 Most of the schools are open at that time in Iran (and maybe other countries) :(Missed four consecutive rounds just for the unusual time :(
•  » » 5 years ago, # ^ |   +11 There would be people who have missed the usual timing rounds because it is "unusual" for them .
•  » » » 5 years ago, # ^ |   -19 I wanted to downvote this, but upvoted instead :p
•  » » » » 5 years ago, # ^ |   -11 unusual comments.. unusual comments everywhere
•  » » » 5 years ago, # ^ | ← Rev. 4 →   +8 I think there can be a time dicipline all people have usual time!
•  » » 5 years ago, # ^ |   -28 It's your choice to live in Islamic countryPeople believing in Jesus are free at Sundays
•  » » » 5 years ago, # ^ |   +18 you don't have to be rude !
•  » » » » 5 years ago, # ^ |   0 I didn't want to. Just pointed out how ridicilous is this argument, considering the fact that in most countries Sundays are holidays.It's impossible to fit in every schedule. That's why contest time changes. To fit other's schedules.
•  » » » » » 5 years ago, # ^ |   +19 I don't think " People believing in Jesus " is just pointing out !
•  » » » » » » 5 years ago, # ^ |   -24 Actually I don't care much about what you think
•  » » » » » » » 5 years ago, # ^ |   +21 Actually you don't have to be rude at all
•  » » » » » » » » 5 years ago, # ^ |   -21 If truth is too rude for you go meet with your therapist, you have plenty to talk about.
•  » » » 5 years ago, # ^ |   +11 there are too many christians in the middle east and the islamic countries -_- Not racist.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   -25 Poor people...Also I didn't figure out how is racism relevant here. At my memory religions only fuels it, don't they?
•  » » » 5 years ago, # ^ |   +5 Codeforces should ban all the racist people, whatever their color is.
 » 5 years ago, # |   +52 Am I the only one feeling tired of reading comments like "Unusual is the new usual"?
•  » » 5 years ago, # ^ |   +3 you're not the only one. i can relate to this.
 » 5 years ago, # |   -156 downvote me plz
•  » » 5 years ago, # ^ |   -17 ok :)
 » 5 years ago, # |   +2 I hate this new usual time :(
 » 5 years ago, # |   +4 Most of the Middle East universities are open in this time :'(
•  » » 5 years ago, # ^ |   +5 Indeed
 » 5 years ago, # |   +7 Did anyone notice a sudden increase in contribution points? My contribution went from -30 to -3 in less than 3 days, without any wave of new upvotes.
•  » » 5 years ago, # ^ |   +6 for me it was a sudden decrease from 56 to 48 :(
•  » » » 5 years ago, # ^ |   +10 Law of conservation of contribution
 » 5 years ago, # |   -8 In contest invitation mail Zlobober isn't legendary!
 » 5 years ago, # |   +9 The time is very good for Chinese competitor.But it is a pity that the beginning time of this round is just the ending time of Dalian regional contest.
 » 5 years ago, # | ← Rev. 2 →   +7 In the registrants list, Div. 1 participants are not marked as unofficial participants. Is that normal?Update: it's fixed, actually.
 » 5 years ago, # | ← Rev. 2 →   +10 why div 1 participants are not unofficial ?Update : fixed
•  » » 5 years ago, # ^ |   -39 What part of "Unfortunately, this time we weren't able to come up with a good problemset for a first division contestants" do you find hard to understand?
 » 5 years ago, # |   +9 The round starts 1.5 hours after Google APAC 1D ends.Will have to eat quickly, rest in that time and be ready for the round. :D
•  » » 5 years ago, # ^ |   +8 Oh boy, I literally dieded.I almost reached rank 200, but my computer hung at the last second and it costed me 16 points. Shouldn't have submitted the code after the contest, that was freakin painful.
•  » » » 5 years ago, # ^ |   +39 Sorry to hear that you literally dieded. Rested in peace.
 » 5 years ago, # |   +7 Love the timing of recent contests. Usual timing is 2am for me, so am happy to actually be able to participate in a few contests.But I understand that others may not agree :)
 » 5 years ago, # |   0 I'll join. It's my first time.
 » 5 years ago, # | ← Rev. 2 →   0 Why do rounds these days occur at this unusual time?
 » 5 years ago, # |   +22 score distribution?
•  » » 5 years ago, # ^ |   0 they forget it :)
•  » » » 5 years ago, # ^ |   0 yeah :-)
 » 5 years ago, # |   -8 Ok :)
 » 5 years ago, # |   0 6 problems for 2 hours.Hopefully problem set will be easy at least 3.Best wishes everyone.
 » 5 years ago, # |   +10 10 minutes Late:)
 » 5 years ago, # |   +57 Start delayed! How unusual!
•  » » 5 years ago, # ^ |   +1 no un
•  » » » 5 years ago, # ^ |   0 2333
•  » » » » 5 years ago, # ^ |   0 2333333333
 » 5 years ago, # | ← Rev. 2 →   +17 Score distribution?
 » 5 years ago, # |   +1 Why Delayed ?
 » 5 years ago, # | ← Rev. 3 →   +29 I just don't get what is this problem which happens right in the begin of the contest and can be fixed in 10 minutes !
•  » » 5 years ago, # ^ |   0 How does it affect you?
 » 5 years ago, # |   +6 could some one say problem B more clear ? ! i cant understanr it : ( pleaseee ...
 » 5 years ago, # |   0 is it possible for sereja not to order any pizza on someday in 2nd problem
 » 5 years ago, # |   0 Problem B, Could He uses both coupons and discount at same time? like if it is 50 pizza, could he use 48 coupon and 1 discount?
•  » » 5 years ago, # ^ |   0 Well for B, you can use discount only if you are buying 2 that should solve it :| explanation sucks
•  » » 5 years ago, # ^ |   0 If he should buy 3 pizzas, he can buy 2 pizzas with discount and 1 pizza with coupon.
 » 5 years ago, # |   0 My submission for D is in queue for 5 mins. Still waiting.
 » 5 years ago, # |   -9 Am I the only one feeling tired of reading comments like "Unusual is the new usual"?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 Am I the only one feeling tired of reading repeated comments like this in each contest blog ?
 » 5 years ago, # | ← Rev. 3 →   +1 i hacked on F with complexity n*n for n=10^5. It failed ! Does the new server support 10^10 ??Edit: Got it ! My test case wasnt good enough !
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Can you show the code please(I guess it is n * log(n)(like this))
•  » » » 5 years ago, # ^ |   0 http://codeforces.com/contest/731/submission/21488890 Another guy hacked him for me :p !!
•  » » 5 years ago, # ^ |   0 May be complexity isn't n*n?)
 » 5 years ago, # | ← Rev. 2 →   0 How to solve C?
•  » » 5 years ago, # ^ |   0 Hint: think about DFS
•  » » 5 years ago, # ^ |   0 dsu i think
•  » » » 5 years ago, # ^ |   0 I too thought of dsu, but it kept failing at pretest 5. Any reason why it might not work
•  » » » » 5 years ago, # ^ |   0 same with me!
•  » » » 5 years ago, # ^ |   0 Can anyone illustarate smooth dsu solution
•  » » » » 5 years ago, # ^ |   +4 build a graph with undirected edges from each l[i] and r[i].now socks at indices l[i] and r[i] must have same color.now use dfs to find the connected components.its just like a normal dfs on undirected graph with edges from l[i] to r[i].each connected component should have same color.after finding components,for each component find the color which exists the most number of times and paint all other socks with this color.this minimizes the required number of paintings.for reference you can see my code.21497227
•  » » » » » 5 years ago, # ^ |   0 Damn, I spent about 1.5 hours on this problem and couldnt solve it. How do you guys think up these solutions? I understand it, and it is quite simple, but why does it actually work? "find the color which exists the most number of times and paint all other socks with this color.this minimizes the required number of paintings" — I understand that sometimes you just see the pattern and cant prove it, but how to see this pattern... :( I failed many problems just not being able to see the pattern. How can I improve this skill? Thanks in advance
•  » » » » » » 5 years ago, # ^ |   0 me too couldn't solve it during contest and i realized it later. I think it all comes with practice.
•  » » » » » » » 5 years ago, # ^ |   0 I hope so. ) Thanks for your reply.
•  » » » » » » 5 years ago, # ^ |   0 From my practice experience, whenver I think of a strategy in a scenario I go through steps like this: Come up with preprocessing ways that helps you analyze the situation. If it's a game then most of the time it is minimax considering it is the most frequent one that pops up. Go for greedy, enumerate a few test cases that I think that could be tricky to handle. If greedy still works, then go for it. If not, see if there is a dynamic programming relation between the states. Go for dp if it is available. If there is still no solution, then you are probably missing some major observation. Dig deeper into the sample cases for inspirations. Also check if the constraints are small enough for more naive solutions to pass.
•  » » » » » » » 5 years ago, # ^ |   0 Thank you a lot! I will try to use this strategy in practice.
•  » » 5 years ago, # ^ | ← Rev. 4 →   +6 Build a graph like this : If you have socks l[i], r[i], then add undirected edge from l[i] to r[i]. Now for each connected component in this graph, you must have 1 color. So we can solve each component independently. It's optimal for each component to change colours of all nodes in that component to the colour that appears the most in that component.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I used DFS....as u said.. But someone hacked me.. How? here is my solution solution
•  » » » » 5 years ago, # ^ |   0 for(i = 1 ; i <= N ; i++){ if(visited[i] == 0){ for(j = 1 ; j <= K ; j++) countcolor[j] = 0; _max = 0; ll v = dfs(i); ans += (v-_max); } }It works only with a few components count. I guess if theres maximum N and M — min, for instance 1, this would be N*K, while N = 2*10^5 and K = 2*10^5, which is TL, obviously.
•  » » » » 5 years ago, # ^ |   0 you are looping through color array every time.here your worst case will be N*K.instead just use a map and you can clear the map every time you run dfs.
•  » » » » » 5 years ago, # ^ |   0 shit.... This simple thing !!! I should have thought of that
•  » » 5 years ago, # ^ |   +4 Consider socks as nodes and pairs as edges. Now in this graph,paint each component with the color which have highest frequency in that component.
•  » » » 5 years ago, # ^ |   0 Could you tell me how to find the highest frequency in a independent component ?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Dfs and store in map amount of each color.
•  » » » » » 5 years ago, # ^ |   0 yes, a map indeed. I tried to find it with an array :(
•  » » 5 years ago, # ^ | ← Rev. 3 →   +4 For input5 3 51 1 3 4 51 22 34 5 You can split all the socks into groups (sets):S1 = {sock1, sock2, sock3},S2 = {sock4, sock5}All the socks in group S1 should be painted in a single color and all the socks in the group S2 should also be painted in a single color (probably, different from the color of S1).For the group Si we count the most frequent color among the socks and paint all the rest socks in that group to that color. In my example the socks in the group S1 have following colors:S1 = {black, black, red} The most frequent color in group S1 is black, so we paint the remaining sock (which is red) to color black. After repainting the set will look like that:S1 = {black, black, black}.
 » 5 years ago, # |   +3 How to solve F?
•  » » 5 years ago, # ^ |   -79 Maybe you have to learn how to solve A and B, too early for F ..
•  » » » 5 years ago, # ^ |   +20 It seemed interesting, because for small constraints it works but I got TLE for large ones which means I was doing something really wrong. So I am interested in learning.
•  » » » 5 years ago, # ^ |   +17 Lets not judge just by looking at color of handle :)
•  » » 5 years ago, # ^ |   0 I used some prefix array to know in O(1) time how many graphic cards are there with power from i to j. Then for each available power of graphics, for example for power 2, i was checking prefix array every 2 (2,4,6,8) and i was increasing max result for this power by (cards in this interval)*(current value/power i was checking(2) ).O(nlogn)
•  » » 5 years ago, # ^ |   +3 Consider every distinct tape as the leading tape and calculate the answer for this using sieve-like technique. Consider tape a[i], then all elements in range i*a[i] to (i+1)*a[i] will be added as i*a[i]. Number of elements between a range can be calculated using a precalculated array since the numbers are less 10^6.
 » 5 years ago, # |   0 please explain C I tried to do it bfs but it doesnt seem to be like that
•  » » 5 years ago, # ^ |   0 I did it using bfs, i made disjoint sets, and tried to find out the most repeated color in each disjoint set, and subtracted that value by size of the disjoint set.
•  » » » 5 years ago, # ^ |   -30 #include #include #include #include using namespace std; int n, m, k; int color[300000]; map > tree; map > sorted; int index[300000]; int index2[300000]; int visited[300000]; int cnt[300000]; int ans, p; void bfs(int col, int s) { queue q; q.push(s); int i; while(!q.empty()) { int now=q.front(); visited[now]=col; sorted[col][index2[col]++]=now; q.pop(); for(i=0; i
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Can u copy send link to your solution instead of copy code ? This seem inconvenience. sory fo my bad E =)
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 BFS works fine. The input is just not usual. For example, the input li = 10, ri = 42 may be repeated:10 42...10 42 this may lead you to insert 42 into adjacency list twice:adj[10].push_back(42);adj[10].push_back(42);
•  » » » 5 years ago, # ^ |   0 That's why i prefer map for adjacency list.
 » 5 years ago, # | ← Rev. 3 →   0 Was anyone else facing problems with opening the site? I couldn't open the site for half an hour during contest.
 » 5 years ago, # |   0 How did people use graph solution for problem C? What if graph is really dense ? It should go out of memory..
•  » » 5 years ago, # ^ |   0 Just use dsu.
•  » » » 5 years ago, # ^ |   0 Dont you think that people who used graphs should get MLE on like 10000X10000 dense graph?
•  » » » » 5 years ago, # ^ |   +14 Wut? There is only 2e5 edges and verticles, you can find connected compounds easily.
•  » » » » » 5 years ago, # ^ |   +14 Never mind, i think i need more sleep...
•  » » » 5 years ago, # ^ |   0 http://codeforces.com/contest/731/submission/21488359 I am getting TLE on pretest 6 using DSU
•  » » » » 5 years ago, # ^ |   0 http://codeforces.com/contest/731/submission/21482988I did using DSU check it out
•  » » 5 years ago, # ^ |   0 At most m edges in graph, since there can be repeated edges. How can it be dense?
 » 5 years ago, # | ← Rev. 2 →   0 What is wrong with following approach for D? It gets WA on pretest 5.Toposort the letters keeping in mind the word constraints. Check for cycle, if so print -1. Also check all nodes in graph are connected. If this is ensured, sort the toposort and check if it is possible at some level to break the sequence into two parts such that they are x, x + 1, x + 2, ...n - 1 followed by 1, 2, 3, 4...., x - 1. Submission: 21492973
 » 5 years ago, # |   +7 Was F easy or there are some tricky cases waiting in system testing
•  » » 5 years ago, # ^ |   +27
•  » » 5 years ago, # ^ |   0 I have the same question. It seems to be not so difficult :(
•  » » 5 years ago, # ^ |   0 Tricky cases :( I just wonder what's the proper solution to F...
 » 5 years ago, # |   0 I will fail b because I declared N to 1e5 and not 2*1e5, horrible mistake but I'm wondering why pretest doesn't cover such case!
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Are you sure it was 2*1e5?E: :( It was, I thought the max no of elements for A was 10000 but that was for Ai
 » 5 years ago, # |   +5 Very interesting round to me !I saw a lot of random solutions for F and some greedy for E... It will be a lot of WAs.
 » 5 years ago, # |   0 Can F be solved with a fenwick tree, and summing contents of the intervals between each power? I think that is O(n (log n)^2), is that fast enough?
•  » » 5 years ago, # ^ |   0 You could use prefix sum from reverse to get the same and hence reduce a logn factor
•  » » 5 years ago, # ^ |   0 Oh wait you can just compute the prefix sum. That makes sense.
•  » » 5 years ago, # ^ |   +6 my O(n log(n) ln(n)) solution passed. so I guess O(n log^2(n)) is fast enough.
 » 5 years ago, # |   -6 How to solve F?I noticed that the main card should be a prime, or 1. Then I wrote a sieve and a map to insert a number along with its index (in sorted input) in the map for each of its prime factors.
•  » » 5 years ago, # ^ |   +9 For each i, iterate over its multiples. If you are currently at x*i, all the numbers in the range [(x-1)*i, x*i) will have to be reduced to (x-1)*i. So, simply add the count of numbers in this range * (x-1)*i to current ans. Repeat for all i, and take max of these. Code
•  » » » 5 years ago, # ^ |   -7 I over complicated things.
•  » » 5 years ago, # ^ |   +1 why should the main card be prime ? Case : 4 4 6 12 36 main card : 4
•  » » » 5 years ago, # ^ |   -8 I was wrong
 » 5 years ago, # | ← Rev. 4 →   +9 D was really interesting. I got AC it using BIT. First of all, ans can be in range [0, c - 1]. For every successive interval, I found what intervals can lead to correct sorting order(handled by L and R), and what intervals cannot(handled by BIT). I maintained the interval [L, R] that contains the answer, and also BIT stores what index cannot be our answer. Finally, for any L ≤ i ≤ R, if BIT allows this to be an answer, print it. Otherwise answer doesn't exists.
•  » » 5 years ago, # ^ |   +3 But you got WA on system test 27!!
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Yups, did not get AC. Test cases aren't available as of now. So cant tell much about the reason.
•  » » » 5 years ago, # ^ |   0 Most probably I forgot to add "return 0;" when I check whether L > R. So it would print  - 1 twice.
•  » » » » 5 years ago, # ^ |   0 Yes that was the problem, It got AC now. Code
•  » » 5 years ago, # ^ |   0 I didn't notice intervals may split during contest. To mark invalid interval [l, r], I think f[l]++, f[r + 1]-- works.
 » 5 years ago, # |   0 Is the following approach for D right? I implemented this algorithm but it doesn't pass some pretests. Where is the mistake in this solution? Take two adjacent words, find the first position where letters are different. If the first letter is greater then we need to turn the wheel by minimum (c-a[i]) so that it becomes smaller than b[i]; if the second letter is greater then we can turn the wheel by maximum (c-b[i]) or else a[i] becomes greater. Store the maximum of the minimums and the minimum of the maximum and if the second value is less than the first then print "-1", else print the first value.
•  » » 5 years ago, # ^ | ← Rev. 5 →   +4 I also did similar. However "if the second letter is greater then we can turn the wheel by maximum (c-b[i]) or else a[i] becomes greater. " This is incomplete. There is another case.Eg:5 -> 6 -> 7 -> 17 -> 1 -> 2 -> 3(c = 7)As you see you could also rotate it 3 times and still ordered.
•  » » » 5 years ago, # ^ |   0 Hell, how haven't I noticed it.(
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 i implemented this too, but there's a catch!Suppose n=2 ,c=6 1 2 1 3(the numbers are 2 and 3)Then according to the above logic you can turn max:3 times but if you turn 5 times it again becomes valid. Hope it clears the doubt!
•  » » 5 years ago, # ^ | ← Rev. 4 →   +11 You have missed out cases.Let a be the char of the first word and b be that of the second word, at the first point of difference. If a < b, the valid range is [0, c-b] U [c+1-a, c].If a > b, the valid range is [c+1-a, c-b] Then from the valid ranges of all the pairs of adjacent words, you can choose any common value. If there is no point which is common to all the ranges, answer is not possible. Also, apart from these, if the second word is a prefix of the first one and is shorter than the first word, answer is not possible. Code
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Shouldn't the valid range for a
•  » » » » 5 years ago, # ^ |   0 It doesn't matter since if [c] is available then [c%c=0] is also available, and the smallest solution always get chose first.
 » 5 years ago, # | ← Rev. 2 →   0 I used DSU for DIV2 C but I am getting TLE on pretest 6.http://codeforces.com/contest/731/submission/21488359
•  » » 5 years ago, # ^ |   +6 You're declaring this array ll cnt[223456] too many times.
•  » » » 5 years ago, # ^ |   0 http://codeforces.com/contest/731/submission/21493869 resubmitted but result still same
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   +11 It's the same complexity now. Memset on N elements is O(N) so you're calling it at most N times -> O(N ^ 2) complexity. I solved it like this : when i dfs, i store the nodes in current component in a list. So now i only need to reset for those. Each node appears in one component -> O(N) complexity for that part. Here's my code: http://codeforces.com/contest/731/submission/21485829.
•  » » » » » 5 years ago, # ^ |   +8 Thnks a ton. I didnt know that memset on n elements is O(n).
 » 5 years ago, # | ← Rev. 3 →   0 I solved the C problem with DFS, but I got TLE... How to optimize my code? http://codeforces.com/contest/731/submission/21484127 Or is it just recursive vs queue? XD
•  » » 5 years ago, # ^ |   +3 If the graph is empty, your codes is O(N2), because of this: memset(colNow,0,sizeof colNow); 
•  » » 5 years ago, # ^ |   0 The problem isn't in dfs i think. But in memset(colNow,0,sizeof col) Think when there are many connected components, it will get tle.
•  » » 5 years ago, # ^ |   +9 In the worst case memset would be called 2*10^5 times , which is basically O(N^2) . Use a map instead .
•  » » 5 years ago, # ^ |   +1 you can save the vertices that you go to them in dfs ,in a vector and after dfs make the colnow of them equal zero or dfs again and do it
 » 5 years ago, # |   +14 kudos to the author for such a nice contest!
 » 5 years ago, # |   0 What's the idea for solving E ?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +13 What I did was this. Let DP[1][i] be the max score which can be obtained by Petya, if in his next turn he has to choose a prefix of length at least i and let DP[0][i] denote the same for Gena.Let S[j] denote prefix sum till j, i.e. arr[1]+arr[2]+arr[3]+...arr[j]Petya tries to get the maximum value possible and Gena tries to get the lowest value possible. DP[1][i] = max(S[j] + DP[0][j+1]), j>=iDP[0][i] = min(-S[j] + DP[1][j+1]), j>=i The answer is given by DP[1][2] (1-indexing is used). Code
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Dynamic Programming on prefix sum arraycheck this: http://codeforces.com/contest/731/submission/21488865
•  » » » 5 years ago, # ^ |   0 your solution is pretty good,it's easy for me to understand
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 Let S[i] be the sum of the numbers from 1 to i.Let D[i] be the optimal maximum difference for the current player if the leftmost sticker contains the sum of the numbers from 1 to i. Then D[i] = max{S[j] — D[j]} for i < j <= N.But since S[j] — D[j] is independent of i, we can just keep track of the maximum S[j] — D[j] and update it at every loop, leading to O(N) solution.
•  » » » 5 years ago, # ^ |   0 How you are taking account of the two persons , please elaborate?
•  » » » » 5 years ago, # ^ |   0 The best play for one person in a certain configuration is the same as the best play for the other."Then D[i] = max{S[j] — D[j]} for i < j <= N"S[j] is what you get from choosing up until the sticker jD[j] is the best play on the configuration jSo you choose the best play possible for every situation.
 » 5 years ago, # |   +14 As I see, problem F easier than problem D & E, problem B easier to WA then problem F :)) funny contest
 » 5 years ago, # |   0 This time is so good for chinese competitor.Thank you for your good game.
 » 5 years ago, # |   0 Hopefully become Expert:)
•  » » 5 years ago, # ^ |   0 You did it, brave move :)
 » 5 years ago, # | ← Rev. 2 →   0 I think problem C can be interpreted in 2 ways. 1. Counting cost of colouring of both left and right pieces of i-th pair of socks as 2.(Counting colouring of each left and right sock seperately) 2. Counting cost of colouring of both left and right pieces of i-th pair of socks as 1.During the contest, I have implemented assuming case:1, which failed on pretest 3. After the contest, I see that I was supposed to assume the other case.Here are my submissions with only difference being which assumption was considered among the above. Assumption-1 : 21492459 Failed Assumption-2 : 21493466 AcceptedShould have got this clarified during the contest :(
•  » » 5 years ago, # ^ |   0 You never have to color both the right and left sock though..
 » 5 years ago, # |   0 can someone identify the mistake in my submission for "C", i keep getting WA on 6.
•  » » 5 years ago, # ^ |   0 Hope that comment helps.
•  » » » 5 years ago, # ^ |   0 i tried a testcase with repeated indeces , it is giving correct output for that .
•  » » » » 5 years ago, # ^ |   0 Your code gives negative answer. That means the expression (size - maxi) sometimes is negative, that is sometimes size becomes smaller than maxi. You can try thinking backwards and work out an example when this is true.
•  » » 5 years ago, # ^ |   0 You use variable 'i' in two loops that are nested.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 i corrected that , it still gives WA on 6 .nevermind , got it !
•  » » 5 years ago, # ^ |   0 It would anyways TLE , it is O(N*K)
 » 5 years ago, # |   0 Rating Updated!
 » 5 years ago, # | ← Rev. 2 →   0 Got TLE for C at test case 33 mysolution . I tried with DSU. Could somebody help?
•  » » 5 years ago, # ^ |   0
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 what does map<> h stores? count of occurrences of colors?
•  » » 5 years ago, # ^ |   +1 there's a small thing that needs to be considered .i think you are clearing the count array every time you run dfs.instead use a map and clear it.
•  » » » 5 years ago, # ^ |   0 my AC solution: Solution linkneeded to replace count vector with map -- to avoid TLEneeded to avoid members insertion during UNION -- to avoid MLEThanks
 » 5 years ago, # |   +18 Finally I'm Cyan !!, and I solved 3 problems from the first submission. Self confidence is rising here ! thank you Zlobober very much for the nice contest
 » 5 years ago, # |   +3 No hacks this time :-)
 » 5 years ago, # |   0 http://codeforces.com/contest/731/submission/21485811 WA in test case 66 :( Can anyone help ?
•  » » 5 years ago, # ^ |   0 Someone please point out the bug ... unable to find it ....
•  » » » 5 years ago, # ^ |   0 In the last loop in main(), the upper bound for i should be m instead of n.
 » 5 years ago, # | ← Rev. 2 →   0 Why does this TLE for F ?http://codeforces.com/contest/731/submission/21494655
•  » » 5 years ago, # ^ |   +3 I also unintentionally did the same mistake...Since the values of array may not be distinct. So, we should avoid calculation for same elements , otherwise if we calculate for value say, 1 or 2, for many times, then this will lead to O(n*n)...I had sorted array, then was trying to escape repetition, but forgot to do that while coding,, finally, which causes TLE :( .
 » 5 years ago, # |   0 How do you solve problem B? I wrote "something" which passed the pretests but it doesn't work it some cases. What's the normal solution for this problem?
•  » » 5 years ago, # ^ |   +3 Iterate from left to right . If arr[i] is even we can use coupons and we are done . But if arr[i] is odd , arr[i+1] should exist and should be positive . If not print NO else do arr[i+1] -= 1 .
•  » » » 5 years ago, # ^ |   0 Thanks, that's so easy and obvious...I actually thought the same but then was misled by some example which I treated incorrectly.
 » 5 years ago, # |   0 anyone can find my code bug for problem C ????? I'm using DSU , calculating all socks needed minus the largest number of colors for every parent. http://codeforces.com/contest/731/submission/21491376
•  » » 5 years ago, # ^ |   0 What does the function join() return?
•  » » » 5 years ago, # ^ |   0 nothing
•  » » 5 years ago, # ^ |   0 You are coloring everything with the maximal color, not the color with maximal number in map( because pairs are sorted by the first element, not the second).
 » 5 years ago, # |   0 :'( F gave TLE on 26th test passed just by fast I/O Yeah Life is unfair!
 » 5 years ago, # |   +1 I don't know why, but I found Problem B very tough (I solved it somehow though :P). Can anyone suggest a simple solution?
•  » » 5 years ago, # ^ |   +1 Here is mine: For i = 0...n-2 (skips the last) ---> if a[i] > 2 then a[i] %= 2 ---> after that, if a[i] == 1 and a[i + 1] == 1 then reduce both of them. The result is 'YES' if sum of remain elements in a is 0. Otherwise, it is 'NO'. Hope this helps.
•  » » 5 years ago, # ^ |   +1 Break the array wherever 0 is present. Find sum of each part. Answer is YES if sum of each part is even.Code
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 from 0 to n-1 if a[i] < 0 answer no and break; else if a[i] is odd substract from a[i+1] 1;then check last element a[n-1] if its odd or less than 0, answer no;otherwise answer yes
 » 5 years ago, # |   -6 There is something mystery in this contest for my case. My code for solving problem C returns 2 for Test 5, which is correct, on my computer. But when I upload the code, it became 3, which is wrong answer.Because it's correct on my computer so that I have no idea where it went wrong. Please take a look: http://codeforces.com/contest/731/submission/21493963Many thanks. P/S: Picture proof.
•  » » 5 years ago, # ^ |   0 Which ide are you using?
•  » » » 5 years ago, # ^ |   0 it's sublime text
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +3 The Sublime Text 2 + SublimeInput for internal testing.
•  » » 5 years ago, # ^ |   +26 Comparator in C++ must return 1 if the first argument is less, then the second. Otherwise 0.
 » 5 years ago, # |   +16 Nice round.. I think problem F was overrated ... it should have been a C or a D. however it was an interesting round. thanks
 » 5 years ago, # |   0 3 points from getting blue :C Anyways, can someone please tell me the solution for problem F?
•  » » 5 years ago, # ^ |   +21 Let f(x) denote the number of integers that are  ≥ x. Then, if we fix a number i as leader, the total sum will be f(i) + f(2i) + f(3i) + ....We can precompute f(i) for all i ≤ 200000 by using the same method as sieving primes. The time complexity is .
•  » » » 5 years ago, # ^ |   +3 Interesting, I didn't think about that.If you don't precompute f(i) you can use binary search to find it, making the complexity O(n*logn*logn) but without the need to worry about precomputation.
•  » » » 5 years ago, # ^ |   0 Very nice solution, thank you.
•  » » » 5 years ago, # ^ |   0 Interesting solution :)
•  » » » 5 years ago, # ^ |   0 I don't understand even if you precompute f(i) for all i<=200000, then also you have to sum it for i, 2i, 3i, ... (200000/i) elements. Why isn't it O(n^2). Here's my solution along the lines suggested by you, it's getting time limit exceeded and the reason I could think of is the above. Am I missing something.http://codeforces.com/contest/731/submission/21516249
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 Make sure you don't visit the multiples that you have already visited and it should get accepted. You took care of the case with repeated ones but look at the one you got TLE'd (repeated twos)Edit: it is worth noting the reason why this is O(nlogn).If you don't visit the same number twice, it takes at most N+N/2+N/3+...+N/N.That's the same as N(1+1/2+1/3+...+1/N). That sum is bounded by ln (look for the integral of 1/x from 1 to n) so the complexity is O(n*logn).
•  » » » » » 5 years ago, # ^ |   0 Thanks!
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 deleted
 » 5 years ago, # | ← Rev. 2 →   +3 Spent an hour and 2 wrong submissions on C because I thought you had to color socks dynamically every day and not just all of them at once beforehand. :DGood thing I went and solved F before realizing how easy C actually was.Just wondering, how to solve C if you can color socks dynamically?
 » 5 years ago, # |   0 anyone knows why my solution for c fails? http://codeforces.com/contest/731/submission/21498239
 » 5 years ago, # |   0 All the best guys
 » 5 years ago, # |   0 Can someone explain the solution to Problem D?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +8 Here is my approach:For each block i (0<=i
•  » » » 5 years ago, # ^ |   0 Can u please elaborate the last part of your solution. Means how you are using the chk[] array to check for intervals where we can shift the lock ??
•  » » » » 5 years ago, # ^ |   +11 Let's say we are counting the amount of intervals at a certain point. The most naive solution is to increament each of the points within the interval by one — but this takes O(n) time to mark each interval.Instead, we can increase the start of the interval by one, and the point near to its' end of it by one, and calculate the prefix sum after we have mark all intervals, and this will tell us how many intervals lie on a certain point. Why does this work? Consider each interval individually, the prefix sum will cause all points on interval [left,right] increase by one, yet since [right+1] has a value -1, therefore it gets canceled and the interval [right,n) remains uneffected.
•  » » » » » 5 years ago, # ^ |   0 Thanks A lot. :)
 » 5 years ago, # | ← Rev. 2 →   +2 mfw practicing and see F only have the "brute force" tag.nvm they fixed it. =]
 » 5 years ago, # |   +3 I liked how none of the problems used complex data structure and algorithms.
 » 5 years ago, # |   +3 quite surprised about the AC number of each problem.I think E is quite easy, the idea is easy and very easy coding.D is a little complicated to code, but the idea isn't hard. F is hard for me, I didn't figure out a way by myself even after contest.
 » 5 years ago, # |   0 I hope for an editorial for this contest, as well as for Technocup.
 » 5 years ago, # |   +3 plz upload the editorial!!!
 » 5 years ago, # | ← Rev. 2 →   0 I Can't get What is wrong on my solution... Solution I get Pretest Passed at 1:59.. but failed to pass Main test at Test22.Please Let me know Why my solution is not working on this test case like 19999 10001 10002 10003 10004 ...I solved The Problem F bruteforce. 1. sort input 2. from the small number to large number in the input, vec[1...n], Iterated if the mainpower key is v[i], if v[j] % v[i] == 0, pass. or not, v[j] -= v[j]%v[i] ( to make secondary power) 3. print the answer
•  » » 5 years ago, # ^ | ← Rev. 2 →   +10 200000 100001 100002 ... 101000 200000 200000 ... 200000 The answer is 200000 * 199000
•  » » » 5 years ago, # ^ |   0 Oh my... Thanks a lot. I realized
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 You should say, "I submitted The Problem F bruteforce" instead of saying, "I solved The Problem F bruteforce", since all of your submissions for F got WA!
•  » » » 5 years ago, # ^ |   0 Thanks for giving great advice!!
 » 5 years ago, # | ← Rev. 2 →   0 i think there maybe some mistakes of problem F. the two same codes, the first code, define maxn=1000100,it AC;21510847. the second code, define maxn=200100,it WR on31;21510692.
•  » » 5 years ago, # ^ |   +16 Because you used num[j + i]
•  » » » 5 years ago, # ^ |   0 i see. my mistake .thanks a lot :)
 » 5 years ago, # |   0 21506585 — > What is my off by one error? :(
 » 5 years ago, # |   0 Could anyone comment the Problem E example 2? input: 1 -7 -2 3 a) turn 1: A takes 1 -7 -2, puts -8 turn 2: B takes -8 3 totals: A - B = (1 -7 -2) - (-8 + 3) = -3 b) turn 1: A takes 1 -7, puts -6 turn 2: B takes -6 -2 3 totals: A - B = (1 -7) - (-6 -2 + 3) = -1 Why (a) is corrent answer? (b) is better than (a)! 
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 B is not playing optimally in b)turn 1: A takes 1 -7, puts -6turn 2: B takes -6 -2, puts -8turn 3: A takes -8 3, puts -5A's score: -6 + -5 = -11B's score: -8diff = -11 — -8 = -3Sometimes you can force a turn on others and thus reducing their scores. >=]
•  » » 5 years ago, # ^ |   0 Could you dig a bit more please? Why -8 in (1) is considered "optimal" but -21000 in (2) is not? input 1: 1 -7 -2 3 input 2: -6000 -5000 -4000 -3000 -2000 -1000 
•  » » » 5 years ago, # ^ |   0 optimal moves for input2:turn 1: A takes [1,5], S= -20000. turn 2: B takes [1,2], S= -21000.Difference in score= +1000
 » 5 years ago, # |   +12 When will the editorials be up!?
•  » » 5 years ago, # ^ |   +10 It's finally there: http://codeforces.com/blog/entry/47840I'm sorry for the delay.
 » 5 years ago, # |   0 Where is the tutorial?
•  » » 5 years ago, # ^ |   +10 Right above ya
 » 5 years ago, # |   0 not able to understand why to use DSU for the div2C problem.Could someone please explain.
 » 5 years ago, # |   0 @Zlobober Please add tutorial to the box names [→ Contest materials] on the righ_bottom of web-pages of the problems. Thank you.
•  » » 5 years ago, # ^ |   0 Check it now :)
•  » » » 5 years ago, # ^ |   0 Thanks a lot~