### MikeMirzayanov's blog

By MikeMirzayanov, 15 months ago, translation, ,

Hello!

ACM-ICPC Southern Subregional Contest (NEERC/Northern Eurasia) 2018 has ended on October 16. There were 72 teams onsite in Saratov, most of them were invited because of their result on the qualification stage.

In this contest I play a role of Cheif Judge and the jury teams consists of ex-participants of ICPC from Saratov and jury members from other cities. Many thanks to all of them! I hope you will like the problems!

I invite ACM-ICPC teams and individual participants of Codeforces competitions to take part! Sure, the contest will be unrated.

MikeMirzayanov

• +221

 » 15 months ago, # |   +25 you forgot to thank MikeMirzayanov
•  » » 15 months ago, # ^ |   +37 He told to him personally
•  » » 15 months ago, # ^ | ← Rev. 2 →   -40 Thanks are the default setting.
 » 15 months ago, # |   0 Will there be problems of all dificulties or just really tough ones?
 » 15 months ago, # |   +6 Why some participants' number in the Registrants list is red?
•  » » 15 months ago, # ^ |   +6 Multiple registration I guess.
•  » » » 15 months ago, # ^ |   0 what is Multiple registration ?
•  » » » » 15 months ago, # ^ |   +1 register in 2 or more groups?
•  » » » » » 15 months ago, # ^ |   0 Thank you.
 » 15 months ago, # | ← Rev. 3 →   -42 ...
 » 15 months ago, # |   -30 Is it rated? I'm serious.
 » 15 months ago, # |   +71 How to solve M?
•  » » 15 months ago, # ^ |   -51 You've tried 7 times, have you got any partial ideas or conclusions?
•  » » 15 months ago, # ^ |   0 I found out you have solved it, could you share the solution of M. QAQ
 » 15 months ago, # |   +22 How to solve A?
•  » » 15 months ago, # ^ | ← Rev. 7 →   +43 BFS. State: remainder, digit sum, number. Then, apply bfs. For every node, we can get its adjacent nodes like this, number * 10 + i, for their states, we can calculate remainder = (current node's remainder * 10 + i) % d and digit sum = (current node's digit sum + i) where i = 0 to 9. Then check for a particular node, if its remainder = 0 and digit sum = s, so this is our answer. For reference, my code: http://codeforces.com/contest/1070/submission/44598713
•  » » » 15 months ago, # ^ |   0 How did you get the intuition for this question? I mean, how did you came to conclusion that applying BFS would be good?Thanks for the summary.
•  » » » » 15 months ago, # ^ |   +1 First I had a similar idea using backtrack, I have solved the same kind of problems before.
•  » » » » » 15 months ago, # ^ |   0 Can you suggest some more problems of this kind please ?
•  » » » » » » 15 months ago, # ^ |   +3 Yes. Try this question.
•  » » » » 15 months ago, # ^ |   +1 Himitsu, read this post :)
•  » » » » » 15 months ago, # ^ |   0 Thank You :)
•  » » » 15 months ago, # ^ |   +1 But how can we know the answer is '-1'? And why is BFS better than DFS?
•  » » » » 15 months ago, # ^ |   0 In general, we are doing BFS because we want to find answer with minimum number of digits. (The intuition is that we want to go wide, not deep.)We visit all numbers who's digit sum is at most S. If we haven't found the number yet, the number doesn't exist :)
•  » » » » » 15 months ago, # ^ |   +1 I get it.Thank you.
 » 15 months ago, # |   +9 In J, is it just that only one character needs to be split across two sides and rest all characters will be only on one of the sides and rest do with bitsets?
•  » » 15 months ago, # ^ |   +3 Yes, but bitsets are too slow because of multitest. You can get OK without them.
•  » » 15 months ago, # ^ |   +7 Yes, only one letter will be split across sides and others will be used whole on one side only. You can use subset sum to check if sum X is possible or not.
•  » » » 13 months ago, # ^ |   0 Why have you assumed that any alphabet other than the one that will be split will either be completely in the smaller set or will not be there
•  » » 15 months ago, # ^ |   +3 Yeah, the same solution with bitset. code
 » 15 months ago, # |   0 where can i see test data?
•  » » 15 months ago, # ^ |   0 sorry, I can see it now. XD
 » 15 months ago, # |   +37 L is very cool, thanks
•  » » 15 months ago, # ^ |   0 How to solve it?
•  » » » 15 months ago, # ^ |   +34 Let's come up with a way to find answer if it is at most 2 and then we will show that it always find the answer.We want to distribute vertices in two classes, it is the same as giving each vertex 0 or 1. Let's say that vertex v gets xv (which is 0 or 1). Now I state that all our properties about parity of degree can be written as linear equations in . Suppose that vertex v initially had even degree. Then it is not important what is xv: in all cases v should have even number of neighbors with 1, in other words . Now suppose vertex v initially had odd degree. Then if xv = 0 then v will have odd number of neighbors with 1, and if xv = 1 then v will have even number of neighbors with 1, in other words .If this system of linear equations has a solution then we are done. How can it be that there is no solutions? Some equations contradict each other. In the only way is to add some of equations and get 0 = 1. Suppose that happens. Let's denote set of vertices corresponding to those equations C. C has odd number of vertices with initially odd degree (otherwise we would have 0 in the right side). Since we have 0 in the left side it is true that all xu have even coefficients, it is true also for vertices in C. That means that if we will look at subgraph induced by C all initially even vertices will have even degree and all initially odd vertices will have odd degree (don't forget that for odd vertices we add not only its neighbors but also itself). But we have odd number of vertices with initially odd degree, so sum of degrees of all vertices in this induced subgraph is odd which is impossible.Therefore there is always a solution with at most 2 components. Checking is there is a solution with 1 component is trivial, and for finding the solution we will use gaussian elimination with bitsets.
•  » » » 15 months ago, # ^ |   +19 Here is a different solution, that also shows we never need more than 2 states.44659832 — runs in O(N^3 / bitset)(the problem was discussed on some facebook group some time ago — apparently it also turned up on the POI)
•  » » » » 15 months ago, # ^ |   +5 Looks like it could be done without bitsets. I've implemented this idea and got AC with time complexity O(N^2 + sum(deg[i]^2)) which is not worse than O(N * M).
 » 15 months ago, # |   +8 In L how to prove that answer is no more than 2? I guessed it and successfully got Accepted.
•  » » 15 months ago, # ^ | ← Rev. 6 →   -24 This is wrong.
 » 15 months ago, # | ← Rev. 2 →   0 Can A be solved by DFS? I tried to solve it with memory search.But I could not pass it.
 » 15 months ago, # |   +1 How to solve I ?
•  » » 15 months ago, # ^ | ← Rev. 38 →   +30 It's not better to color two edges which are not adjacent.Consider the degree of one vertex, call it r. If r>2k, there is no solution. If r<=k, we can just ignore it. If k
•  » » » 15 months ago, # ^ |   +4 Thank you very much. I have got it via your explanation.
 » 15 months ago, # |   +4 Will there be an editorial put up?
 » 15 months ago, # |   +21 Can E (Getting Deals Done) be solved using Ternary search?
•  » » 15 months ago, # ^ |   +8 It can (44592241), but binary is enough.
•  » » » 15 months ago, # ^ |   +3 can you explain how it can be done with binary search?
•  » » » » 15 months ago, # ^ |   0 F(d) = {0,1} — can we do all of the tasks that is less or equal to d. The values of this function will be in form of 1111100000. With binary search we should find 1-0 point, and result will be either in the last point with value 1 or in the first point with value 0.
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   0 So far, I've understood that one can binary search without the constraint of extra time after m tasks. However, how can you prove that the tasks will still be of the form 11..00.. even after adding this additional constraint?
 » 15 months ago, # | ← Rev. 3 →   0 My output for the sample test case 1 of E (Getting Deals Done):3 54 62 90 101Why this is wrong? It is given that we can print any value of d.
•  » » 15 months ago, # ^ |   +4 You should satisfy condition d <= t.
 » 15 months ago, # |   +6 How to solve C ?
•  » » 15 months ago, # ^ | ← Rev. 4 →   0 You can solve it greedy. The main observation is: you able to sort available tariffs by price in non-decreasing order and choose some of them greedy every day starting by cheapest and stopping when you got enough cores. Then just model tariff starts and finishes in historical order, accumulating paid amount per day. You also will need some data structure to keep active tariffs and their cost day-to-day, segment tree or Fenwick tree, and binary search to determine count of tariffs to buy today in log(m).See my submission 44600156 for implementation based on segment tree; its complexity is O(m * log2(m)).
•  » » » 15 months ago, # ^ |   +3 Binary search is not needed, Fenwick tree supports the operation "first index with prefix sum greater than x", 44588175
•  » » » 3 months ago, # ^ |   0 I can't understand your solution. Can you please explain more?
 » 15 months ago, # |   +8 Will there be an editorial?
 » 15 months ago, # |   +16 Can I get the editorial?
 » 15 months ago, # | ← Rev. 2 →   0 How to solve problems G, I?
•  » » 15 months ago, # ^ |   +5 For G, you can try every possible position, call it x. Now you can greedily try to move the closest hero that can beat all monsters in the path to x, and if at the end you can move everyone, then you have found the answer. The complexity is O(N^3).
 » 15 months ago, # |   0 How to solve I?? QAQ
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 I'm sorry.The solution is on the top, but I overlook it.
 » 15 months ago, # | ← Rev. 3 →   0 About problem B If the input data is 7 +0.0.0.13 +0.0.0.12/32 -0.0.0.2/31 -0.0.0.7/32 -0.0.0.10 -0.0.0.9/32 -0.0.0.8/31 output data is: 2 0.0.0.0/29 0.0.0.8/30 but my answer is: 2 0.0.0.2/29 0.0.0.10/32 I think my answer is also right,but it is WrongAnswer why?
•  » » 15 months ago, # ^ |   +15 From the statement: "It is required that 32 - x rightmost (least significant) bits of subnet a.b.c.d/x are zeroes." 0.0.0.2/29 violates this requirement.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 Could you give an example?I do not understand.And why does 0.0.0.2/29 violate this requirement?
•  » » » 15 months ago, # ^ |   0 I already understand it.Thanks.
 » 15 months ago, # | ← Rev. 2 →   0 how to solve C ?? looks like some have done sweepline ..
•  » » 15 months ago, # ^ |   +3 That's not sweepline, you just consider a tariff task as two events, and do some proper segment tree over prices.
•  » » » 15 months ago, # ^ |   0 could you elaborate a little more...
 » 15 months ago, # |   0 Can anybody explain the flow solution for the problem I? Thanks!
 » 15 months ago, # |   0 How to resolve H? I see it is a blute force problem. But I get timeout. Can someone give me a guide how to implement a blute force solution with any special skills?
 » 14 months ago, # |   -7 How to solve Problem F?