csacademy's blog

Round #18
By csacademy, 8 years ago, In English

Hello, Codeforces!

We are happy to announce that we're going to host a new contest at csacademy.com. Round #18 will take place on Sunday, 12/Feb/2017 18:30 (UTC). If you want to take part in this round you need to register before the contest begins. This contest will be a Div1 + Div2, with 8 tasks of varied difficulty that need to be solved in 2 hours and 30 minutes.

We are honoured to have desert97 as problem setter.

Contest format:

  • You will have to solve 8 tasks in 2 hours and 30 minutes.
  • There will be full feedback throughout the entire contest.
  • Tasks will not have partial scoring, so you need to pass all test cases for a solution to count (ACM-ICPC-style).
  • Tasks will have dynamic scores. According to the number of users that solve a problem the score will vary between 100 and 1000.
  • Besides the score, each user will also get a penalty that is going to be used as a tie breaker.

About the penalty system:

  • Computed using the following formula: the minute of the last accepted solution + the penalty for each solved task. The penalty for a solved task is equal to log2 (no_of_submissions) * 5.
  • Solutions that don't compile or don't pass the example test cases are ignored.
  • Once you solve a task you can still resubmit. All the following solutions will be ignored for both the score and the penalty.

We still recommend using an updated version of Google Chrome. If you find any bugs please email us at contact@csacademy.com

Don't forget to like us on Facebook, VK and follow us on Twitter.

EDIT:

Congratulations to the winners:

  1. Um_nik
  2. andrew.volchek
  3. Reyna
  4. IvL
  5. LHiC

We hope you enjoyed the contest!

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

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

My solutions.

F: sparse table to precompute the min. position j such that gcd([i..j)) = 1 in a linear array, then DP counting the number P(i, g) of A[i..N) such that the last partition has gcd equal to g; there are just possible values of g, so it's

G: when solving the subtree of R, we keep a structure S that contains some previous ancestors and is able to answer queries "pick the best of them for any vertex v"; pick the son s with the largest subtree, solve all other sons' subtrees by bruteforcing over them and picking from S, then solving them recursively without S (starting with empty structures), then add R to S and solve the subtree of s recursively with S (HLD trick, time if one query on S takes time)

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

    How do you answer this query "pick the best of them for any vertex v"? And what is the time complexity for this?

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

      Let fv(x) = Cv + xdepv. You're looking for the smallest x such that there's some fu(x) = fv(x), but it's enough to consider the smallest fu for each x; for a set of lines, taking only the smallest fu gives a convex (or concave?) polyline, to which you can add lines like in the convex hull algorithm. When all u can only be ancestors of v, fv will only intersect such a polyline once and you can find the segment of the polyline containing that intersection by binsearch. Note that lines are added in a very specific order in this algorithm, which simplifies things.

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

It's nice to see that editorial mentioned the fact that naive implementation of G works in O(N2). However, such implementation works in 0.121 on provided test data.

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

I really liked last problem! Too sad I made a stupid bug when fixing loops issue :(. Btw I guess that such picture can be a little misleading :P :

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

    Take it positively, at least you could submit.

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

    I don't get it. TL was changed during contest to 5s, but in archive it is set to 1,5s <- this is bad, but I get it. First thing I don't get is why I am getting "Accepted" even though I get TLE? Is that because it was killed after archiveTL=1.5s and execution time (shortly killed after 1.5s, to it is <1.6s) was compared with contestTL=5s? Second thing I don't get is why I started getting WA on 4th and 5th test in archive even though I am pretty sure I got them correctly earlier.

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

      First thing I don't get is why I am getting "Accepted" even though I get TLE?

      In TC, when you batch test on samples, it used to tell you "success" on top... when your code compiled.

      In some other sites, in problems with partial scoring, getting a non-zero number of points gives you AC verdict.

      And in CSAcademy, it tells you your solution is accepted when it passed some tests, even if it failed other tests. I've had it happen to me, luckily only when practicing. Once when the judging froze, I was getting AC in the "Submissions" tab, but it only meant AC on samples.

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

      The time limit was always 1.5seconds, it was changed before anyone submitted any code to it. It was a typo on our part to make it 5 seconds in the first place, that's why it was changed during the contest (when we realised). On your first point, I don't know what to say, it seems like a bug if it gets you AC, we will check it out. Second part seems really hard to believe though. We will check that out as well, thank you :)

      → Reply