hiddentesla's blog

By hiddentesla, 4 years ago, In English

Hello Codeforces Community. I would like to invite you all for ICPC Indonesia COMPFEST 12 Multi-Provincial Contest Online Mirror. I am the Person In Charge of the event.

compfestlogo

I want to thank:

The online mirror will be held on , 3 hours after the official contest starts. Teams are allowed. The duration of the contest is 5 hours. For the official contestants, please refrain from joining this mirror contest.

Our problems are relatively easier than ICPC regional contests. However, we promise an interesting and diverse problem set. I'd say the overall difficulty is slightly more challenging than div two rounds. There might be an interactive problem. So make sure to familiarize yourself

About COMPFEST: COMPFEST is an annual event hosted by the University of Indonesia. It is the largest student-run IT event in Indonesia, and Competitive Programming Contest (CPC COMPFEST) is one of the competitions hosted.

Our contest on regional finder

Note: this contest is unrated.

UPD1: Editorial and contest review will be posted in a few hours, after we finish the official contest duty.

UPD2: Editorial is available here

Congratulations to the winners!

  1. Extra Registration (LJC00118, xay5421, Sulfox)

  2. jiangly

  3. Bajetii (theodor.moroianu, freak93, bicsi)

  4. 未来ガジェット研究所 (wasa855, frame233, memset0c)

  5. QAQAutoMaton

  6. wlzhouzhuan

  7. 2016wudi fan club (ChthollyNotaSeniorious, leukocyte, Cirno_9baka)

  8. wucstdio

  9. Sugar_fan

  10. Teams Are For The Weak (IceKnight1093)

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

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

can I participate without team?

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

How many members in a team are allowed?

»
4 years ago, # |
  Vote: I like it +59 Vote: I do not like it

rip im 20 years too late

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

    whoops! sorry about that. It's fixed now.

    (effects of writing at 2 AM)

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

      Isn't it a bit unfair to post the announcement and then delay the round by 20 years?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -35 Vote: I do not like it

        Isn't it a bit unfair that without contributing much to the community, you are 2nd top contributor.

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

          What do you mean? This is a quality post right here

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

here link is wrong.

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Will there be any editorial for this contest?

Thanks

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

I am eager to participate !!

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

How do you participate as a team?? could anyone walk me through the process it's my first time participating as a team.

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

    go to ur profile , in tag "team" create ur team, invite ur teamates, when register choose "as a team member" instead of "as individual participant"

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Will we be able to see the live standings?

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

th level?

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Have a feeling that this contest would be pretty interesting!

Also great to see "There might be an interactive problem. So make sure to familiarize yourself" such notification before the contest. I was clueless when I first saw an interactive problem a couple of contests back.

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

Will problems be sorted depending on the difficulty like normal CF rounds?

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How many question will be set on the dashboard?

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

Will this year's INC be running a mirror on CF as well?

»
4 years ago, # |
Rev. 2   Vote: I like it -43 Vote: I do not like it

Nvm it'll be great :)

»
4 years ago, # |
  Vote: I like it -23 Vote: I do not like it

CAN I USE C++ THIS CONTEST??

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

Are contestants allowed to copy-paste code from their library or search things on the Internet during the contest?

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

will there be any rewards for the toppers of this contest?

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

will tutorial be available after contest??

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

Nice problemset! Enjoyed a lot!

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve E :|

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Hints for problem E
    Code
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any edge cases for test case 19 in D??

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

    Its

    4 3
    1 2 4 8
    17 15 16 1
    

    You can get 7 by only exciting the last atom

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

      I think the question is problem D, not E

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

        Sorry i misread the question. In D there are no edge cases (that we intend to). Maybe check your formula

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

    I found the mistake the range of n was 2000 and coordinates was 1000 I took both array of size 1000 :(

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

We will release the editorial and contest review in a few hours. right now we are so tired from nonstop supervision of contests. Sorry about the unexpected difficulty jump :( we intended B to be a medium dynamic programming problem.

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

hiddentesla Can we participate in the contest virtually?

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

Now contest is over,but why can't I read the problems?

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

    Sorry about that. We just updated the settings. We disallowed before just to prevent the official contestants from registering

»
4 years ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

In Problem B, I think it's not very nice to mention "every checkpoint except checkpoint 1 has exactly two routes connecting it" only in the input section , since it is quite important leading to the solution :(

BTW I've spent about an hour to write&debug my B but in vain :(

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve I?

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

    Oh, I thought the editorial wouldn't be published. I'll read it :).

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

    Arrange the nodes in dfs order so that subtrees correspond to subarrays, and then simply answer each query in O(n). Runs in 3.2s without pragmas or fast i/o, and 900ms with them: Code

    Using the ternary operator is apparently important because I TLE'd when I used an if condition instead, probably some stuff going on with branch prediction which I really don't know about.

    I'm sure this wasn't intended, but I don't know if it can be made to TLE within the limits of the problem.

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

      The intended solution uses segment tree beats. We tried our best O(NQ) solution before and our fastest only got 13s. Pretty suprised we are still far away from constant optimization. Please wait for the editorial for the detailed explanation

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

        With $$$N = 50000$$$ and 7 seconds, it's hard to imagine quadratic solutions to not pass, with some minor tricks (our solution also runs in under 1s with pragmas). Was the official complexity $$$O(Q \sqrt{Q} \cdot Beats(N))$$$?

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

          $$$ Q \sqrt{Q} log (N)$$$ was the intended complexity. Yeah we are quite suprised. One solution NQ solution even manage to pass in less than 1 second sobs

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

      Is it in time!? I was trying to make a solution better than O(NQ).

      Thank you!

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

        yeah our intended solution runs at 4.000 s. However some NQ solutions run less than 1 s.

        oof

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Weak tests for problem G XD

My program outputs lolos for case :

7 7
.......
.#####.
.....#.
..##.#.
..#MC#.
..#..#.
.......
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Behind the scenes: generating test cases for problem G was so hellish, that its easier to generate testcases by hand rather than using a generator program. First 25 test cases was hand made.

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

    Bad move, now they removed the problem from your standings.

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

When or where will the editorial be published for this contest?

»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

problem C

detected an integer overflow error at the 154th line of the problem setter's submission:

intmod c(int K) {
	return a(3*K/2)-b(K/2);
}

K can be up to $$${10}^9$$$ so 3*K will cause overflow

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

    Yeah, all of our testers used the same formula. So sorry for this. All of the submissions for C is rejudged. Only 1 participant in contest is affected.

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

how to solve D?

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Is there any solution?

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

Can someone help me find bug in my solution for Question D? During contest, I got wrong answer on test case 9. I tried upsolving later but couldn't find the bug.

Link to the submission : https://codeforces.net/contest/1425/submission/93937461

General Idea : So the idea is to count the total number of strategies in which a & b both occur together. Let's assume they occur in X number of different strategies. Then we can add X * (2ab) to our answer (calculating a^2 is trivial and can be handled separately). Now in order to calculate X, we can consider the bounding box for a & b and then count the number of snakes in their intersection, union, and rest and can use combinatorics to calculate the answer. Please refer the code.

Can someone please explain the bug in my code?

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

    Hi, you might want to check your logic on getIntersection. Here is a small testcase that might help:

    3 1 0
    5 6 10
    4 6 30
    3 6 20
    

    Answer should be 1400.