Asymmetry's blog

By Asymmetry, 3 years ago, In English
Tutorial is loading...

Prepared by Asymmetry

Tutorial is loading...
Prepared by Markadiusz
Tutorial is loading...
Prepared by Asymmetry
Tutorial is loading...
Prepared by Markadiusz, Monogon and Asymmetry
Tutorial is loading...
Prepared by Markadiusz
Tutorial is loading...
Prepared by Markadiusz
Tutorial is loading...
Prepared by Asymmetry and Markadiusz
Tutorial is loading...
Prepared by Asymmetry
  • Vote: I like it
  • +70
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I think 1572C - Paint is actually just 2021 USACO Gold February P2 if you reverse time and apply operations "backwards." The USACO problem starts unpainted, but we can just subtract 1 from our answer in the USACO problem to get something equivalent to 1572C. Also, the operation in 1572C and USACO aren't exactly inverses of each other; namely, 1 USACO operation can do everything that 1 inverse 1572C operation can do, but the reverse does not hold. However, the cases in which the two operations aren't inverses shouldn't affect the answer and I am too lazy to prove it.

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

    They seem very simillar, but I think that the main difficulty of 1572C - Paint was using the fact that a color may appear at most 20 times.

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

I just wrote the following Hinted solution to Div1C/Div2E in response to this comment by Penguin07, since this editorial didn't seem to be published when I started. Since I know many people like hinted editorials, I will post it here now anyway.

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

    Thanks a lot for the explanation. I really didn`t understood anything in editorial, but your solution is nice and clear.

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

    looking for proof of first hint.

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

      I'm not sure I understand. As I don't make or use any claims anywhere about how to calculate the values I suggest in hint 1, there's nothing to prove.

      I was very careful about the repaint-before-joining concern, because I shared that concern. Off the top of my head, I'm not sure of a better way to prove that these aren't necessary than "This solution is optimal. Oh, look, it doesn't actually perform any non-joining repaints." (That's not to say that no easier proof exists!) Please let me know of any step where you think I may have inadvertently used this assumption, or any other.

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

        "This solution is optimal. Oh, look, it doesn't actually perform any non-joining repaints."

        This doesn't look valid argument to me. How can you look? As far as I understand, that dp calculation assume that you combine two or three subintervals. You can't claim that it's always two subintervals, because this thing should be proven. Then, in order to paint whole segment, you have to claim that you can paint first subinterval into first color, then second subinterval into second color, and if there is third subinterval, then color it into third color. Suppose you successfully painted first subinterval into first color. Why would we successfully color second subinterval into second color? It could possibly already have been messed by all previous actions over first subinterval? Because I think they could overflow bounds of first subinterval, and thus its coloring sequence now meaningless.

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

          It's pretty trivial: You repaint the second interval first. No recomposition step on interval $$$[i..j]$$$ will ever mess with pixel $$$i$$$ or any lower-numbered pixel. This can be seen as a slightly stronger version of Hint 4.

          EDIT: But I agree in hindsight that I should have provided more detail in the proof of hint 4, since there are a few ways to go wrong. I will add this to my original comment.

          EDIT2: This is done.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            I tried to make induction, but I stuck
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Right. The last operation doesn't work: In order to replace a 3-way merge efficiently, we need the right-most color to match the left-most color, and have no way to control the colors available in the right-most interval. The worst-case looks something like this:

              12 | 343 | 2
              22 | 343 | 2
              22 | 333 | 2
              22   222   2 
              

              To avoid this problem, I need to scrutinize and replace some operation that cannot result in a 3-way merge in $$$[i..j]$$$. Luckily, in any counter-example, there must be one: The operation that modifies pixel $$$i$$$. I've fixed/replaced the proof in Hint 4 to hopefully not be broken, and added a proof to Hint 6 as well.

              Let me know if you spot any other oversights.

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

                Well, I completely agree with proof in hint 4. You're genius! I was trying to prove anything for past three days with no luck. There is tricky order of induction though.

                About proof in hint 6
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Re: Proof of Hint 6: The recoloring of $$$M$$$ can't partially merge it with any other region, because that region is recolored later but $$$M$$$ is not.

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

                  In proof of hint 6 you say color c is color of M before repaint. But M itself is before repaint or after? Because before last repaint it could have shorter length. If it's before repaint, then it's how I thought initially in previous reply. If M is after last repaint and L and R is also after, then let S be before repaint. Then union of L, R and S is not whole interval. Whole interval is union of L, R, M. You provide sequence to paint union L, R, S.

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

                  I intended it to mean $$$M_\text{before}$$$, as otherwise "previously of color $$$c$$$" doesn't make a lot of sense. But actually, $$$M_\text{before} = M_\text{after}$$$, since it is impossible for the original sequence to later recolor any cell in $$$M_\text{after}$$$ without also recoloring every cell in $$$M_\text{before}$$$.

                  That said, this property of $$$M$$$ shouldn't matter: The induction hypothesis and the non-clobbering guarantees from Hint 4 apply to the intervals $$$[i..x-1]$$$ and $$$[y+1..j]$$$ even if they do not respect region boundaries. The important thing is that the non-repaintedness of $$$M$$$ prevents the original sequence from being able to share work between $$$L$$$ and $$$R$$$. (So, this proof does NOT work on a circle, for example.)

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

                  I just wanted to tell right before you made reply that I got it. But reason is different. By contradiction, in case it enlarged into $$$M_{after}$$$ by recoloring, then joined part will never recolored, and didn't colored with this action. Thus, it was recolored earlier — we found earlier action that did recolor never-recolored-afterwards segment. Thus, our initially considered action wasn't first one of kind. Contradiction with assumption that it was earliest.

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

here's a nice alternate solution to Div.1 E that comes up intuitively but is surprisingly hard to prove.

my solution (spoiler)
sike

Congratulations to tourist for winning the contest, and solving E with this solution that is very hard to prove!

fun fact

implementation: 129215696

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

For Div1 A, I think Topological sort isn't needed when we are using DP in DAG. We can just iterate on nodes in a random fashion and use DFS with DP to calculate the longest path

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

    Note that the process you've described simulates toposort. If a node v is reachable from node u, they either lay on the same cycle, or v belongs to a SCC reachable from u's SCC. In short, sometimes topologically sorting the graph explicitly is not necessary.

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

      Not necessarily. It will be topological sort if and only if we are picking the right root randomly. Example, we have edges from 1 to 2 and 2 to 3, then topological based DFS will always start from 1 whereas a random traversal can start from anywhere. And in this problem, the order in which you pick the nodes/roots isn't important

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

        As the order of nodes isn't important for calculation of our DP, we only need to calculate dp[x] after it is calculated for all the nodes that would appear later in the topological sorting of the graph, which is ensured by the DFS itself.

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

          That is the property of the DFS itself, and since it's pretty implicit, we don't need to mention the need of toposort like that, because highly likely that the readers of the editorial may relate it to the order of picking roots (which will obviously work, but an overkill)

»
3 years ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

This edge has weight 0 if a<b and 1 otherwise Shouldn't the weights be vice versa?

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

    why answer is 5? you can read them in one cycle 1,2,3,4,5.

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

    Thanks for pointing out that typo. It should be correct now.

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

I never believe that I will one day say this to a flow problem, but D (div 1) is great. After the contest I've talked to some people about it, and most of their thought processes involve somehow optimizing the finding-the-blocking-flow operation (which one of them apparently managed to do). I am glad to see that instead of some obscure trick written in Chinese/Polish/Russian paper #1257, the key to the solution lies in a simple observation. Kudos to the authors for coming up with such a nice problem.

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

Can anyone help me with the problem 1572A - Book?? My solution is giving wrong answer in test case 2. I have used topological sort.

My solution — 129302238

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

    IMO the problem is that for each chapter of the book (nodes if you suppose its a graph) you have to check all the ones on its require list. but you only check the last one in the topological order. since my solution is pretty much like yours, i recommend you to check it out: [](https://codeforces.net/contest/1573/submission/129306114)

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

      You were right. I was updating only for the last element of topological sort.

      Accepted solution (if anyone need) — 129310560

      Thanks a lot MOOONI

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

        Can you please explain what your dp vector stores? And, what this lines of code means

        int y;
                    if (nx < x) {
                        y = dp[x]+1;
                    } else {
                        y = dp[x];
                    }

        Thanks.

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

div1 A was really interesting!

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

If anyone solved Book (Div 2 C / Div 1 A) with the first approach mentioned in the editorial then can you please send me your code, I'm having a hard time understanding what is written. thanks!

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

    https://codeforces.net/contest/1572/submission/129340066

    I think you can refer mine

    below are comment on variables.

    set<int> lefts: contains chapters that are not read yet.
    set<int> reads: contains chapters that are readable.
    vector<int> resolves[n]; resolves[i] contains chapters that needs the chapter i to be read first.
    int need[n]: need[i] == #of chapters that must be read first before chatper i.
    
    bool hasNext: there's next chapter readable.
    
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in which we can find a matching with maximum cost and size at most k with for example one of the standard min cost max flow algorithms

Can someone please explain this part?

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

    Let's assume that after the reduction we are left with edges (1, 5), (4, 5), (4, 6), (2, 6), (2, 10). Then we can make a flow network like so and find min cost max flow from node S_0 to node T in it. Here the first value on an edge is its capacity and the second is its cost. I hope that you can figure out the general approach from this picture.

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

      How to prove that minimum cost always occurs when flow is k?

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

        It’s based on the fact that the weight of an edge $$$w(U, V)$$$ is the sum of the values of the two vertices $$$a_U + a_V$$$. Consider an augmenting path algorithm to calculate maximum weight flow/matching. In order to increase the size of the matching by one, we search for an augmenting path with maximum weight. For example, if edges (B, C) and (D, E) are in the matching, an augmenting path may be (AB), (BC), (CD), (DE), (EF). Its weight is $$$w(AB) - w(BC) + w(CD) - w(DE) + w(EF)$$$. This is equal to the sum of the values of its endpoints, $$$a_A + a_F \geq 0$$$. So, as k increases, the maximum weight of a matching of size k is non-decreasing.

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

Can anyone prove the optimality of the solution for div2 a?

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

    Well, consider taking a number 2079, so we have to make it 0, either by subtracting 1 or swapping positions. Now first we'll subtract 1, 9 times to make it 2070. After this we've to make 7->0, for this we'll need to subtract 1, 70 times but since we can swap 2 digits , so we'll swap 7 and 0. The main idea being getting every digit to the one's place so that we can make it 0 in min number of operations. For more clarity consider 10, we'll need to subtract 1, 10 times to make it to 00. And so the most optimal way is to swap 1 with 0 and then subtract 1 only once.

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

I think editorial is poorly written. And that's why I decided to write my alternative editorial with hints and proofs of tasks which I solved or upsolved. Only my solutions (alternative solutions not covered).

1573A - Countdown

Editorial

1573B - Swaps

Editorial

1572A - Book

Editorial

1572B - Xor of 3

Editorial

1572C - Paint

Editorial

1572D - Bridge Club

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

How is the time complexity of the first approach of 1572 — A Book O(nlogn) ? Please can someone explain.

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

    all chapters(n) are once added to set(logn) and removed from it(logn).

    so total O(nlogn + nlogn) = O(nlogn)

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

      Thanks a lot.

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

      Just to confirm, logn because we are using sortedset? I tried to find some submission which has implemented the first approach but couldn't so not sure.

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

        yes logn because of using sorted set

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

My Submission

Edit: this has been resolved

Here I'm getting wrong answer on test 2, its failing in conditions like 1 5 0 2 1 3 1 1 4 1 2 3 5 3 1 2 3 required answer 3 my answer 2

If any of y'all are able to find out why my code is failing, do lemme know! thanks!