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

Автор hiddentesla, 4 года назад, По-английски

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)

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

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

can I participate without team?

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

How many members in a team are allowed?

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

rip im 20 years too late

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

here link is wrong.

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

Will there be any editorial for this contest?

Thanks

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

I am eager to participate !!

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

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

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

    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 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Will we be able to see the live standings?

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

th level?

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

How many question will be set on the dashboard?

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

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

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

Nvm it'll be great :)

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

CAN I USE C++ THIS CONTEST??

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

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

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

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

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

will tutorial be available after contest??

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

Неответственно обвинять других в своих ошибках, так что, пожалуйста, верните мне мой рейтинг.

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

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

Nice problemset! Enjoyed a lot!

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

How to solve E :|

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Hints for problem E
    Code
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any edge cases for test case 19 in D??

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

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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

hiddentesla Can we participate in the contest virtually?

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

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

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

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

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

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 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

How to solve I?

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

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

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

    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 года назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          $$$ 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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      Thank you!

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

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

        oof

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

Weak tests for problem G XD

My program outputs lolos for case :

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

    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 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

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

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

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

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

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 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

how to solve D?

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

Is there any solution?

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

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 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.