I_love_Hoang_Yen's blog

ACM ICPC Vietnam National Round 2017 Online Mirror — Sun 05/11
By I_love_Hoang_Yen, 7 years ago, In English

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

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

Comments Comments (35)
| Write comment?
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

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

    Can you explain the solution?

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

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

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

    106 ≤ K

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

    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?

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

      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!

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

      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.

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

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

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

          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.

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

            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.

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

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

              → Reply
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I want to die.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks a lot!

      I'm waiting for the solution of Problem F.

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

        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.

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

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    And the bit-wise XOR of the sequence b should be 0 so that the second player wins the NIM.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It's not derivatives of function. You can read editorial in Vietnamese here.

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

      What is the approach for C, the editorial simply mentions the oeis link, with no formula/explanation as to how to calculate the sum efficiently.

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

        Do you read Vietnamese? It says problem is too difficult, in VN only very few people can solve it, including author. Editorial authors can't solve it.

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

        Key idea is that: sod is not too big. So if start with xxxx000...000yyy, we want to jump to xxx(x + 1)000...000zzz. Count the number of that jumping and the sum of them.

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

      Thank you. It is clear now.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Mrs. Hoang Yen, not Mr. Hoang Yen

    → Reply