rng_58's blog

By rng_58, history, 5 years ago, In English

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.

  • Vote: I like it
  • +172
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is it one hour later than usual?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    There's some local contest before that.

»
5 years ago, # |
  Vote: I like it -109 Vote: I do not like it

rng_58

Please 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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    I have a solution. Go with whatever comes first in your priority queue.

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    but how its possible, codeforces and atcoder both use https security , its not easy to hack paswsword

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Clearly you don't know anything about hacking. For example, here are instructions for hacking an ATM:

      1. get a car, a laptop and a pickaxe
      2. drive to the ATM
      3. break it open with the pickaxe
      4. 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?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -15 Vote: I do not like it

        what u said , i didnt understood . so , anyone can hack anyone's password ?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Phishing, lists of leaked passwords, guessing, etc.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it -28 Vote: I do not like it

            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 .

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              only happens when u urself submit ur paswword to some fake sites

              if ur password is strong

              You might as well expect that if you tried competing here in rating contests you'd no doubt crush tourist.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +4 Vote: I do not like it

              Maybe that hacker hacked passwords from CodeForces and users had same passwords in AtCoder or vice-versa.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  He got a database of leaked passwords.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                  Rev. 3   Vote: I like it -18 Vote: I do not like it

                  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?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C and D?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)$$$.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you tell that solution or share some resources?

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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".

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        As far as I remember, the last sample test is a counter-test to this solution

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Try the following test case:

        6 1 1
        3 1 2 5 6 4
        
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        Determine if three circuits (see Notes)

        Notes

        A 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.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        using each of the edges exactly once

»
5 years ago, # |
  Vote: I like it +36 Vote: I do not like it

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.

»
5 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

How to solve A, lol...

I squeezed (2ms running time tho) backtracking but couldn't come up with a solution.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -37 Vote: I do not like it

    you cant solve a , its quite surprised , almost a red coder u r

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      That's what fascinates me most about atcoder contests. In many cases problems aren't easily observable, yet contests are really interesting.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Observation
    Solution
»
5 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    That seems like a really wishful thinking to me. Why would such a sequence form a linear recursion?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Wow, you've used the same colors in the editorial of E as I did while solving this!

photo
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Editorial says that, we can rearrange the left pairing and get the right one without increasing the larger ugliness of those two pairs.

    Screenshot-from-2019-03-27-10-01-25

    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 :(?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      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.
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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}$$$.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, that's great, I've never seen combinatorial argument for that

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      "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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 years ago, # |
  Vote: I like it +53 Vote: I do not like it

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!

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, sure, as long as what really shouldn't pass doesn't pass.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    see this https://atcoder.jp/contests/agc032/submissions/4672371

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm terrible at code reading :( I saw that you try to shuffling approach, so I thought you passed with this approach...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve first problem ?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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]<p[i]) dp[i]=min(dp[i],dp[j]+cntx*b+cnty*a);
        if(p[j]<p[i]) cntx++; else cnty++;
    }
}
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.