JATC's blog

Codeforces Round #520
By JATC, history, 6 years ago, In English

Hi everyone. I'm glad to announce that the Codeforces Round 520 (Div. 2) will be held on 14.11.2018 18:35 (Московское время).

The round will be rated for Div 2 participants (whose ratings are lower than 2100). However, all the other participants can compete as well, without worrying about ratings being changed.

You will be given 2 hours to solve 6 problems. It's better to read all the problems. The scoring distribution will be announced soon before the contest starts.

All the problems were prepared by myself, with some help from my friend GiraffeCoder. I want to thank cdkrot for coordinating me in preparing the problems, vintage_Vlad_Makeev, isaf27, demon1999 and Arpa for testing my solutions. I also want to thank csacademy for their graph editor tool. You can check it out at this link.

This is the first round I propose. I put a lot of work into it so I hope that you will enjoy it (smiley face).

Wish you do your best and get a high rating!

Update 1: If you want to discuss about the problems after the contest, here is the link to the CP Community on Discord. Please make sure that you don't give the solutions to other participants during the contest.

Update 2: The score distribution will be the standard one: 500 1000 1500 2000 2500 3000.

Update 3: Congrats to the winner

Official participants:

  1. Kataoka_Yuuki

  2. Dark_Warlock

  3. wcysai

  4. coriander

  5. fcwww

Unofficial participants:

  1. budalnik

  2. HIR180

  3. KrK

  4. ayaze

  5. Anadi

Tutorial UPDATED

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

Comments Comments (98)
| Write comment?
»
6 years ago, # |
← Rev. 4   Vote: I like it -75 Vote: I do not like it

You forgot to thank MikeMirzayanov!!! for awesome codeforces and polygon platform.

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

Why vintage_Vlad_Makeev became blue?

→ Reply
»
6 years ago, # |
  Vote: I like it -31 Vote: I do not like it

I think you should hope that none of your problems or your checkers would have had mistake instead.

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

Happy to see another round from Vietnamese.

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

In China,520 means "I love you."




I prefer high rating :)

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

    But my girlfriend and I just broke up,I am so sad that I don't know how to do it.

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

      Sorry about hearing that bad news.
      振作起来，哥们。

      → Reply
»
6 years ago, # |
  Vote: I like it -33 Vote: I do not like it

Hi warriors,I'm back;

→ Reply
»
6 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Why gritukan became blue?

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

    I asked his friends and he wants his team on the list in front of the icpc with nicknames and ratings to look funny. A team of two red and blue.

    → Reply
»
6 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Isnt it unrated??

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

Can someone get rid of fake accounts in places 3-8. It's obviously just one or two people modifying their codes and submitting again. JATC

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

    now he is even first place, lol

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

    If there is any cheating those accounts will be disqualified probably :)

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

      I think there's some mistake happening here. Only 3 of those are cheaters, but coffee_chicken is not, but they all seem to be banned simultaneously. Is there any way to fix this?

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

        I'm not sure since it's the decision of the admins.

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

    They all got banned. Thanks, admins!

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -64 Vote: I do not like it

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

What's wrong with pretest 9 of Problem B? Anyone with a clue...

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

    Probably something like 93184 which is 1024*7*13. You may be having overflow issues.

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

How to solve E????? I tried Mo's algorithm + LCA the left/rightmost but got TLE every single time. I think the set is the main problem...

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

    I think you just need to have the lca of (i and i+1) and (i and i+2) pre-calculated for all i and then do with segment tree.

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

      Oh, it was that simple!!!!! LOL!!!!!! Thanks.

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

        I couldn't implement it as I forgot to make a simple observation in D but I think that should pass.

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

    My solution is like this: say that dfn[x] represent the order of vertex v when you do dfs, then the LCA of a set of vertices is just the LCA of the vertices with the lowest dfn and the highest dfn, so we can use a segment tree to maintain the vertex with the lowest dfn, second lowest dfn, highest dfn and second highest dfn, to answer a query, just do case analysis (3 cases here, erase the vertex with the lowest dfn, erase the vertex with the highest dfn, or neither). The solution is . You can do the LCA part using whatever technique, both binary lifting and euler sequence+RMQ would do.

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

What hacks are there? (for any problem)

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

Does this work for E?
Find maximal L that lca(l, L) != lca(l, r)
Find minimal R that lca(R, r) != lca(l, r)
If L + 1 == R — 1 and lca(lca(l, L), lca(R, r)) != lca(l, r) answer is L + 1.

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

D is too easy, innit? Or i will drop on full tests...

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

Just 10 more seconds :(

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

Is this not the correct formula for C?

(2^noOfOnesInLtoR-1)+((2^noOfOnesInLtoR-1)*noOfZerosInLtoR)

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

    nope dude, try this test case 4 1 0001 1 4

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

    I first thought so and got several WAs.

    must be aware that after eatings ones, which were initially zeroes now have some values which even gets larger and larger eating those.

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

    (2^noOfOnesInLtoR-1)+((2^noOfOnesInLtoR-1)*(2^noOfzerosInLtoR-1))

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

    It's just 2^(num zeroes + num ones) - 2^(num zeroes). Other formulas are looking kind of complicated.

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

All naruto characters are in the standings www

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

What is solution for D?

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

    My solution was simply to find all factors of every number from 2 to n. Now for each number from 2 to n, sum up all factors except 1 and the number itself. Now add all of these sums and multiply by 4 to get the answer.

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

    Build the graph where there's an edge between a and b with weight if you can go from one to the other. Whenever you have an edge between a and b, you also have one from a to  - b, so the degree of each vertex is even, and thus the graph is eulerian, and you can traverse every edge. So it suffices to find the sum of all of the edges, which is easy.

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

    Suppose you have an integer i.You can always make a cycle of size 4 for every k which is less than n and divisible by i.For any k which is divisible by i,just add 4 * (k/i) to your ans.Suppose that i has p multiples <=n.So for i,add 4 * ((p * (p+1))/2 — 1) to your ans.(-1 because i can not form a cycle to itself).

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

Does this work for E? I did dfs to find time in for every node. Then for each query, used seg tree to find node with minimum and maximum time, say mini and maxi. Then I took a node from l to r which is neither the max nor the min time, say x. I found lca(mini, x) and lca(maxi, x) and reported the one with maximum level and removed the other one.

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

RIP my rate :)

anyone knows B pretest 3?

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

    I think it's 10^6

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

      meh it was a silly mistake I knew the solution idea but I done it terribly :( I should have just checked if the last sqrt equals prime factors multiplied to know if we should multiply or not

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

    It's 256 or 64 I guess..

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

Problem F is simply this but with more cases.

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

    I think the factor of the "semi-important" cities makes the problem significantly more interesting and hard.

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

anyone knows problem B test 32?

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

In problem A, it would have been better if constraint for n was upto 1000, because for n = 1000 answer would be 1000. Some people might have missed this test case. I have also printed 999 in my current solution.

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

    exactly. I've got at least 3+ people in my room who've made this mistake. What was the reason for n being 100, I don't understand.

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

      Well, you can't call it a "mistake" if it doesn't lead to an incorrect solution. I knew this, but since n < 100, I didn't bother putting that case.

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

        Calling it a "mistake" was wrong actually. But n = 100 made it easier I think

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

    Really? What a disgrace.

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

    However this allows to handle less cases in the solutions, which is also not very bad

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

How is my system test B(submitted at ~45mins) still running on test 50? while many other people's submissions finished running.

https://codeforces.net/contest/1062/submission/45725683

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

Pretests for A were very weak.

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

    I'm sorry this happens but it's seem too hard to cover all the cases in just a few tests. Too much tests and the server will die.

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

The problem A pretests are one of the top-10 pranks that went too far.

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

I was wondering in Problem E if i wanted to count the number of nodes instead of just printing one what would the solution be ?

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

    I guess there can be only two nodes (at max) the ones with min start and max finish (dfs) times.

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

      the case of x nodes being direct children to LCA or choosing a subtree the answer will be x not sure if this is just a corner case thou.

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

        If x nodes are children to LCA, with x > 2, then u can never increase the answer right? by just performing one remove operation. So the count is zero.

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

          i think he asks for the nodes when removed will result in the best answer so i think the answer will be all of them however, my question is does handling this assures that the answer for all other cases is <= 2.

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

          I would consider the count to be x, since you can remove any of the children and it will be true that the "level of the project manager required is as large as possible."

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

it was hard for me. But in any case, thanks for the round and interesting problems.

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

It was really a prank with the problem "A Prank". Missed the last line :'(. Yet didn't get AC.

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

deleted

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

How can the fastest solution in Python be 171 ms for even shortest test (e.g. problem A. tc #1)? Status order by consumed time (choose language, e.g. Python 2, and status: acc). Seems it doesn't depend on which problem but all Pythons (2, 3, pypy-2-3) have >100ms to pass any test case. Strange.

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

    Maybe it is to load the runtime environment, just like how java always eats 100ms start time.

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

      But its first time I see ~170 ms (almost 1/6 of TL). If you look at much earlier contests this minimal time was usually faster, e.g. Contest #839

      → Reply
»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

I get 247 rated! Thank you!!!!

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

Take a glance at A

Process to calculate sum of (each continue-element segment — 2) lengths

Wrong answer at test 7

Take one hour to realize answer is the maximum length

Ye.

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

Codefores is the best!!!

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

It seems that H.D.T and trungttt cheated during the contest. The codes are basicly the same but with random stuff added to hide it.

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

    The common parts of code seem to originate from http://e-maxx.ru, which is allowed.

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

      E-maxx has implementations for standard algorithms, not specific problems. It is clear that all the solutions are identical. And why are the solutions filled with var-=a, var+=a, then?

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

It is written that Tutorial is UPDATED. where is the editorial link?

→ Reply