Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

### rng_58's blog

By rng_58, history, 12 months ago, ,

AtCoder Grand Contest 032 will be held on Saturday (time). The writers are sugim48 and camypaper.

This is the second GP30-rated contest in this season — see this post for details.

Contest Announcement

Contest duration: 110 minutes

The point values will be announced later.

Let's discuss problems after the contest.

• +172

 » 12 months ago, # |   0 Why is it one hour later than usual?
•  » » 12 months ago, # ^ |   +11 There's some local contest before that.
 » 12 months ago, # |   -109 rng_58Please prepone the contest by 20 mins since the last 20 minutes are clashing with the first match of the Indian Premier League (CSK vs RCB) which means most cricket lovers will not be able to do the contest.Thanks in advance for your kind co-operation.
•  » » 12 months ago, # ^ |   +41 I have a solution. Go with whatever comes first in your priority queue.
 » 12 months ago, # |   +12 Who is Makki0? I guess (99% sure) that he is a password-hacking cheater, because I've encountered similar username 0ahmad0makki0 hacking strong-player account in codeforces contests. Refer to the comment of 300iq
•  » » 12 months ago, # ^ |   -24 but how its possible, codeforces and atcoder both use https security , its not easy to hack paswsword
•  » » » 12 months ago, # ^ |   +8 Clearly you don't know anything about hacking. For example, here are instructions for hacking an ATM: get a car, a laptop and a pickaxe drive to the ATM break it open with the pickaxe load the money to the car and get away In case you're asking what the laptop is for: what sort of hacker doesn't have one?
•  » » » » 12 months ago, # ^ |   -15 what u said , i didnt understood . so , anyone can hack anyone's password ?
•  » » » » » 12 months ago, # ^ |   0 Phishing, lists of leaked passwords, guessing, etc.
•  » » » » » » 12 months ago, # ^ | ← Rev. 2 →   -28 yes , i also did hacking beginners course , i am not an expert or not ever near to it , but phishing only happens when u urself submit ur paswword to some fake sites . they save ur password . regarding guessing , brute force will take years , if ur password is strong , and https is much secure . thats why i am surprised as the same guy hacked dotorya yesterday at edu. round , now today .
•  » » » » » » » 12 months ago, # ^ |   +8 only happens when u urself submit ur paswword to some fake sitesif ur password is strong You might as well expect that if you tried competing here in rating contests you'd no doubt crush tourist.
•  » » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   -33 lol . xd what u mean
•  » » » » » » » 12 months ago, # ^ |   +4 Maybe that hacker hacked passwords from CodeForces and users had same passwords in AtCoder or vice-versa.
•  » » » » » » » » 12 months ago, # ^ |   0 yaa , u may be right .
•  » » » » » » » » 12 months ago, # ^ |   +3 How exactly does that happen? How can an attacker who gains access to CodeForces' databases actually get users' passwords? Aren't these things usually hashed before they are stored?Sorry if it's a dumb question, I don't know too much about computer security.
•  » » » » » » » » » 12 months ago, # ^ |   0 He got a database of leaked passwords.
•  » » » » » » » » » 12 months ago, # ^ | ← Rev. 3 →   -18 Right, but I guess the question I'm asking is: Why does there even exist a database of unhashed user passwords? What would be the origin of this database?Edit: I'm probably not explaining myself well, based on the response. To my understanding, a website like Google does not actually store anything like "Kognition — 'password' " in their database, but instead will have something like "Kognition — 3f930a9bc27d", corresponding to the hash of my password, which presumably gets hashed client-side. So, my actual password should never be stored anywhere on their servers. Is this understanding correct? If not, what is the misunderstanding? If so, then why exactly is there a database of unhashed Codeforces passwords?
 » 12 months ago, # |   0 How to solve C and D?
•  » » 12 months ago, # ^ |   +1 D: one can see that rotation left is just moving a single element to the right and vice versa. All untouched elements must represent an increasing subsequence. Now we can calculate dp[i][j] which stands for the minimal cost of rearranging all elements which are initially at the first $i$ positions in such a way that the rightmost untouched element among them is the $j$-th.C: I did the following: remove all vertices with degree $2$ one by one, ignoring loops, then see if num_loops + remaining_edges / 2 is at least $3$. Maybe I did something else, I don't remember, my brain has decided to forget this solution.
•  » » » 12 months ago, # ^ |   0 Wait, quadratic time complexity was enough in D? I knew that the problem asking for the min. number of elements to move is $O(N\log)$, so I didn't check the constraints at all and just solved it in $O(N\log)$.
•  » » » » 12 months ago, # ^ |   0 Can you tell that solution or share some resources?
•  » » » » » 12 months ago, # ^ |   +5 See my solution. I'm just using an interval tree with operations "get minimum of range", "put a fixed value at some position" and "increment all values in a range by x".
•  » » » 12 months ago, # ^ |   0 Do you know why this doesn't work for D:dp[i][j] is the cost to complete the sorting if you know that there are first (1, 2, .... i) brought to the very beginning in sorted way and numbers (j, j+1, .., n) are brought to the very end in sorted way. dp transitions are either bring the number i+1 to left ( with cost A if it is not already in the left) + dp[i+1][j] or bring the number j-1 to the right (with cost B if it is not already in the right) + dp[i][j-1]???my code
•  » » » » 12 months ago, # ^ |   +3 As far as I remember, the last sample test is a counter-test to this solution
•  » » » » 12 months ago, # ^ |   +3 Try the following test case: 6 1 1 3 1 2 5 6 4 
•  » » 12 months ago, # ^ |   0 C.Notice that circuits combined have to be an Euler cycle. Check for that. Now we know that all vertices have even powers. If there's a vertex with power 6+. Answer is yes. Else if there're at least 3 vertices with power 4, answer is yes. Else if there's only one vertice with power=4, answer is no. Else we have two vertices with power=4 and every other vertex has power=2. Collapse those and we have one of two cases. 1 2, 1 2, 1 2, 1 2,. Answer is no 1 1, 1 2, 1 2, 2 2. Answer is yes. Note that you don't have to collapse graph explicitly. It's enough to try walking from one of the power 4 vertices and see if we can loop back without hitting other.
•  » » » 12 months ago, # ^ |   0 Could you please explain why the graph must be eulerian ?Statement says "Determine if three circuits (see Notes) can be formed using each of the edges exactly once."What if we take a correct graph G, and add a new vertex connected with a random vertex from G. Now the new G' is not eulerian because the new vertex has degree 1, but it still has three circuits.What I am missing ?
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   +3 Determine if three circuits (see Notes) NotesA circuit is a cycle allowing repetitions of vertices but not edges.Take a look at 1st cycle. As graph is connected it has a shared vertex with some other cycle. We can merge them. Repeat and receive eulerian cycle.
•  » » » » » 12 months ago, # ^ |   +5 Yea, also I think the key here is that it forces us to take every edge exactly once. With that constrain, probably the new edge (in my example) is never used by any circuit and this is probably the reason that the graph must be eulerian.I think I got it, thank you.
•  » » » » 12 months ago, # ^ |   +3 using each of the edges exactly once
•  » » » » » 12 months ago, # ^ |   0 Yea, exactly. Thank you !
 » 12 months ago, # |   +36 AGC is a puzzle contest only for genius, not a programming contest.... by the way, can you send me a problem list containing a lot of problems about determining whether it's possible to make something from a graph (by looking at degrees or something)? I always have no idea to solve them.
•  » » 12 months ago, # ^ |   -36 but tourist and ksun solved them including petr
•  » » 12 months ago, # ^ |   0 You may like problem J from here: https://codeforces.com/gym/101341But it is not very hard, Div 1 B/C I'd say.
•  » » 12 months ago, # ^ |   -103 lol , what type of red coder u r ,are u cheater
•  » » » 12 months ago, # ^ |   +27 No. You are.
•  » » » » 12 months ago, # ^ |   -90 first , recover your lost mental balance after today's contest .
•  » » 12 months ago, # ^ |   +10
•  » » 12 months ago, # ^ |   0 Lol, I hope you were not serious and wrote this just to trigger me and some other users.
•  » » » 12 months ago, # ^ |   0 rng_58 just told me that AtCoder is just about mathematics puzzle ability from red (where ARC becomes unrated)
•  » » » » 12 months ago, # ^ |   -57 lol , who r u , that rng_58 will call you and tell you.
 » 12 months ago, # | ← Rev. 2 →   +18 How to solve A, lol...I squeezed (2ms running time tho) backtracking but couldn't come up with a solution.
•  » » 12 months ago, # ^ |   +9 I did the reverse operation. You start from the moment N and greedily remove the largest element where b[i] == i. This is optimal, because size of array will decrease so its always preferable to remove the largest possible element you can.
•  » » 12 months ago, # ^ |   -37 you cant solve a , its quite surprised , almost a red coder u r
•  » » » 12 months ago, # ^ |   +8 That's what fascinates me most about atcoder contests. In many cases problems aren't easily observable, yet contests are really interesting.
•  » » » » 12 months ago, # ^ |   -10 solutions are too short also . upto d
•  » » 12 months ago, # ^ |   +6 ObservationIf, for any i, b[i] > i, it's not possible (b[i] would have to be inserted at position b[i] and then travel left, which is not possible). SolutionLet's say that in the last step we inserted b[i]. First of all, b[i] == i. Also, if we also had b[j] == j, j > i, then in the second-to-last step we'd have b[j-1] == j which is contradictory with the observation above. So, in the last step we had to use the last i such that b[i] == i. Now recurse.
 » 12 months ago, # |   -10 Quite disappointed with my performance here, I spent about half of the contest on B until I saw the pattern and got an unnecessary WA on C — not because I missed a case, but because I had a small bug and didn't customtest that one case where it appeared.Still, D with costs A and B instead of 1 and 1 is well-known (sort by moving elements) and this version isn't much harder — I solved it in about 5 minutes, complete with copypasting an interval tree and making small changes.
 » 12 months ago, # |   +5 Nice problems, as always.I think F is hard already for $n \le 8$. I wanted to solve it with dp similar to tourist's atcoder problem about arcs and then run Berlekamp–Massey. I didn't finish in time and wasn't even close. But would that work?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 That seems like a really wishful thinking to me. Why would such a sequence form a linear recursion?
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 When something is a fraction, numerator and denominator are often some complicated polynomials. But I understand it can also be something of magnitude $n!$ easily. Then BM doesn't work.
 » 12 months ago, # |   +29 Wow, you've used the same colors in the editorial of E as I did while solving this! photo
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Editorial says that, we can rearrange the left pairing and get the right one without increasing the larger ugliness of those two pairs.Now, suppose the larger ugliness is formed by the red pairing then its ugliness is (if we denote the four numbers by $w, x, y, z$ so that $w \le x \le y \le z$ and $w$ pairs with $y$, $x$ pairs with $z$) $x + z - M$ (in the left pairing). Then when we reassign the pairing as shown in the right one, the ugliness of the blue pairing does not increase like the red one's does not decrease; also now the larger ugliness is formed by the red pairing, it also remains a "red" pairing since $M \le x + z \le y + z$. On the contrary, the larger ugliness might have increased (since it's less than or equal), the red one's. So, everything is contradicting with each other unless I am missing something (Undeniably, I am). Can you please tell me, what am I missing :(?
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +10 the red pairing of the right side has smaller ugliness than the blue pairing of the left side, so the right one always have smaller or equal ugliness than the left one. UPD: Not blue side, left side.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 What do you mean by blue side?
•  » » » » » 12 months ago, # ^ |   0 Left side, sorry.
 » 12 months ago, # |   0 Editorial of problem F said that "A simple calculation shows that when we divide a segment into $k$ parts at random, the expected length of the shortest part is $\frac{1}{k^2}$ times the length of the original segment.But I feel I'm not good at simple calculation.. how to prove it?
•  » » 12 months ago, # ^ | ← Rev. 2 →   +25 Wlog assume that the initial segment is $1$ unit length. The probability that all parts are greater than or equal to $s$ is $(1 - ks)^{k-1}$ (since we kinda divide a segment of length $1 - ks$ and then expand each part by $s$). Thus the expectation is $\displaystyle \mathsf{E}\int_0^1I(len\ge s)\,ds = \int_0^1\mathsf{P}(len\ge s)\,ds = \int_0^{1/k}(1 - ks)^{k-1}\,ds = \frac{1}{k}\int_0^{1}(1 - x)^{k-1}\,dx = \frac{1}{k^2}$qed.
•  » » » 12 months ago, # ^ |   -48 how can one ccome with such maths , many dont know formula . why atcoder contest so inclined on maths side . its like International maths olympiad
•  » » 12 months ago, # ^ |   +20 Here's a weird combinatorial argument, not sure if it's correct.Consider $k-1$ random numbers in $[0,1]$, and say they are $x_1, \dots, x_{k-1}$ after sorted. Let $x_0 = 0$ and $x_k = 1$. Additionally, pick a random number $y$ in $[0,1]$. The expected value of the minimum segment length is equivalent to the probability that $y \le x_{i+1} - x_i$ for all $i$.First, we must have $y \le x_i$ for all $i$, which happens with probability $\frac{1}{k}$.After this, we can look at the numbers $y - x_0, x_1 - y, x_2 - x_1, \dots, x_k - x_{k-1}$. Given that $y \le x_i$ for all $i$, the distribution on these values is the same distribution as splitting a segment of length $1$ into $k+1$ parts. In order for $y$ to be at most $x_{i+1} - x_i$ for each $i$, $y$ must be the minimum of the elements $y, x_2 - x_1, \dots, x_k - x_{k-1}$, which happens with probability $\frac{1}{k}$. (We already know that $y \le x_1 - x_0 = x_1$.)Now we can multiply these probabilities together to get $\frac{1}{k^2}$.
•  » » » 12 months ago, # ^ |   -49 ABRB , what u have written , from where do u learn these things , so hard combinatorics .u r very brilliant in maths . https://www.imo-official.org/participant_r.aspx?id=23293
•  » » » 12 months ago, # ^ |   0 Wow, that's great, I've never seen combinatorial argument for that
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 "The expected value of the minimum segment length is equivalent to the probability that $y \leq x_{i+1} - x_i$ for all $i$."Why exactly is this true? It sort of makes sense to me intuitively, but it's the only part of the argument I'm having trouble justifying myself.
•  » » 12 months ago, # ^ |   0 I remember that one Petrozavodsk problem asked basically that what is that value for a particular k and many people, including me, just did a Monte Carlo for k=3,4,5 and formula became obvious :p
 » 12 months ago, # |   +53 I don't know why people complain about slow convergence of AtCoder rating. Not only my AtCoder rating converges, it converges towards my Codeforces rating!
 » 12 months ago, # |   +8 Testcases for C is not strong.During the contest,I came up with a wrong solution:Consider graphs that only contains vertices of degree 4 or 2.I find an Eulerian circle and check if there exists something like A...A...B...B in the circle.In fact,it can be easily hacked.Input: 9 12 9 1 3 9 8 3 2 8 7 2 1 7 6 1 3 6 5 3 2 5 4 2 1 4 It should be Yes,but my submission output No.My submission
•  » » 12 months ago, # ^ |   +5 I guess it's because there's a lot of cases and there aren't enough tests for some case to break every solution that only fails this case; also because the answers are just yes/no (I really don't like yes/no outputs). So far, I've noticed that Atcoder doesn't go for really crazy strong tests where a wrong solution probably fails 40 of them, but adds a few tests that break specific wrong ideas that shouldn't pass. It's possible to get lucky, but it's usually not worth the time.
•  » » » 12 months ago, # ^ |   0 Generally speaking, it's impossible to come up with all wrong solutions in advance. Your case can be handled by just counting the number of vertices of degree 4 anyway, so your solution doesn't look very natural.
•  » » » » 12 months ago, # ^ |   0 Well, sure, as long as what really shouldn't pass doesn't pass.
•  » » 12 months ago, # ^ |   0 In my impression, your solution depends on edge order.This sort of wrong solution is tough to defend. What's happen if you try to shuffle edge order and find eulerian circuit as long as time allows?
•  » » » 12 months ago, # ^ |   0 Note that the "outer2" loop is a leftover from an unsuccessful attempt to apply this shuffling approach :)In this solution this loop is executed exactly once, and the solution is basically the same as the editorial.
•  » » » » 12 months ago, # ^ |   0 I'm terrible at code reading :( I saw that you try to shuffling approach, so I thought you passed with this approach...
 » 12 months ago, # |   0 how to solve first problem ?
 » 12 months ago, # |   0 For problem D — Rotation Sort, I checked some AC codes, and I found codes similar to the code below. But I don't understand, could anyone help me understand the code plz. fill(dp+1,dp+n+1,INF); dp[0]=0; for(ll i=1;i<=n;i++) { ll cntx=0,cnty=0; for(ll j=i-1;j>=0;j--) { if(p[j]
 » 12 months ago, # |   0 In problem C, I counted how many times a visited vertex gets visited again while running the Euler cycle making algorithm (I guess it's called Hierholzer's algorithm). And if the count is greater than or equal to 3 then output yes, no otherwise. This should be correct, but it's giving wrong answer. Can anyone tell me where am I wrong?
•  » » 12 months ago, # ^ |   +13 Consider the case where you have two nodes of degree 4 (we'll call them $A$ and $B$), and all other nodes of degree 2.There are basically two types of graphs that can be a result of this: one where $A$ has it's own circuit, $B$ has it's own circuit, and there is a third circuit containing both $A$ and $B$. The other kind of graph has two disjoint circuits, both containing $A$ and $B$. The Euler tour will visit $A$ and $B$ the same number of times (note that the number of times a vertex gets revisited is just it's degree minus one), but the answers differ in both of these graphs.