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

Автор I_love_Hoang_Yen, 7 лет назад, По-английски

UPD: Author's solutions are published here.

Hi all,

This Sunday (Nov 05, 2017), there will be ACM ICPC Vietnam National Round 2017. This is the qualification round for Vietnamese teams participating in ACM ICPC Vietnam Regional.

There will be online mirror on Kattis.

  • Time: 8am Vietnamese time
  • Normal ACM ICPC rules will be used.
  • Standings will be frozen in last hour.

I hope that many of you will enjoy the problemset, especially the teams that will come to our Vietnamese regional. Good luck & have fun :).

  • Проголосовать: нравится
  • +91
  • Проголосовать: не нравится

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

For problem L, I only read the description part of the problem. And, I can't believe there are so many ACs on the scoreboard of the online mirror.

After contest, I finally found out the most important key points in the Constraints section...

  • For all nodes which has property, .
  • For every i from 1 to M, 1 ≤ ui < vi ≤ N.
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Yeah, That is a tricky one. In the official contest, noone realize that and there is no serious attemp to that problem

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

    Can you explain the solution?

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

      Notice that the given graph is DAG, and there's no point in buying house, so this become a trivial DP on DAG problem (dp[u] is the largest amount of money one can get if they start from vertex u).

      Seriously, noticing the unusual constraints is much harder than solving the problem itself (and no one in the official contest was able to do this, we all thought that this problem is an insanely hard game problem and didn't even bother finish reading the statement).

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

    Actually, there is one more important tricky constraint that solves the problem.

    106 ≤ K

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

    While admitting that the author purposely tried to hide that key information, I am still curious why you did completely ignore the constraints section before trying to solve the problem. Being aware of how large the graph is was helpful in thinking of solution, wasn't it?

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

      Yes, I did read the constraints til the 4th one(1 ≤ sa ≤ N, 1 ≤ sb ≤ N). And, I thought rest of the parts may be something like no self-loop, no multiple edges, etc. as usual graph-related problem.

      It looks like a normal graph size(N, M ≤ 105) and 106 ≤ K seems to let the game go into some stable state. Thus, I thought I totally understood the problem and decided to skip it first.

      If the graph is some special graph(tree, DAG, functional graph, etc), I thought it would be better to mention it in the description.

      Anyway, the contest is still very nice!

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

      I thought that I can't solve this problem no matter what is the constraint of N and M so I just skipped this problem without even reading the constraint.

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

        What if N, M are at most 10 and K is at most 100? It becomes a trivial dp problem, doesn't it?

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

          Probably I was being too haunted by the game on graph problem to a point that I skip all problem involved those. Perhaps I should practice this kind of problem more.

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

            You should practice reading statement more. "didn't even bother finish reading the statement" is not acceptable in any ACM ICPC contest. You have 15 people hours. Read everything carefully.

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

              I guess this is a lesson for me and also, everyone in Vietnam who participated this round. And I learned it the hard way.

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

I want to die.

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

Any hint for problem A? Or even better, will there be an editorial?

For problem G, I would not expect that the graph can contain many loops and many roads between 2 vertexes :'(

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

    There will be editorial in Vietnamese. I'm writing it but keep getting interrupted by work, so it will take some time to finish.

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

      Thanks a lot!

      I'm waiting for the solution of Problem F.

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

        F just has few simple steps:

        1. DP to calculate how many numbers in [L, R] where digits are in bitmask S. You do this with a DP function: f(length, digit_mask, is_lower_than_upper_bound).

        2. For a number like 1234, you actually want to add f to all its subset (not just set {1, 2, 3, 4). You can do this with O(210) for all bitmask, but simple O(310) can pass.

        3. Now the problem becomes a combinatoric problem where you want to count number of ways to select K elements. This can be done using inclusion-exclusion.

        If you still don't know how to solve it, wait until judge's code are published.

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

    For problem G, I also didn't know the fact for an hour. After that, I solved with parametric search for L whether there is a cycle or not.

    For problem A, we can use segment tree — lazy propagation with some coefficients of arithmetic sequence for each degree in polynomials.

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

Did I understand problem H right? I thought that statement means finding the number of sequence {b_n} that satisfies

0 <= b_i <= a_i for all 1 <= i <= n and there are at least two k satisfies b_k = a_k (1 <= k <= n).

I submitted code and I expected the result should be TLE, but it was WA.

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

How to solve problem C (Cumulative Sum)?
It has 0 accepted submissions.

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

Sorry, Mrs. Hoang Yen!!! Regarding solution of problem A, would you mind elaborating on the "update" method? Why did you take derivatives of the function? I am completely confused about that.