hiddentesla's blog

ICPC Indonesia COMPFEST 12 Multi-Provincial Contest Online Mirror Editorial
By hiddentesla, history, 4 years ago, In English

Hi everyone, sorry for the considerable delay. It turns out, we were exhausted yesterday from supervising two contests back-to-back. We are surprised by the number of participants in the online mirror. And I hope you enjoy the problems :)

Our big surprise was problem B. We were setting it to be a medium problem. Turns out, maybe the observation is not that obvious.

fun fact: Initially, we don't plan to have any particular naming theme other than the obligatory first letter matches the problem order. However, when naming 6 out of 9 problems, one of my committee member noticed that 5 problems have A of B theme. So, we decided to continue using this theme.

Here are the authors and first solvers for all problems:

A — Arena of Greed

Author: JulianFernando

Expected difficulty: Medium

Tag: greedy

First solver: kotamanegi

B — Blue and Red of Our Faculty!

Author: dewa251202, hiddentesla

Expected difficulty: Medium-hard

Tag: dynamic programming

First solver: team NeedHelpPls: MiricaMatei, AlexLuchianov, loan

C — Captain of Knights

Author: AMnu

Expected difficulty: Very hard

Tag: math

First solver: team Extra Registration: LJC00118, xay5421, Sulfox

D — Danger of Mad Snakes

Author: hiddentesla

Expected difficulty: medium

Tag: Inclusion-exclusion, DP prefix sum.

First solver: team hsy-DD: Yukikaze_, Fuyuki, xzx34

E — Excitation of Atoms

Author: hiddentesla

Expected difficulty: easy-medium

tag: Adhoc, casework.

First solver: jiangly

F — Flamingoes of Mystery

Author: hocky

Expected Difficulty: easy

Tag: Adhoc

First solver: Team LCA on Cactus: tem_shett, Dart-Xeyter, sevlll777

H — Huge Boxes of Animal Toys

Author: hocky

Expected Difficulty: easy

Tag: Adhoc

First solver: idea guy, snake wrangler, and deep learner: oof_ouch_owie, tenth, WolfBlue.

I — Impressive Harvest of The Orchad

Author: hocky, hiddentesla

Expected Difficulty: Hard

Tags: SQRT algorithms, Segment tree beats.

First solver: IIT Patna: ravik1, Sixpathsguy, darklight13

Tutorial is loading...

Code: 94148836

Tutorial is loading...

$$$O(N^2 \sqrt{N})$$$ code: 94149019

$$$O(N^2)$$$ code: 94149066

Tutorial is loading...

code: 94149150

Tutorial is loading...

code: 94149327

Tutorial is loading...

code: 93947185

Tutorial is loading...

code: 94151055

Tutorial is loading...

code: 94151563

Tutorial is loading...

Code (without lazy propagation): 94152055

Code (with lazy propagation): 94152123

Honorable mention: the fastest $$$O(NQ)$$$ solution during the contest: 93941953

About problem G

Problem G was really saddening. We had a cool solution using convex hulls. The solution idea is for we find all connected components of "#". For each CC, we push to a set all non-"#" squares connected in the top, right, left, and down of each '#' and then build a \textbf{convex hull} from the set. The convex hull is then marked the safe zone. If the thief can reach one of these safe zones, the answer is "lolos".

However, after the contest, one participant found the counter case on solutions like this:

5 5
M....
.....
..#..
...C.
.....

The distance from the thief to each safe zone is not less than Mr. Chanek. However, the thief can move to bottom-right, which can then react to Mr. Chanek's next move. (output is "lolos", jury will print "tertangkap").

We are sad and are currently finding the correct answer. We have also taken down the problem (for now). We manually verify every test case during the test generation of this problem, so they are correct. During the contest (official and mirror), nobody managed to pass the test cases (except jiangly), so it does not affect the standings. However, broken is still broken. We hope it does not reduce the enjoyment of the other problems that much :(.

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

Comments Comments (30)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain if 2*k — 2 > k why we should go for second case?

Problem A

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

    Because then we get the same number of coins as the first case, but there are more coins left in the chess. This is of course better, since we can collect more coins on the long run.

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

      Shouldn't it be considered as the profit I'm making over the other user? In one turn I get 2*k, while my opponent gets 2, Hence 2*k-2(For the first case) For the second case, I get 2*k, while my opponent gets K. Hence he diff 2*k-k=k

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

In the question Arena of Greed, let us say that we have 4k coins. If we pick 2k coins, what is the guarantee that the opponent will pick k coins? Since the opponent also plays optimally, is it guaranteed that from 2k coins, his optimal strategy is to pick k coins? Can someone explain this?

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

    Yeah, the opponent may have a manuver. However, no matter what move the opponent makes, us picking 1 coins when having 4k (k > 1) coins always guarantees us having the same (or more) coins that taking n/2 coins, while there are more coins left on the board (which is better, since we can get more coins overal)

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

      A different perspective:

      Lets say we take the first case. We have 2k coins. The maximum number of coins we can get from the following moves is less than k-1. Because obviously the opponent wants to minimize our score, and a possible move is to take k coins which results in us having at most k/2 + k/4 + ... which the sum cannot be greater than k-1 coins.

      However, if we take the second case. We get 2k coins while there are 2k — 2 coins remaining. Just by halving again, we already get k — 1 coins. Which is better than the maximum coins we get from the first case.

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

        How to think of "4k" intuitionally?

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

          I think intuition comes with practice and experience. For me the intution is, as explained in the editorial, to minimize the number of coin that the opponent get. When solving, it's also a good idea to brute force by hand for small test cases, and see if you can find any observation.

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

In E, what do you mean by "toggling bonds" when K>2?

UPD: Oh I see it now.

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

Hi, for problem E, it is said that for K >= 2, we can basically excite all atoms starting from anywhere by exciting only 1 atom.

But I want to give a counter TC.

5 3
1 1000000 1 1 1
1000000 1 1000000 1000000 1000000

For that TC, clearly we should start from index 2, right? because d[2] is the smallest among all d. But somehow I couldn't figure out the way to excite all atoms by only exciting one atom, i.e. the second atom using K = 3. So I think for this case, the answer should be 1000002 instead of 1000003. But jury's solution gives 1000003. CMIIW.

Please help me to point out the way to achieve 1000003 in case I miss something.

Thanks

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

    Hello, you can change $$$E_2$$$ to $$$1$$$ and then change $$$E_1$$$ to $$$3$$$. So, when you excite atom $$$2$$$, it will excite all atoms.

    EDIT: sorry, i misread your $$$K$$$. I thought you wrote $$$K = 2$$$. Ok, minor change: First change $$$E_2$$$ to $$$4$$$. Then change $$$E_2$$$ to $$$1$$$, then change $$$E_1$$$ to $$$3$$$. Same configuration as written above.

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

      Hi, that is for K = 2, right? My case is for K = 3. If we change some bonds 3 times, can we excite all atoms by exciting atom 2 only?

      Thanks

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

        yeah misread that, I updated my comment. I updated it the same time you posted this comment xD.

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

      First change E2 to 4. Then change E2 to 1.

      but what about "You must first change exactly K bonds before you can start exciting atoms."?

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

        That's indeed what we do, right? E2 to 4..then E2 to 1..then E1 to 3. We have changed exactly K bonds (K = 3 here), only then we start exciting atoms. In this case we can just excite 1 atom from atom 2.

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

I used segment tree with two-dimensional tag (A,B) (which means v=max(v+A,B)) instead of segment tree beats and got AC . but I can not analyze its efficiency well , is it O（nlogn）too ？ My Submission: 94211700

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

    For problem I

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

    this break condition:

    if (a[V][n].mi>0) return;

    and this tag condition

    if (f && a[V][n].ma==0)

    Isn't this the same break & tag condition proposed by the editorial? except you implemented it in a different way. Correct me if im wrong.

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

      Yes，this's right !

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

        Yeah that should yield the same complexity. The important thing is that the segment tree should visit the highest vertex which all of its child is harvestable. The implementation details on how to know that information can vary, but it will all give $$$O(Q log n)$$$ complexity since the analysis is not dependant on the implementation details.

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

          Ok I get it. Appreciating your help !

          → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

For anyone looking for an easy way to understand problem-A, this is for you.

Let's take an example first, n = 12;

0 has the opportunity take 1 coin or 6 coins, if he takes 6 coins then remaining coins are also 6 and the other person can take 3 coins.

But here's the trick. Take n/2 coins if and only if n/2 is odd and you force the opponent to take the least no.of coins, i.e, 1 coin since n/2 is odd.

Following this approach, we have as below;

0th person: 1 + 5 + 2 + 1 = 9;

1st person: 1 + 1 + 1 = 3

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

In statement of problem B said: "The game ends when Blue or Red can no longer move. That is, there is no two distinct gray routes they can choose to continue moving." Why can't we get situation, when there's one gray edge between red and blue parts of loop?

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

    Yes, lets say we have a cycle like this: 1 -> 2, 2 -> 3, 3 -> 1. Its possible that red takes path 1 -> 2, blue takes 1->3. Now both of them can no longer move because there remains only one edge both of them can choose.

    This is handled in the DP, since we can determine red and blue's final position in our fixed cycle uniquely by the difference in the number of edges they took.

    → Reply
»
4 years ago, # |
  Vote: I like it +52 Vote: I do not like it

The complexity analysis of the solution in the editorial for problem I is wrong. The problem with the proof is that the claim 'each nonzero mark can appear at most once at any given time' is false; multiple siblings of ancestors of node X can gain an 'old mark' when we query X.

In fact, the solution for one $$$A_i$$$ is not $$$\mathcal{O}(Q\log(N))$$$, but actually $$$\Omega(QN)$$$, as the generator below demonstrates. For the generated testcase, the segment tree beats solution 'harvests' about $$$\frac{1}{12}QN$$$ nodes when $$$A_i$$$ is $$$3$$$ (assuming $$$Q$$$ is allowed to be $$$\frac{8}{3}N$$$). The codes in the editorial take around 30 and around 50 seconds respectively on this case on my local machine, so would probably give TLE on the codeforces platform.

Generator

As an aside, personally I find segment tree beats solutions quite tricky to prove, but I also find it quite difficult to create testcases that causes them to become slow. So I don't blame the authors; I am just a little disappointed that what first looked like a cool application of segment tree beats turns out to be wrong.

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

Problem B. Can anyone explain why the jury's answer is 22 (test 6)? As I unterstand, there are 2 ways to get stuck in A, 6 ways to stuck in B and 18 ways to stuck in C.

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

can someone explain me about prefix sum 2d in problem D?

→ Reply