Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### maroonrk's blog

By maroonrk, history, 8 months ago,

We will hold AtCoder Regular Contest 111.

The point values will be 300-400-600-600-800-1000.

We are looking forward to your participation!

• +173

 » 8 months ago, # | ← Rev. 2 →   +21 For those interested, I'm planning to do a stream afterwards on Twitch.
•  » » 8 months ago, # ^ |   0 wrong URL
•  » » » 8 months ago, # ^ |   0 Thanks, fixed.
•  » » 8 months ago, # ^ |   0 please do on youtube
•  » » » 8 months ago, # ^ |   +5 I do upload to Youtube later: my channel
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Stream finished it was saying and disappeared . UPD : It was delayed by few minutes by AnandOza .
 » 8 months ago, # |   +20 I wish good luck to all participants able to solve a problem in this contest. :/
 » 8 months ago, # |   0 All the best to all the participants may you get a positive rating :D
 » 8 months ago, # |   +3 I give up!
 » 8 months ago, # |   +8 How to solve E?
•  » » 8 months ago, # ^ |   +1
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +8 How does that code work? The comments don't seem to be explaining it. count_solve// number of (x, y) : (0 <= x < n && 0 < y < k/d x + b/d) ll count_solve(ll n, ll k, ll b, ll d) { if (k == 0) { return (b / d) * n; } if (k >= d || b >= d) { return ((k / d) * (n - 1) + 2 * (b / d)) * n / 2 + count_solve(n, k % d, b % d, d); } return count_solve((k * n + b) / d, d, (k * n + b) % d, k); } EDIT: I guess this explains it, though I still don't really understand it :(
•  » » » » 8 months ago, # ^ |   +8 I think it can be derived from the formula: https://codeforces.com/blog/entry/65500#comment-496154.
•  » » » » » 8 months ago, # ^ |   0 Seems, that it's a different approach than described here.
 » 8 months ago, # | ← Rev. 2 →   0 How to solve A?
•  » » 8 months ago, # ^ | ← Rev. 4 →   0 If b divides a, then we can write (a/b) % p = a%(p*b) / b . Since we have to mod the floor value, we can ignore the condition above( b|a ). I used big mod to calculate a%(p*b) My submission
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 how did you know (a/b) % p = a%(p*b) / b it should be p*b??any source or explanation?
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 I don't know the source but it works. I found this so many days ago here.
•  » » 8 months ago, # ^ |   0 Find modulo result of (10^N) with (M^2). The result floor divided by M is the answer.
 » 8 months ago, # |   +20 To me, B was easier then A. How to solve A?
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 $Answer =\frac {(10^N\%M^2 - 10^N\%M)}{M}$ as we know the property $\lfloor \frac{\lfloor \frac{A}{B} \rfloor }{C} \rfloor = \lfloor \frac{A}{B*C} \rfloor$ Basically you want to calculate A $A = \lfloor \frac{10^N}{M} \rfloor - \lfloor \frac{10^N}{M * M} \rfloor * M$ let $\lfloor \frac{10^N}{M} \rfloor = Q$ and $\lfloor \frac{10^N}{M*M} \rfloor = Q^\prime$ we know that $10^N = Q * M + R$ $Q = \frac {10^N - R}{M}$ $10^N = Q^\prime * M^2 + R^\prime$ $Q^\prime = \frac {10^N - R^\prime}{M^2}$ So, $A = Q - Q^\prime * M$ $A = \frac{(10^N - R) - (10^N - R^\prime) }{M}$ $= \frac{R^\prime - R} {M}$ $=\frac {(10^N\%M^2 - 10^N\%M)}{M}$
•  » » » 8 months ago, # ^ |   +3 Will you please explain your solution.
•  » » » » 8 months ago, # ^ |   +35 Imagine $10^n$ in base $m$ and you can see the answer is the second last digit.
•  » » » » 8 months ago, # ^ |   +19 $10^n = m*k + r_1$$(10^n - r_1)/m = k$$k = \left \lfloor \frac{10^n}{m} \right \rfloor$ $r_2 = k \mod m$$k = m*k_2 + r_2$$(10^n - r_1)/m = m*k_2 + r_2$$10^n = (m^2)*k_2 + r_2*m + r_1$$r = r_2*m + r_1$$10^n = (m^2)*k_2 + r r = r_2*m + r_1$$answer = r_2 = (r - r_1)/m$$answer = r_2 = ((10^n)\%(m^2) - (10^n)\%m)/m$
•  » » » » » 8 months ago, # ^ |   0 how is r = ($10^n$) % ($m^2$) ???
•  » » » » » » 8 months ago, # ^ |   0 We have assumed r = r2*m + r1 right When you put this thing in . The equation will look like 10^n = k2*m^2 + r. That means when you divide 10^n by m^2. Then it will leave remainder r and quotient k2. That's why the same Hope it helps
•  » » » » 8 months ago, # ^ |   0 $\frac{10^n}{m}\bmod m=\frac{10^n\bmod m^2+k*m^2}{m}\bmod m$Meanwhile, $\frac{k*m^2}{m}\bmod m=0$Then the answer is $\frac{10^n\bmod m^2}{m}\bmod m$
•  » » » 8 months ago, # ^ |   0 great！
•  » » 8 months ago, # ^ |   +1 let y be the answer(0 <= y < M), then the condition is: ( 10N — (10N)%M — y*M)%(M2) = 0 my prooflet 10N = q*M + r we want q%M. Let this be y So q = q1*M + y Multiply M both sides So q*M = q1*M2 + y*M implies: 10N — r = q1*M2 + y*M OR 10N — r — y*M = q1*M2 As q1 is integer, hence above condition.Now how to solve B??
•  » » » 8 months ago, # ^ |   0 Ty, now i think im able to understand.
•  » » » 8 months ago, # ^ | ← Rev. 4 →   0 Create a graph of colors and keep deleting vertex with degree eguals to 1. In the end the answer is the number of vertex deleteds plus the remainders with degree greater then 1. Any vertex wich has degree equals to one, has only one chance to be chosen. In the end of the process of retiring these vertex, vertexes that have degree bigger then 1 can be put in a cycle that make they be chosen.I don't know how explain better, my poor english.My submission: 19286958
•  » » » » 8 months ago, # ^ |   0 your idea was very clear of showing up the color that occurs once(degree 1) and remove then from graph now consider others. but please would you like to explain what editorial said i am unable to relate it with this.
•  » » » » » 8 months ago, # ^ | ← Rev. 3 →   0 Every conected component with the number of edges greater or equals than the number of vertex has at least one cycle, so in the process of deleting vertex of degree 1 in this component , it will remain just vertexes with degree greater than 1, so all vertex of the component can be chosen.In the case of there's no cycle in the connected component (when number of edges is the number of vertex minus 1), one vertex will remain without be chosen.I think this is the way the two solutions are linked.
•  » » » 8 months ago, # ^ |   +3 Amazing proof!!
•  » » » 8 months ago, # ^ |   +3 Make a graph with numbers on cards as nodes and edges as cards. For each connected components, count the number of edges it has (repeated is counted twice, vertices of components only once). If number of edges for a component is greater than equal to the number of vertices for the component, then we can take all vertices as numbers on cards. Otherwise we can only take (number of vertices — 1) for the component as contribution to the answer.
•  » » » » 8 months ago, # ^ |   0 please would you like to explain what editorial said i am unable to relate it with yours explanation neither i understood it.
•  » » 8 months ago, # ^ |   +25 I felt A took more thinking than B and C and D
 » 8 months ago, # |   +75 Wow, I spent an hour trying to figure out how to calculate the sum of floors in E, and it turns out that Atcoder contestlib has a function to do exactly that???
•  » » 8 months ago, # ^ |   +13
 » 8 months ago, # |   -8 can anyone please explain what is wrong with this solution to D.
•  » » 8 months ago, # ^ |   +8 consider a single loop of nodes. your set of edges would contain 1 extra edge from the dfs root to one of its children
 » 8 months ago, # |   0 I am wondering why my solution to B is incorrect.My idea: build a graph using $N$ nodes as cards and some other nodes as colors. Connect an undirected edge between two kinds of nodes when a card has a color on its either side.Then I tried Dinic but got TLE. I thought of a linear method but it got 13 WAs. My code is Here, could anyone found what the problem is?
•  » » 8 months ago, # ^ |   0 I managed to squeeze Dinic in by first removing all cards that connect to a colour that only appears once and adding the number of removed cards to the max flow. https://atcoder.jp/contests/arc111/submissions/19287109
•  » » » 8 months ago, # ^ |   +5 Changing Dinic to Push Relabel makes it run much faster in only 316 ms :PSubmission
•  » » » » 8 months ago, # ^ |   0 Wow. That's much faster. I wonder if Push Relabel is fast enough to work without this optimisation.
 » 8 months ago, # |   +164
•  » » 8 months ago, # ^ |   +13 Could you elaborate? This is wa, isn't it?
•  » » » 8 months ago, # ^ |   +18 Probably judge solution is incorrect. I guessed some common pitfall and got AC.
•  » » » » 8 months ago, # ^ |   +89 Ok I got it, it's like you answer the question in the title, ok haha funny
•  » » 8 months ago, # ^ | ← Rev. 2 →   +45 We found this during the contest :)Maybe you were glad when you found the title "Do you like query problems?", then opened it, and ...Thank you for participation!
•  » » » 8 months ago, # ^ |   +25 xdI liked it even though it was not a query problem. Thank you!
 » 8 months ago, # |   -11 Can anyone please explain the time complexity of D without the constraint that guarantees the existence of a solution to me? From the editorial of D, it is $O(N+M+\frac{N(N+M)}{\sigma})(\sigma:wordsize)$ but I don't know why.
•  » » 8 months ago, # ^ | ← Rev. 5 →   +6 Soln remains the same. The additional step is checking if the found soln is correct. Given a directed graph, count no of nodes reachable from a particular node. That wordsize is a hint for bitsets. SpoilerCompress SCCs. It's a DAG now. dp[i][j] is true if j is reachable from it. Maintain bitsets for dp[i]. You can solve it in topological order of DAG.Upd: To the ones downvoting above comment. It wasn't obvious. I had the same doubt when I first read this.
•  » » » 8 months ago, # ^ |   0 I completely forgot that this task gave $c_i$ for every $1 \le i \le N$ so that I was always thinking about the way to check if the graph was strongly connected. That's why I didn't understand this time complexity.Anyway, thanks a lot for your help!
 » 8 months ago, # |   +4 Can somebody explain how to get the idea that problem B can be solved by transforming it into a graph problem. I could never think that the problem relates to graph. Thank you.
•  » » 8 months ago, # ^ |   +3 For me, at first I had a wrong idea. But eventually got the solution. First, I thought for every card I can choose only one color — (a or b). May be I could solve it using bicoloring. So, started drawing a graph. And eventually realized it wasn't a bicoloring problem and found the solution that I need to check only if there's any cycle.
•  » » » 8 months ago, # ^ |   0 why to apply graph i dont understand we have to find max color showing on one side so can not it be like this https://atcoder.jp/contests/arc111/submissions/19280968i know its wrong but why what i am not getting
•  » » » » 8 months ago, # ^ | ← Rev. 3 →   0 Check this input 3 1 2 1 3 1 3 Your solution gives 2. But you can take colors 2, 1, 3. So ans should be 3. 4 1 2 1 3 1 4 3 4 AC Ouput: 4 (2, 3, 1, 4)
•  » » » » » 8 months ago, # ^ | ← Rev. 4 →   0 Can you give some test cases which fails my code. I try to solve it using SET but failed 2 tests. But could not figure out what cases it fails.  N = int(input()) s = set() for i in range(N): a, b = list(map(int, stdin.readline().split())) s.add(a) s.add(b) print(min(N, len(s))) 
•  » » » » » » 8 months ago, # ^ |   0 5 1 1 2 2 1 2 3 4 3 5 AC Output: 4
 » 8 months ago, # |   0 What was difficulty of todays problems in terms of CF rating ?
 » 8 months ago, # |   0 can't we solve problem B using DP??
 » 8 months ago, # |   +86 Problem E's maker has no wood!
•  » » 8 months ago, # ^ |   +21 不讲武德 :)
 » 8 months ago, # |   0 Problem C is really amazing. Learnt a lot from it!!
 » 8 months ago, # | ← Rev. 3 →   +5 I just want to note that the final %m in the solution given at the end of the editorial for problem A is unnecessary.
 » 8 months ago, # |   0 can somebody explain why is this getting runtime error?https://atcoder.jp/contests/arc111/submissions/19387114
•  » » 8 months ago, # ^ |   +9 a,b <=400000Array visited[200000] is to small.
•  » » » 8 months ago, # ^ |   0 Damn i always forget to change that..thanx man ur the best this is like 5th time u helped me out :)
 » 8 months ago, # |   +8 in my opinion, problem F should not have queries type 2