Блог пользователя maroonrk

Автор maroonrk, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

For those interested, I'm planning to do a stream afterwards on Twitch.

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

I wish good luck to all participants able to solve a problem in this contest. :/

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I give up!

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve E?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How to solve A?

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

To me, B was easier then A. How to solve A?

  • »
    »
    3 года назад, # ^ |
    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} $$$

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Will you please explain your solution.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +35 Проголосовать: не нравится

        Imagine $$$10^n$$$ in base $$$m$$$ and you can see the answer is the second last digit.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +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$$$

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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$$$
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    let y be the answer(0 <= y < M), then the condition is: ( 10N — (10N)%M — y*M)%(M2) = 0

    my proof

    Now how to solve B??

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ty, now i think im able to understand.

    • »
      »
      »
      3 года назад, # ^ |
      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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Amazing proof!!

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    I felt A took more thinking than B and C and D

»
3 года назад, # |
  Проголосовать: нравится +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???

»
3 года назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

can anyone please explain what is wrong with this solution to D.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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

»
3 года назад, # |
  Проголосовать: нравится 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?

»
3 года назад, # |
  Проголосовать: нравится +164 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -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.

  • »
    »
    3 года назад, # ^ |
    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.

    Spoiler

    Upd: To the ones downvoting above comment. It wasn't obvious. I had the same doubt when I first read this.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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!

»
3 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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/19280968

      i know its wrong but why what i am not getting

      • »
        »
        »
        »
        3 года назад, # ^ |
        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)

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          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)))
          
»
3 года назад, # |
  Проголосовать: нравится +86 Проголосовать: не нравится

Problem E's maker has no wood!

»
3 года назад, # |
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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can somebody explain why is this getting runtime error?

https://atcoder.jp/contests/arc111/submissions/19387114

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

in my opinion, problem F should not have queries type 2