jinlifu1999's blog

Codeforces Round #460 (Div. 2)
By jinlifu1999, 7 years ago, In English

Hello, Codeforces!

It's my honor to invite you to Codeforces Round #460 (Div. 2), which takes place at 13:05 UTC, January 31st. The round will be rated for all division 2 participants. Also we warmly welcome those division 1 participants to join us out of competition. Note that round starts in the unusual time! :)

This round is prepared by me and my friend wuminyan0607. Many thanks to my friend for helping me testing the round and generating testcases. Besides, many thanks to the Codeforces coordinator KAN for giving me a chance to hold this round, testers cdkrot, cyand1317, demon1999, Glebodin, vintage_Vlad_Makeev, FalseMirror for testing this round and MikeMirzayanov for the great Codeforces and Polygon platforms. Without their huge effort, this round would't be possible.

Hope you can find these problems interesting. Wish all of you fewer bugs and higher rating!

The scoring distribution will be announced soon.

UPD1: There will be 6 problems and you have 2 hours to solve them. The scoring distribution will be 500-750-1000-1500-2000-2500.

UPD2: System test is over. Hope you will like those problems. Congratulations to the winners!

Div. 2

  1. OO0OOO00O0O0O0O00OOO0OO (Solved all 6 problems and got 4 successful hacking attempts)

  2. pannibal (Solved all 6 problems)

  3. sasasagagaga

  4. answerrtx

  5. Kemal

  6. Ren_shimosawa

  7. UoA_Kanade

  8. just_soso

  9. jijiang

  10. TayTayTayTaylor

Div. 1 & Div. 2

  1. KrK

  2. Vercingetorix

  3. OO0OOO00O0O0O0O00OOO0OO

  4. uwi

  5. black_horse2014

  6. TonySnark

  7. zscoder

  8. Marco_L_T

  9. quailty

  10. pannibal

UPD3: Editorial is ready!

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

Comments Comments (250)
| Write comment?
»
7 years ago, # |
  Vote: I like it +17 Vote: I do not like it

two consecutive rated rounds that's good__

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

What's the name of the cute character? :P

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

    It's something like "The thinking bear".

    To be honest, I'm not sure about the English name of that character. :)

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

    I think it is from uoj.ac. At least that is where I've seen it.

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

      GREAT I will give you an upvote :P

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

      A partial list can be found here (#2, #3, #5, #6, #7 from the top). I skimmed through my message images and found six more, which altogether are enough to supply two picture rounds (no I don't suggest that).

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

Good time for East Asia participants！

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

    Why so [user:@Phos] ?

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

      Usually this round would begin in 17:35(MSK),for Chinese participants they have to start their work in 22:35(CST) and Japanese even later 23:35(JST). It's too late for most of the students in the East Asia.

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

To be honest, if these bears appear in the problem statements, I'll consider spending the remaining contest time looking at them instead of raging randomly :P

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

    No pictures in problem statement. :P

    So you can focus on solving problems. :P

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

      And so that pages can load more quickly. :)

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

1 upvote = 1 pray

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

We will try to bear this round too.

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

    Your pun is soo POLARizing

    It is borderline un BEARable :P

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

This time, my handle will definitely turn into "Green" . Nobody can stop me !

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

    Haha all the best. By the way you have to solve atleast 4 problems to become green. My advice is solve at least 2 problems consistently in all contests to become stable in green rather than targeting too much once at a time

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

      Regularly solving only A and B is enough to become green.

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

        Yes but his rating is 933.In order to become green he has to get +267 which I think is only possible by solving 4 problems in this contest.

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

          If he solved four problems he will probably become specialist in one round! This is not impossible. worse did something like that.

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

        I have solved A and B.

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

Cute drawings!

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

Another cute images contest!

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

I think that adrozdova is very old nick of demon1999) Why do you use it?

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

    I think it might be because they prepared the blog post way in the past, when it was still his nickname. This is only a guess though.

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

    Maybe testers' Polygon handles are directly copied here — grikukan is also gritukan's former handle.

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

CS Academy Round #67 starts right after the round, is there something to be done about this?

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

    Looks like that we can't participate in both contests.

    UPD: In codeforces calendar this contest is shown in 13:35 UTC. Please fix it.

    UPD: It's fine now

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

    C137 Adhami It is delayed for 30 minutes

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

Is this round a Chinese round?

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

I realized the author is Chinese at the first sight of thinking bear... BTW, I study in SJTU too. It's frustrating that campus network doesn't work from 00:00 to 06:00. So now it's a fantastic chance for us to participate in contests and get higher rating, isn't it?@jinlifu1999

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

I hope the difficulty gradient for this contest will be somewhat better than the last one. 2 rated contest in a row. ✌

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

"The scoring distribution will be announced soon."

Lies, lies everywhere.

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

Support teacher Jin OVO 资磁靳老师

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

solved 2 problems and got 50+ ratings :) , seems cool :D:D

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

    Don't you think of solving 3 or more :P

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

      Yes , I think of solving 3 or more , but , now a days , solving 2 problems is quite tough for me , but i will try my best to develop , and thanks for inspiration :D :D jinlifu1999

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

        Well, your dream of solving 3 or more will fulfill in this round :)

        Believe me :P

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

          Thanks a lot thanks a lot , if it occurs , i will be a specialist soon , pray for me :)

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

            How's your perform in the contest :P

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

              Really 3 were easy problems. The real competition began with the 4th question. :)

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

              3 problems werre passed pretests but C was caught in main test, if it could be hacked in the contest time, I could debug it, but no one hacked mine, so....

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

                So it seems that you're really unlucky. :(

                Hope you can solve 3 next time. :P

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

Will the problems` background happens on "the thinking bear"?

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

Who found a palindrome here?

PS. I love palindromes.

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

Yet another Chinese round...

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

I'm interesting in if the round time was scheduled so that it does not overlap with the round on csacademy? Anyway, coordinators, good job!

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

hope everyone dies in this round :) :> :D xD =) =D <3 (:

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

BJLFZS

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

CONTEST, CONTEST and CONTEST...

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

    RATING, RATING and RATING...

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

      AIM Tech Mini Marathon 1 is an unrated contest.

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

        Then, RATING, TRAINING and RATING ;)

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

          None of this contests are rated for me , so it is sleeping

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

            I hope after this contest my handle becomes like yours and Educational round becomes unrated for me too :)

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

              I also hope after this contest my handle becomes purple and every div.2 becomes unrated for me.

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

                I don't like rated. If I don't do well in this contest, my rating will go down and down...

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

          CONTEST, RATING, TRAINING, CONTEST, RATING, TRAINING ...

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

thinking bear, moe! baidu's only contribution(LUL

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

Can't go to WC,so I'm here for CF round.

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

If it's half an hour ahead, it's perfect.

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

    You can finish this round in half an hour,then go to sleep XD.

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

Please correct the timing of this contest in the Codeforces Calendar. It is 30 minutes ahead.

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

    Please, wait a minute. I will ask the coordinator to fix that :P

    Huge thanks to your correction :P I hadn't noticed that until I saw the calendar.

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

I have a question to those people who submit Problem A just in 1 minute ..??

A problem takes at least 3-5 minute to read from me, So how could you..??

Do you want to share or give me any tips about this..??

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

    It takes 20 seconds to read the problem for me. Maybe it is because I am reading in Russian and Russian is my native language.

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

      Do you read total problem just in 20 sec...!!!!!

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

        Lol. You don't need to read the whole problem statement) Don't read input/output format, skip useless legend or maybe learn to read faster) But it doesn't matter how fast do you solve first problem. 5 minutes or one minute. You need to solve MORE problems, time isn't the most important thing

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

    Usually it takes me from 30 seconds to 1 minute.

    If there are any tips about this, I may provide two: skimming for main keywords and improving your typing speed (for quickly finishing your code).

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

      Thank you man.

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

        Is thank you illegal in codeforces..?? I just have told thank you to Akikaze and some people gave me down vote... Was that necessary..??

        By the way, Due to your down vote I just solved 2 problems..

        Once Again Thank you MikeMirzayanov for creating this platform..

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

    Go read the examples and notes. That works only on A

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

jinlifu1999

Can we have the editorials please ?

Edit : I wanted the editorial for Round #459. I did not notice and asked it here before the start of this contest. Sorry for the misconception.

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

    Bro, you're asking for editorial before contest!!! Whats the rush??? Enjoy the round.

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

      Sorry mate I wanted the editorials for round #459. I'll go there and comment and delete this one. Sorry :P

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

Good luck to all!

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

This is a perfect time for afternoon brazilian students. Thanks

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

30 minutes after the beginning of the round, super blue blood moon rises..

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

    Use Eclipse Luna for this round and you'll be blessed.

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

Just Curious to know, Why some contest have Unusual start time.

I wonder how CF appeals to global audience with all the different time zones. BTW In INDIA I prefer 15:35 UTC.

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

    The author lives in China so that time is perfect for him. but not bad for us BTW

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

    Usual start time in UTC+8 is often in the midnight...

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

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

This is the first time I used this account to participate in CF. What do I need to watch out for?

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

    Hacks, Beware of Hacks and weak Pretests, always gets people XD LOL!

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

It's lunar eclipse today while the contest and it's happening after a long time but consecutive two "fully" rated contest is even rare!:p XD lol. Let's hope it's worth missing the eclipse!!

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

"The scoring distribution will be announced SOON." What does "SOON" mean? :)

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

Hope for the short problem statements

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

Because of the eclipse, I may have to endure the wind on the balcony to participate in this game. I think this is not a pleasant experience :(

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

hope contest will be rated my first contest wish everone big rating so excited about it thank you MikeMirzayanov for platform codeforces.

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

Another contest without scoring distribution...

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

The first time that I'm happy that my flight is delayed! I could participate in a CF round at least! ¯_(ツ)_/¯

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

What does "consecutive" means in C?

Does

2 3 3 **. ...

gives the answer of 2 rather than 1?

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

it took me 37 min to see that k could be 1 in c ugh... the text said for you and your firends that made me thin k>=2

from 1500 to 2500 because of this mistake ...my first life lesson in cf :

READ THE PROBLEM CLEARLY!

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

    Exactly I also thought that I'll always have a friend with me. Took me ages too to get the hack case.

    Same lesson learnt :)

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

    one can have 0 friends as well :)

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

      that one must be a programmer

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

    It took two minutes for me!

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

How to solve D?

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

    topological sort & DP

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

    First of all check for cycles with Tarjans/Kosaraju's algorithm, if there are any (or self edges), the answer is -1.

    Otherwise, create a dynamic programming array dp[N][26], where N is each node.

    The value of dp[v][i] is the maximum of dp[u][i] for each neighbour, +1 if the letter i is the letter of the node.

    The answer is the maximum dp value.

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

    I used the following approach: if there is any cycle answer is -1 otherwise use dp, where dp[i][j] is max path len from vertex i counting character j. Answer is maximum of dp[i][j]

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

Very nice round, with good difficulty distribution.

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

How to solve E?

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

    Hint: Fermat little theorem, Inverse modulo, Chinese Remainder Theorem.

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

    Similar as merging process in merge sort.

    Make a table1 = (k^(-1) * b mod p, k), table2 = (a^k mod p, k)

    Then find a elements s.t. table1.first == table2.first

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

      what is 'k'? is it [1, b]?

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

        [1,b-1] in table1, [0,b-2] in table2

        -> Sorry, [1,p-1] in table1, [0,p-2] in table2

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

          can you please elaborate a bit!

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

            Oh Sorry, my big mistake. Not b, but p.

            first, k^(-1) for k = 1, 2, 3, .. , p-1 may different. and since b != 0, we don't have to care n = 0. So for table1, range is [1,p-1]

            second, a^k for k = 0,1,2,..,p-2 may different. but k >= p-1, since a^(p-1) = 1, we don't have to care about it.

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

what might be the 15th testcase in D ? I kept getting tle .

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

I'm very impressed by the problem E. Very very nice.

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

    how you solved E?

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

      I have just got pretest passed, so solution could be wrong.

      Note that 'a' is co-prime to P. So, powers of 'a' form multiplicative group mod P. Let the size of this group be x. So , for each i, ai = ai + x mod P. Also, by euler's formula, we know x is a divisor of P - 1. So, x and P are co-prime.

      Now, it comes down to finding the number of j ≤ N (N is max limit), such that j·aj%x = b. This is because aj%x = aj mod P.

      This last part can be done using CRT, using the fact that x and P are co-prime.

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

    can you please explain the solution?

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

k=1 in problem C :)

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

What was test 15 in Problem D? I was getting a TLE. Is there a better solution than O(26*(V+E))? I did a DFS and stored the counts of all alphabets in a vector and took the maximum of them when I reached a leaf. I did this for every disconnected portion of the graph and took the maximum out of them.

Edit: It wasn't because of cycles, unless my code for detecting cycles was wrong. I had taken care of them beforehand

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

    Do you take care of cycles?

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

      Yes, I took care of cycles before proceeding to do this.

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

    Do you check the condition "Note that x can be equal to y and there can be multiple edges between x and y"?

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

    I went nuts optimizing my code. I removed the factor of 26, and went to simple DFS (only parameters passed were values u and v). And still TLE!!

    Although I had to make 2 DFs functions (1 to check if theres a cycle in that forest and other for ans from that forest).

    I dont think its complexity problem- there must be some edge case on cycles. Thats what I can think of. Any suggestions?

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

      Multiedges and you don't use a visited array apparently, thus DFS is not O(V + E) anymore

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

        Thank you. Aside from that, I think Len 's case is the thing. For the given configuration, my loop does goto O(N2). Should have been careful. Thank you :)

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

    I don't think your solution is 26 * (V + E).
    Consider test like this
    n -> n — 1
    n — 1 -> n — 2
    ...
    2 -> 1.
    I think you will run O(V) dfses, i-th dfs will visit i vertexes(total V^2).

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

      Why would I run O(V) dfses? I'd just run one dfs for this graph, no? I run multiple dfses only when the graph is disconnected

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

        I don't think that term disconnected can be used for oriented graphs. Everytime if(!vis[i]) will be true because i-th dfs can't visit vertexes > i on this graph.

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

          OH! I get it now. Thanks a lot! Do you reckon it's possible with a modified version of DFS?

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

            Just use memoization.

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

      I have taken care of visited vertices and also I made dfs after topological sorting but still getting TLE in 15th test case

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

    What about complete bipartite graph that has n / 2 vertices in right and n / 2 in left

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

It was my dream to be purple after this contest, but it seemed that I failed.

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

Problem C in a nutshell

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

    Anybody has any idea what the 10th testcase for C might be??

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

That moment when you lock your problem and after that you realize your solution has a bug

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

Anyone with a hint on how to handle E when x/p is greater than p?

My contest in a nutshell: solved 3 first problems in 10 minutes, got hacked in C and recovered right after, stuck with D for an eternity without knowing exactly what I've done wrong, then going on with E and realize that there wasn't enough time to make it perfect...

UPD: Just realized that my topological solution for D has gone completely wrong. Well the suffering seems to have no end... :<

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

F: It is right?

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

    I thought the same, but was too lazy to write it. I am sure there is a smaller solution.

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

I submitted two codes for problem 2 Code 1 in Java: http://codeforces.me/contest/919/submission/34754490 code 2 in C++: http://codeforces.me/contest/919/submission/34757925 Both the codes have exactly same implementation, but, Java code got TLE on pretest 6 whereas C++ Code passed the pretests ! How is this possible?? I don't think fast IO can be a issue here. Can anyone explain why did it happen? Thank you !

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

    because it is JAVA

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

    C++ is faster than Java. 10^6 should be very comfortable in C++, might be tight in Java

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

      why 10^6? for k = 10000 the answer is 10800100 (10^7)

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

        Oh, sorry, I thought he was talking about C.

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

        Got it. But isn't the time limit different for different programming languages?

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

          No, it is like that on some other sites though.

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

    use BufferedReader for reading in Java

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

      I don't think Fast IO can be a issue in problem B.

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

    I wasted much of my time thinking about the reason and then tried C++ and it cleared the pretests immediately ! I don't think That's fair if language really can be the issue. MikeMirzayanov jinlifu1999 KAN wuminyan0607 Please look into my problem and help me. Thank you.

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

      Hmmmmm it seems that it's our mistake. We have tested using language 'D' which seems to be OK. I really have no idea with Java. Sorry for that. :(

      BTW, you could come up with a better brute force. You can refer to editorial after system testing.

      Sincerely.

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

        My java brute force solution passed in approx 1 / 3rd of TL.

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

        I just tried to resubmit my exact Java code for problem 2 right now and guess what it got accepted. Exact same code gave TLE on pretest 6 but now it cleared all the tests. Link to code 1 giving TLE Link to code 2 accepted Seems like there was some problem with the judge. Unlucky ! :(

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

          On the bound of the TL passing system tests really needs to be lucky :P

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

      You should not have used long, and it would probably have been faster

      (CF system is 32bit)

      edit: here 34773486 it passed with int in 655ms

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

Thanks jinlifu1999, Good contest :)

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

Problem C:

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

Am I the only one to do binary search with digit dp in B? :D

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

    only 10000 of course brute it

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

    I think Brute force without Fast I/O will give TLE,if you are using i++. Edit:-it seems it won't be problem here

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

      You're reading 5 characters at most.

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

![Summary of the contest]()

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

JUST WTF MAN!! I wrote code for E and put it paste.ubuntu.com for sending it after contest (I sent link to myself so I could send code with mobile phone). Now I looked some peoples' code and I see they just COPIED MY CODE. How this happens! Is there any reliable paste site?

My code created 14:22:32: https://paste.ubuntu.com/26495347/

Some examples sent after my code:

http://codeforces.me/contest/919/submission/34769724 LMissher

http://codeforces.me/contest/919/submission/34769669 20155603

I know it's my mistake, but I want them to get disqualified from contest as it is really unfair.

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

Am I the only one who saw k=100000 in B and spent 1 hour thinking about how to solve it ?

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

    Even if k=100000 you can use the same solution that you use for k=10000. Just ran my code and it was < 1 s.

    EDIT: Didn't realize you could literally brute force every number. I had tried that and it seemed too long for k=10000, so I did another sort of brute force enumeration, enumerating in lexicographically smallest order.

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

Can anyone send a code of problem E?

思考熊

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

In problem B, is there a way to estimate the number of digits in the 10000th perfect number?

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

    The number of perfect number with length N is approximately the number of way to put 10 balls into N boxes, which is Combinatoric(N + 9, N) by stars and bars theorem.

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

      Thanks!

      To anyone else wondering, check out this code. The number of perfect numbers with digits <= 7 is ~ 7997. Hence the 10,000 perfect number should be of 8 digits.

      Do you think the brute force solution would pass the system tests?

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

        I used brute force and it passed.

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

          Almost everyone in my room used brute force. I was talking about the main tests. Logically I could argue that a loop of 10^8 calculations should give TLE. But thats not the case as all the top participants have used brute force.

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

            You can just test k=10000 locally (why are you lazy, it's so simple) and see that result is 10800100 (order 10^7), thus calculating the sum of digits takes at most 8 iterations, 8*10^7 simple operations can pass easily

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

        8 digits is ~10^7

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

In problem D, the problem statement says a path's value. Path in most cases means the vertices cannot repeat in the path. But the question assumes that the vertices can repeat and hence the answer is -1 if there is a cycle in the graph. I only understood the assumption after looking at the second test case and wasted a lot of time before that. Anyone face this problem?

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

    The last line of the statement says "If the value can be arbitrarily large, output -1 instead.". Should be pretty clear that "arbitrarily large" means infinite path and therefore cycle. Just my opinion.

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

      I shouldn't have to infer it from the question which is in general not expected. I anyway inferred the same after seeing lot of submissions on the question. But that took sometime and nobody should waste time during the contest.

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

    Same here. I'm amazed how everyone else was OK with this. Poor problem statement IMHO.

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

Whats Happens if I get a TLE on the first pretest of a problem? Do I get a -50 points for it?

(I know that there is no penalty for a WA but am not sure for a TLE)

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

Note to self: remember that an element's order in Z_p is not necessarily p -1. I failed E because of this. Oh well.

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

i did a normal dfs on problem D and i count the value after reaching each leaf and get the maximum value between last value and this value,but i got wrong answer. can someone tell me why my solution is wrong?

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

Can someone please help me to figure out difference between my solution and this solution. It seems same but my solution is giving TLE.

mathmaniac, we both have done same thing. What is the problem with my solution?

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

It was easy contest

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

So problem C says "You need to find k consecutive empty seats in the same row or column and arrange those seats for you and your friends", and "k consecutive empty seats" means "k seats that are consecutive without considering those seats that are occupied" instead of "k seats that are consecutive and they are all empty". That's why I'm hacked...

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

    No, "k consecutive empty seats" means exactly "k seats that are consecutive and they are all empty". You got hacked because you didn't treat the case k=1. For example, on test

    2 2 1
..
..

    Your code prints out 8 instead of 4.

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

I don't understand why submission http://codeforces.me/contest/919/submission/34754490 although submited at 00:42:27,it is has been run after all other submissions.

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

Can someone see why this submission TLE for problem D 34771026? or it is just because of time constraint is too tight for Java?

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

Height of UNLUCKINESS. Got one test case wrong only enough to destroy rank in 4th problem. So remember even one test case after pretest pass is sufficient to kill you temporarily :(. Thanks for the beautifully designed problems in the contest :)

→ Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it +7 Vote: I do not like it

My submission in Java for problem D gets TLE on test 32. Am I missing something? http://codeforces.me/contest/919/submission/34773421

Edit: Somehow this submission of mine gets AC :P http://codeforces.me/contest/919/submission/34778206

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

    The same situation :( It's a pity that any solution on C++ passes...

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

Great Contest! I did not realise a brute force solution would pass in B and ended up coding and debugging a DFS :P Anyways, a nice lesson for the future.

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

Why i have a time limit exceded In my C submisiorn C++11 compiler and why i have accepted in c++14 compiler??

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

Who is OO0OOO00O0O0O0O00OOO0OO ?

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

So what is the problem with the D's 15th test case?

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

    I got TLE for 15th test case because there was an issue in my modified DFS. I forgot to put vis array check and it got TLE. After putting the vis check, it got AC.

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

Hi, I'm not sure if this is the place to put it but please re-evaluate my solutions for contest 919. The system claims that neutron-byte/34741180 is too similar to czommerfelds/34745389. The solution is very simple so it is no surprise it would be similar. Also the first result on Google for "c++ sum of digits" yields the exact same function http://www.sanfoundry.com/cpp-program-display-sum-of-digits/. Thank you. Best, Christian

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

With all due respect I didn't like the contest that much ... the reason is mostly because problems D and E were not a challenge and this increases the expectation for problem F , and 'F' was only hard to code and didn't have that much theoretical beauty in my opinion Though I surely hope the next rounds jinlifu1999 would come up with will be much better :)

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

    Thanks for your comment.

    I think I will come up with better problems (perhaps challenging for Div.1 participants) if there will be "next time". :P

    Thanks.

    → Reply