vovuh's blog

By vovuh, history, 5 months ago, translation, ,

<almost-copy-pasted-part>

Hello! Codeforces Round #582 (Div. 3) will start at Aug/30/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD: Thanks to Artem Rox Plotkin for testing the round!

UPD2: Editorial is published!

• +187

 » 5 months ago, # | ← Rev. 2 →   0 [deleted]
 » 5 months ago, # |   -7 I hope I will get some positive rating from the contest.
•  » » 5 months ago, # ^ |   -29 YOU WILL NOT!!!!!!!!!!!!!!! I AM SURE THAT AFTER 5 CONTESTS YOUR RAITING WILL BE BELOW 750!!!!!!!!!!!!!!!!!!!!!1
•  » » » 5 months ago, # ^ |   +15 Why are you being mean? You are not even blue yet LMAO
•  » » » » 5 months ago, # ^ |   -24 In my real account my raiting is 1700+
•  » » » » » 5 months ago, # ^ |   +15 No one cares..Just learn to be nice to people
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 I am just trolling in all my comments(not in posts).my small contribution can proof this. But this comment is not trolling and is true
 » 5 months ago, # |   +3 First,div3 after becoming expert hope my rating remains constant.
•  » » 5 months ago, # ^ |   0 your rating will remain constant because div.3 is unrated to experts and higher like you and me.
•  » » 5 months ago, # ^ |   +22 Raiting does not matter, matter only nice girls!
 » 5 months ago, # | ← Rev. 3 →   +32 Now I can say "I won't lose my rating ANYWAY!" proudly :D
•  » » 5 months ago, # ^ |   +17 Now I can say "I won't gain any rating ANYWAY" sadly :(
 » 5 months ago, # |   +27 This will be my first contest. I hope I will do well and good luck for everyone for the same....
•  » » 5 months ago, # ^ |   0 Good luck.
•  » » 5 months ago, # ^ |   0 Didn’t take part in it?
 » 5 months ago, # |   +1 Hope the ranking of problems be better from the last contest.
 » 5 months ago, # |   +1 After this contest,I think I will be a expert.How excited I am!
•  » » 5 months ago, # ^ |   +11 Hope you will be an expert
•  » » » 5 months ago, # ^ |   0 Thanks!
•  » » » » 4 months ago, # ^ |   0 you are now expert
•  » » 5 months ago, # ^ |   +5 A japanese friend told me that reaching blue in a div3 (and yellow in a div2) is dishonorable.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -7 I thought it was orange :(
•  » » » » 5 months ago, # ^ |   +5 to my eyes: yellow = master, orange= international master
 » 5 months ago, # |   0 I hope that rating Will increase somehow.
 » 5 months ago, # |   +3 Vovuh...master of preparing div3 contests...
•  » » 5 months ago, # ^ |   +56 I'm still not a master unfortunately :(
•  » » » 5 months ago, # ^ |   +43 How did you write "master" like that?
•  » » » » 5 months ago, # ^ |   +2 I'm sure you can see the html-code of my message to understand how I did it :)
•  » » » » » 5 months ago, # ^ |   +3
•  » » » » 5 months ago, # ^ |   +8 master will be masterIt means that CF support html code.
•  » » » » » 5 months ago, # ^ |   0
 » 5 months ago, # |   +15 My Final exam is going on... But I won't miss div-3.. Div-3 is love..
 » 5 months ago, # |   +59 Vovuh's rounds are always good!
•  » » 5 months ago, # ^ |   +27 Yours are also good.
•  » » » 5 months ago, # ^ |   +47
•  » » 5 months ago, # ^ |   +143 Comment from Div3 #579 Now tell Codeforces isn't ratist :c
 » 5 months ago, # | ← Rev. 2 →   +1 Div 3 rounds are better than "Educational rounds" in teaching the most valuable skill for Codeforces, namely SPEED.
•  » » 5 months ago, # ^ |   +3 Depending upon what your purpose. If you have high rating is seem not :)) But I like Div3 rounds too :3
 » 5 months ago, # |   0 Hopefully we will get some interesting problem. And always thanks to Vovuh from arranging div3. Its always increase my rating. :)
 » 5 months ago, # |   0 Hopefully I will become back to expert soon. I have been very disappointing in myself recently.
 » 5 months ago, # |   0 First unrated contest for me. XD
 » 5 months ago, # |   +9 Hello,Guys. This is my first contest after a lot of time. I studied Quantic Math in this period. I think that I can beat majority of the Div3 contestants even tough I am at 1361. :)Letsssssss GOOOOOOOOOOOOOOOOOOOOOOOO
•  » » 5 months ago, # ^ |   0 LoOooOoOLoOOooOoLoOOoOoOOooOooOOLoOooOOoOOoOOL. ROFL. LMAO. You think majority of contestants can only solve less than 3 problems?↑that's just bullshitAll the best. The time I solved 5 problems I didn't really expected that. it was pure luck. one lucky contest will be enough to bring you up to specialist or even 1500+. Good luck and have fun! :)
 » 5 months ago, # |   +18 Note that this is Vovuh's round. It's likely to have problems with multiple queries. So guys, a notice for you, remember to clear the data of the last query before answering the queries!
 » 5 months ago, # |   0 Do I have to register to join this contest? (My current rating is under 1600)
•  » » 5 months ago, # ^ |   +8 Of course. You have to register if you want to take part in a contest. For those rating equal or more than $1600$, they will be registered "Out of competition" for Div.3 contests. That is, their rating will remain unchanged after the round and they won't be listed in the official standing board.
•  » » » 5 months ago, # ^ |   0 Alright, thanks for the information
•  » » 5 months ago, # ^ |   0 Yep
 » 5 months ago, # | ← Rev. 2 →   +40 I have a great idea! Make div3 rated for (blues,) purples and yellows but update ratings only if the delta is negative.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +1 Why don't do the same thing to blues? They are unofficial for div.3 as well :(
•  » » » 5 months ago, # ^ |   +6 sorry, I thought blues are also div3.
 » 5 months ago, # |   +1 Let's escape this division guys! :D
•  » » 5 months ago, # ^ |   -7 Goood luck, niggaaaaa!!!!
 » 5 months ago, # | ← Rev. 2 →   +1 Finally, not a Mathforces Round.
 » 5 months ago, # | ← Rev. 2 →   0 P.S Here was bad info
•  » » 5 months ago, # ^ |   0 I don't think you should write that during the round.
•  » » » 5 months ago, # ^ |   0 My fault
 » 5 months ago, # |   +2 D2 solution accepted with 1900msMe: heavy breathing for 14 hours
 » 5 months ago, # | ← Rev. 4 →   +36 Unofficial editorial by me.A (Chips Moving) ExplanationIt is easy to see that there is no way for even valued chips to move to odd positions without paying, and vice versa. Let's say there are E even valued chips and O odd valued chips. The answer is min(E, O). Codedef solve(N, A): count = [0, 0] for x in A: count[x & 1] += 1 return min(count) B (Bad Prices) ExplanationSince we want to know the minimum price in the future, lets iterate in reverse and keep track of it. When we are considering the i-th price, we already know the minimum price we saw. Codedef solve(N, A): ans = 0 low = float('inf') for x in reversed(A): if x > low: ans += 1 low = min(low, x) return ans C (Book Reading) ExplanationWe write K = floor(N / M) numbers, the numbers are f(k) = k * M % 10 for k = 1, 2, ..., K. These numbers f(k) must repeat every 10 instances of k, that is f(k) = f(k+10). Let k = 10 * q + r. We write q numbers of f(0), f(1), ..., f(9); plus another r numbers f(1), f(2), ..., f(r). Codedef solve(N, M): K = N // M q, r = divmod(K, 10) ans = q * sum(k * M % 10 for k in range(10)) ans += sum(k * M % 10 for k in range(1, r+1)) return ans D (Equalizing by Division) ExplanationFor each number i in reverse order, lets see if all numbers could equal i. To do this, we maintain at each number, an int[] count[i] of how many numbers reached here by 0, 1, 2, ..., 18 divisions of 2. Then, for a number i with some count, we can calculate if K numbers could equal i in a greedy way: count[0] of them got here in 0 divisions, count[1] of them got here in 1 division, etc. and see how many divisions we need to find K numbers.Afterwards, we divide the number i by 2, which increases the counts at count[i//2] appropriately. CodeLOGV = 19 MAXV = 200000 def solve(N, K, A): count = [[0] * LOGV for _ in xrange(MAXV + 1)] for x in A: count[x][0] += 1 ans = float('inf') for i in xrange(MAXV, 0, -1): bns = 0 todo = K for j, x in enumerate(count[i]): delta = min(todo, x) todo -= delta bns += delta * j if todo == 0 and bns < ans: ans = bns for j in xrange(LOGV - 1): count[i // 2][j + 1] += count[i][j] return ans E (Two Small Strings) ExplanationIts always possible. Consider the graph with nodes 'a', 'b', 'c' and all possible directed edges (even self edges). There are three types of edges: forward edges 'ab', 'bc', 'ca'; backward edges 'ba', 'cb', 'ac'; and repeat edges 'aa', 'bb', 'cc'. Our goal is to walk around this graph without touching the banned edges S or T.Evidently, if we don't ban forward edges, we will answer 'abc' * N. If we don't ban backwards edges, we will say 'cba' * N. So lets say we ban a forward edge and a backwards edge. Without loss of generality, we could say the forward edge banned is 'ab'. Then the backwards edge is 'ba' or 'cb' or 'ac', and we have an answer 'b' * N + 'c' * N + 'a' * N. Codefrom itertools import permutations def solve(N, S, T): def check(cand): return S not in cand and T not in cand if check('abcabc'): return 'abc' * N if check('cbacba'): return 'abc' * N if check('bbccaa'): return 'b'*N + 'c'*N + 'a'*N if check('ccaabb'): return 'c'*N + 'a'*N + 'b'*N if check('aabbcc'): return 'a'*N + 'b'*N + 'c'*N F (Unstable String Sort) Explanation (grindy)We have 2N — 2 inequalities S[P_i] <= S[P_{i+1}] and S[Q_i] <= S[Q_{i+1}]. For each inequality S[u] <= S[v], draw a directed edge from u to v. Notice if a path exists from u to v, it implies S[u] <= S[v] by transitivity. If a path exists from u to v and from v to u (ie., u and v are in the same strongly connected component), then S[u] <= S[v] and S[u] >= S[v], so the letters S[u] and S[v] must be equal.We can use Kosaraju's algorithm to find the strongly connected components. If there are less than K strongly connected components, the task is impossible. Otherwise, we could greedily fill the answer. Code (grindy)def solve(N, K, P, Q): P = [x - 1 for x in P] Q = [x - 1 for x in Q] graph = collections.defaultdict(list) rgraph = collections.defaultdict(list) for i in xrange(N - 1): graph[P[i]].append(P[i+1]) rgraph[P[i+1]].append(P[i]) graph[Q[i]].append(Q[i+1]) rgraph[Q[i+1]].append(Q[i]) # first dfs of kosaraju's seen = [False] * N visited = [] ENTER, EXIT = 0, 1 for start in xrange(N): if not seen[start]: stack = [(start, EXIT), (start, ENTER)] while stack: node, cmd = stack.pop() if cmd == VISIT: if not seen[node]: seen[node] = True for nei in graph[node]: stack.append((nei, EXIT)) stack.append((nei, ENTER)) else: visited.append(node) # second dfs of kosaraju's component = [None] * N for start in reversed(visited): if component[start] is None: stack = [(start, start)] while stack: node, root = stack.pop() if component[node] is None: component[node] = root for nei in rgraph[node]: stack.append((nei, root)) color = 0 ans = [None] * N for i in xrange(N - 1): x, y = P[i], P[i+1] if i == 0: ans[x] = color color += 1 if component[x] == component[y]: ans[y] = ans[x] else: ans[y] = color color = min(color + 1, 25) return "".join(chr(x + ord('a')) for x in ans)  Explanation (nice)If S[u] <= S[v], draw a directed edge from u to v.If x occurs before y in P, and x occurs after y in Q, then a path exists from both x to y and y to x, ie. x and y are in the same strongly connected component, so S[x] == S[y].We can use the above fact to deduce when there may still be P[j] with j > i such that S[P[i]] == S[P[j]]. Code (nice)def solve(N, K, P, Q): Qindex = {v: i for i, v in enumerate(Q)} far = -1 ans = [None] * N cur = 0 for i, p in enumerate(P): far = max(far, Qindex[p]) ans[p - 1] = cur if far == i: cur = min(25, cur + 1) if cur < K: return False return "".join(chr(x + ord('a')) for x in ans) G (Path Queries) ExplanationSort the queries. Every time q increases, we can only add edges to the graph under consideration. Therefore, we only need to maintain the correct answer every time we add an edge to the graph.Lets say the graph is a set of disjoint connected components, each component having s_i nodes (s for size). Then, the answer is sum_i (s_i choose 2), which we can write as (1/2)(sum_i (s_i)^2 — sum_i s_i) = (sum_i (s_i)^2 — N)/2. Thus, it is only necessary to maintain S_2 = sum_i (s_i)^2.Whenever we add an edge, if it connects two disjoint components with sizes sx and sy, then S_2 gets increased by (sx + sy)^2 — sx^2 — sy^2 = 2 * sx * sy. Codedef solve(N, M, edges, queries): # edges are u, v, w with 0 <= u, v < N parent = range(N) size = [1] * N rank = [1] * N S2 = [N] def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(x, y): xr, yr = find(x), find(y) if xr == yr: return parent[yr] = xr if rank[xr] < rank[yr]: xr, yr = yr, xr if rank[xr] == rank[yr]: rank[xr] += 1 sx, sy = size[xr], size[yr] size[xr] += sy S2[0] += 2 * sx * sy queries = sorted((q, i) for i, q in enumerate(queries)) edges.sort(key = lambda e: e[2]) i = 0 ans = [None] * M for q, qi in queries: while i < len(edges) and edges[i][2] <= q: union(edges[i][0], edges[i][1]) i += 1 ans[qi] = (S2[0] - N) / 2 return ans 
•  » » 5 months ago, # ^ | ← Rev. 2 →   +5 Is this official editorial? I am confused why its not part of the post.
•  » » » 5 months ago, # ^ |   +1 It’s unofficial
•  » » 5 months ago, # ^ |   0 Your implementation of G has failed on a test in which function find makes $O(n)$ recursive steps. I believe it would be better to use rank heuristics here.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 In G, can you please slightly explain more what are components of edge and how are we merging them with a small walkthrough of an example?
•  » » 5 months ago, # ^ |   0 what about self loop in E?you are not considering it
 » 5 months ago, # |   0 You should've seen my face when I found the "error";wrong submission: http://codeforces.com/contest/1213/submission/59756421hint: I removed the second if
 » 5 months ago, # |   +3 thanks Vovuh, it was cool contest.
 » 5 months ago, # |   0 Hopefully I go back to blue after open hacking is done!
 » 5 months ago, # | ← Rev. 2 →   0 How does my D2 pass in time ? 59740108. Isnt the complexity O(2*10^5 * K * log(K) ) while iterating the map since maximum numbers in map can be 2*10^5.Am I missing something or are the test cases weak ?
•  » » 5 months ago, # ^ |   0 Heh. I'm TLEing when I really shouldn't be.
•  » » 5 months ago, # ^ |   +1 No, your complexity analysis is wrong. The total number of elements across vectors in the map is at max Nlog(a[i]). So, you can say that your amortized time complexity is O(Nloga[i]logN)
 » 5 months ago, # | ← Rev. 2 →   0 Can anyone tell me why this Java solution for D2 is TLEing?: 59748534Shouldn't my solution be NlogN?
•  » » 5 months ago, # ^ |   +3 Java Arrays.sort() uses quicksort which is O(n^2) in worst case
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 Thanks! I was unaware that Arrays.sort() was so bad :(
•  » » » 5 months ago, # ^ |   0 Yes! I was able to verify that using Arrays.sort was the problem. I implemented mergesort, and it passed in 202 ms.
•  » » 5 months ago, # ^ |   +3 Arrays.sort in Java has a worst case running time of O(N^2). Converting your nums array to arraylist and using Collections.sort will make your code pass comfortablyhttps://pastebin.com/7UtCkk9u
•  » » 5 months ago, # ^ |   0 TLE before even beginning your algorithm: https://codeforces.com/contest/1213/submission/59763079
 » 5 months ago, # |   0 In B i accidently took array smaller than the limits so i tried to hack myself and i can't hack it can anyone help me?
•  » » 5 months ago, # ^ |   +1 Difficult to hack, only hackable if those memory locations are assigned next to OS memory locations. Keep trying :P
 » 5 months ago, # |   0 Can anyone tell me why my problem G TLE? I think it is O(N + M) (assuming that dsu operation is constant). Is there any infinite loop possibility?59762107
•  » » 5 months ago, # ^ |   +3 return (pr[x] == x ? x : root(pr[x]));this line needs to bereturn (pr[x] == x ? x : pr[x] = root(pr[x]));
•  » » » 5 months ago, # ^ |   0 omg :( silly meIm actually used to code it like this return pr[x] = (pr[x] == x ? x : root(pr[x])); thank you XD, i think im just too tired right now..
 » 5 months ago, # |   0 Sad for him :(((( be hacked 4 problems :<<
•  » » 5 months ago, # ^ |   0 Will those hack tests be included in final tests? What if my code fails in one or more of them?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yes, if you not pass all test, you will be hack. =)))))))))
•  » » » 5 months ago, # ^ |   +2 He is trolling lol. if your code fails in one of them, you get WA!
•  » » » » 5 months ago, # ^ |   0 Ah! makes sense.
 » 5 months ago, # | ← Rev. 2 →   +45 Problem E :
•  » » 5 months ago, # ^ |   0 36 cases o.0 It's so afraid :<
•  » » 5 months ago, # ^ |   -11 1st solution is of Ashishgup right??
 » 5 months ago, # | ← Rev. 6 →   0 Solution for Fif d occurs at i position in a and j position in b then it can be said that s[min(i,j)]=s[min(i,j)+1]=.......s[max(i,j)] make an array of intervals and add every [i,j] in it sort the array now merge the intervals which share common index if length of the interval array is less than k then it is NO else if length of the interval is greater than 26 then merge all intervals from 26th indexassign letters from a to each interval now sort intervals on the basis of their position in A.done AC
 » 5 months ago, # |   0 Why the following brute force solution for D1 gives WA in test 5. https://codeforces.com/contest/1213/submission/59764056. Can someone have a look.
 » 5 months ago, # | ← Rev. 4 →   -9 русский Я очень люблю раунды Vovuh. Спасибо! 1213E - Two Small Strings удивительно.Ελληνικά Μου αρέσουν πολύ οι γύροι Vovuh. Ευχαριστώ! 1213E - Two Small Strings είναι εκπληκτικό.English I really like the rounds Vovuh. Thanks! 1213E - Two Small Strings is amazing.Español Realmente me gustan las rondas Vovuh. ¡Gracias! 1213E - Two Small Strings es asombroso.
 » 5 months ago, # |   0 I try to use Golang to solve Problem B and complexity is O(Tn) but I got TLE. Can someone help me? Maybe Huge IO?
 » 5 months ago, # | ← Rev. 2 →   0 This summer vacation I'v joined lots of cf's contests. before the new term , I wish I could be an 'expert'.
 » 4 months ago, # |   0 I submitted this code for the D2, got a TLE in the 5th case. Can anyone help. (For all possible numbers, I recorded the numbers those could be formed from the original numbers of the array and the operations required for the same, rest is self explanatory) https://ideone.com/PKClD9