ICPC Indonesia COMPFEST 12 Multi-Provincial Contest Online Mirror Editorial

Revision en3, by hiddentesla, 2020-09-28 21:25:49

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, Gioto

C — Captain of Knights

Author: AMnu

Expected difficulty: Very hard

Tag: math

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

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: shart23, Dart-Xeyter, sevlll

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, epicxtroll, 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 :(.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English hiddentesla 2020-09-28 21:25:49 4
en2 English hiddentesla 2020-09-28 21:23:58 221 (published)
en1 English hiddentesla 2020-09-28 21:18:22 4521 Initial revision (saved to drafts)