chokudai's blog

By chokudai, history, 7 weeks ago, In English

We will hold Caddi Programming Contest 2021(AtCoder Beginner Contest 193).

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

»
7 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

Looking forward to facing some great problems

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

OK, seems greedy is wrong for F....

What's the correct solution?

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

    How to solve E ?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't solve it neither...

      there's little time after solve 4 problems, so I just implement F

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

      I solved E using diophantine equations... u can see my sol here

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you explain how to handle the segments correctly? I mean, with diophantine in first place we calculte single integer values.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          just brute force Y * Q times....

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

          yes then we can check the values of k in

          " equation: ax + by = c. let x0,y0 be integers which satisfy the following: a⋅x0 + b⋅y0 = c Then x = x0 + k⋅b/g, y = y0 − k⋅a/g are solutions of the given Diophantine equation. g: gcd(a,b)"

          which give us x >= 0 && y >= 0. and calculate the values at border values of k.

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 4   Vote: I like it +35 Vote: I do not like it

      We want to find some $$$t$$$ such that $$$X + n(2X + 2Y) \leq t < X + Y + n(2X + 2Y)$$$ and $$$P + m(P + Q) \leq t < P + Q + m(P + Q)$$$. In other words, $$$X \leq t \mod (2X + 2Y) < X + Y$$$ and $$$P \leq t \mod (P + Q) < P + Q$$$. Because $$$Y$$$ and $$$Q$$$ are sneakily only at most 500, we can naively brute force $$$t \mod (2X + 2Y)$$$ and $$$t \mod (P + Q)$$$ pairs and check the existence of a solution with Chinese remainder theorem. There's conveniently a crt implementation in Atcoder library under math header.

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

        It should be "...In other words $$$X \leq t \mod (2X + 2Y) < X + Y$$$". Insn't it?

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          (2X + 2Y) = (2 * (X + Y)), so because of this we can take mod as (X+Y)?

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I don't think that's always true, consider a simple example of $$$X = 1, Y = 1, 6 \mod (2X + 2Y) = 2, 6 \mod (X + Y) = 0.$$$

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Good catch, fixed.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nice explanation, thanks.

        I think you made a small typo in the first sentence: it should be $$$k(2X+2Y)$$$ instead of $$$n(2X+2Y)$$$.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Must have not been fully awake when I wrote that :D. Thanks for catching it.

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Couldn't catch the train till the end!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

F, what strategy works, how to prove it?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can't we do it via dp ?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Most solutions I inspeced created a max flow graph.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you elaborate ?

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it +40 Vote: I do not like it

          Let's suppose you had to minimize the number of adjacent pairs of cells with different colors. For a final coloring of the grid, this number can be calculated by dividing the nodes of the grid-graph (graph formed by adding edges among all pairs of cells which share a side) into 2 parts based on their colors and then counting the edges which connect nodes in different parts.

          To minimize this value, you can just find the minimum-cut of the graph. But you also have to ensure that cells that were already colored and had different colors are in different parts of the cut. For this, you can add an edge with infinity capacity from the source to each cell which is already colored black and from each cell which is already colored white to the sink. These edges can never be part of a minimum cut dividing source and sink and hence they will ensure that edges with fixed but different colors are in different parts.

          To solve the original problem, we will minimize the number of adjacent pairs of cells with same colors in a valid final coloring and subtract this value from the total number of edges in the grid graph. Notice that the endpoints of all edges in the grid graph have different value of (row no. + col no.) mod 2. So, if we flip the color of every node with (row no. + col no.) mod 2 == 0, then edges whose endpoints had different colors will now have same colors and vice-versa. This transformation reduces our problem to the problem discussed in the previous paragraphs which can be easily solved with Dinic's algorithm.

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            How can we flip the colour of vertices that have a fixed colour? Won't that violate the min-cut condition as the new value would be infinity?

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it +16 Vote: I do not like it

            I probably read the editorial 3-4 times but still couldn't make sense with it, you just made it a lotttt clear.

            Thanks!

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

            Why are we flipping 'B' and 'W' in problem F only when i+j is odd in the editorial ? I am unable to understand it. If anyone else understood it, please explain in simpler terms.

»
7 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

I found D very frustating because of overflow. What is the point ?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Integers (Longs) were supposed to be used instead of Doubles.
    In order to attain a precision of 10^-5, I simply multiplied the number by 100000, performed integer division, and split the answer into two parts using a formatting function.
    1st part -> (long)result / 100000
    2nd part -> (long)result % 100000
    The link to my submission: Submission

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, the output is a ratio a/b of long long. So your method is fine.
      But a simpler way is to output double(a)/b as done in the exercise editorial.

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E and F?

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

    My solution for E:

    Among the first 2(X+Y) seconds, the train stops at Y of those seconds. Label these seconds 0,1,2...Y-1. Also, if second i is labeled, apply the same label to second i+2(X+Y).

    Similarly, among the first P+Q seconds, label the seconds where Takahashi is awake, and if second i is labeled, apply the same label to second i+P+Q.

    The problem is to find the earliest second that was simultaneously labelled in both steps. We can brute-force this by enumerating all Y*Q pairs of labels and considering when is the earliest second labelled with those specific pairs of labels. For each pair, the answer is an intersection of APs (https://math.stackexchange.com/questions/1378976/computing-the-intersection-of-two-arithmetic-sequences-a-mathbbz-b-cap).

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know why using doubles is giving WA in D!

  • »
    »
    7 weeks ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it

    For D I simulated all possible card selections (2 for loops, skipping invalid combinations that pass the card limit)

    then calculating the sums after picking those cards

    if its bigger add number of ways to get that card combination to num(if the cards picked by both are the same, let cnt = num of remaining cards with i written on them not picked. Its cnt * cnt-1 ways,

    else its num of remaining cards numbered i * number of remaining cards numbered j) Add the same to tot then output num/tot.

    btw i used doubles. You can check my solution here:

    https://atcoder.jp/contests/abc193/submissions/20554741

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

I had some idea how to do F with Maximum Flow. But couldn't complete it. Anyone can share their approach?

»
7 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

For D, i used ll x=n-mp1[i]+mp2[i],y=n-mp2[j]+mp1[j]; instead of ll x=n-mp1[i]-mp2[i],y=n-mp2[j]-mp1[j]; . and tried to find the bug for 1 hour+. (: fuc* my luck (:

»
7 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

My usual screencast with explanations, but only A-E this time, sorry guys.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you solve C?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Note that all numbers usable as $$$a$$$ are smaller or equal to sqrt(n), so max ~1e5.

    Then we simply find all numbers (collect them in a set) we can build by all possible $$$a^b$$$, and subtract this number from n.

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

    run two for loops i and j to calculate all i^j <= N, storing values in a set,

    the first loop runs from 2 to sqrt(N), while the second runs starting from 2 till i^j > N (which is in worst case logN)

    ans = N — Set size

    https://atcoder.jp/contests/abc193/submissions/20535157

    works in O(log N * sqrt(N))

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As you can see clearly, the maximum base number is not more than $$$10^5$$$, and the maximum power does not exceed to $$$\left\lfloor\log_{2}10^{10}\right\rfloor=33$$$. So we just directly list all numbers within n that satisfy the b-th power form of a, and then remove the multiplicity then get the answer :)

    Code using set
    Code using map

    Hope it'll help you :)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! That makes a lot of sense

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

I have realized how powerful the AtCoder library it is... Look at this AC submission of E if you want to know reasons.

»
7 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

A more interesting ABC than usual. Kudos to problemsetters.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes best round in recent history. Hope this becomes a trend!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem F, how do I extract the chosen colors for all '?' cells (from the min-cut/max-flow)?