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

Автор JATC, история, 6 лет назад, По-английски

Hi everyone. I'm glad to announce that the Codeforces Round 520 (Div. 2) will be held on Nov/14/2018 18:35 (Moscow time).

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

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

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

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

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

Why vintage_Vlad_Makeev became blue?

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

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

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

Happy to see another round from Vietnamese.

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

In China,520 means "I love you."




I prefer high rating :)

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

Hi warriors,I'm back;

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

Why gritukan became blue?

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

    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.

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

Isnt it unrated??

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

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

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

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

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

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

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

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

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...

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

    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.

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

    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.

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

What hacks are there? (for any problem)

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

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.

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

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

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

Just 10 more seconds :(

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

Is this not the correct formula for C?

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

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

All naruto characters are in the standings www

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

Я только одного не понял, а сегодняшнее соревнование было все-таки по программированию или по математике?

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

What is solution for D?

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

    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.

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

    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.

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

    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).

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

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.

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

RIP my rate :)

anyone knows B pretest 3?

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

Problem F is simply this but with more cases.

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

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

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

anyone knows problem B test 32?

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

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.

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

    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.

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

      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.

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

    Really? What a disgrace.

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

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

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

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

https://mirror.codeforces.com/contest/1062/submission/45725683

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

Pretests for A were very weak.

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

    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.

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

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

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

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 ?

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

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

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

      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.

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

        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.

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

          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.

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

          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."

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

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

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

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

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

deleted

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

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.

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

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

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

      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

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

I get 247 rated! Thank you!!!!

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

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.

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

Codefores is the best!!!

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

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.

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

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

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

      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?

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

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