Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

JATC's blog

By JATC, history, 5 weeks 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 _kun_ for coordinating me in preparing the problems, gritukan, 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. I_Love_Kirino

  2. Dark_Warlock

  3. wcysai

  4. coriander

  5. fcwwww

Unofficial participants:

  1. BudAlNik

  2. HIR180

  3. KrK

  4. ayaze

  5. FCB1234

Tutorial UPDATED

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

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it

Why gritukan became blue?

»
5 weeks ago, # |
  Vote: I like it -54 Vote: I do not like it

fuckme please.

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

Happy to see another round from Vietnamese.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    a vừa tổ chức thi freecontest lại còn thi bên này nữa lun hả

»
5 weeks 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 :)

»
5 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

Hi warriors,I'm back;

»
5 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Why gritukan became blue?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    Because at the moment they post this he was blue.

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it

Isnt it unrated??

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I m not able to register for the contest ?

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Whenever i try to submit it says you should be registered, although i registered for it yesterday itself, Please help

»
5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    now he is even first place, lol

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      5 weeks 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?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    They all got banned. Thanks, admins!

»
5 weeks ago, # |
Rev. 2   Vote: I like it -64 Vote: I do not like it

»
5 weeks 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...

  • »
    »
    5 weeks 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.

»
5 weeks 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...

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks 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.

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What hacks are there? (for any problem)

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just 10 more seconds :(

»
5 weeks 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)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

All naruto characters are in the standings www

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

What is solution for D?

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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).

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

RIP my rate :)

anyone knows B pretest 3?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's 10^6

    • »
      »
      »
      5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's 256 or 64 I guess..

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Problem F is simply this but with more cases.

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone knows problem B test 32?

»
5 weeks 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.

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Really? What a disgrace.

  • »
    »
    5 weeks 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

»
5 weeks 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.com/contest/1062/submission/45725683

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretests for A were very weak.

  • »
    »
    5 weeks 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.

»
5 weeks 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.

»
5 weeks 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 ?

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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.

      • »
        »
        »
        »
        5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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."

»
5 weeks 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.

»
5 weeks 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.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

deleted

»
5 weeks 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.

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

I get 247 rated! Thank you!!!!

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Codefores is the best!!!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems that hatuanlhpk97 and trung289123 cheated during the contest. The codes are basicly the same but with random stuff added to hide it.

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Cheaters should be punished. I am still struggling to become a pupil :( and here these guys are cheating.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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