jinlifu1999's blog

By jinlifu1999, 7 months 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, gritukan, neckbosov 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. velity

  5. Hacker_White

  6. Ren_shimosawa

  7. UoA_Kanade

  8. just_soso

  9. jijiang

  10. wzz

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  

»
7 months ago, # |
  Vote: I like it +17 Vote: I do not like it

two consecutive rated rounds that's good__

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    7 months 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. :)

  • »
    »
    7 months 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.

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

      GREAT I will give you an upvote :P

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

»
7 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Good time for East Asia participants!

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

    Why so [user:@Phos] ?

    • »
      »
      »
      7 months 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.

»
7 months 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

  • »
    »
    7 months 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

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

      And so that pages can load more quickly. :)

»
7 months ago, # |
  Vote: I like it -26 Vote: I do not like it

1 upvote = 1 pray

»
7 months ago, # |
  Vote: I like it +24 Vote: I do not like it

We will try to bear this round too.

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

    Your pun is soo POLARizing

    It is borderline un BEARable :P

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the problem statements are as short. Good luck to all!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

»
7 months 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 !

  • »
    »
    7 months 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

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

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

      • »
        »
        »
        »
        7 months 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.

        • »
          »
          »
          »
          »
          7 months 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.

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

        I have solved A and B.

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Cute drawings!

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Another cute images contest!

»
7 months 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?

  • »
    »
    7 months 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.

  • »
    »
    7 months 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.

»
7 months 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?

  • »
    »
    7 months 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

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

    C137 SuperJava It is delayed for 30 minutes

»
7 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Is this round a Chinese round?

»
7 months 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

»
7 months 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. ✌

»
7 months ago, # |
  Vote: I like it +52 Vote: I do not like it

"The scoring distribution will be announced soon."

Lies, lies everywhere.

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Support teacher Jin OVO 资磁靳老师

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

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

    • »
      »
      »
      7 months 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

      • »
        »
        »
        »
        7 months 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

        • »
          »
          »
          »
          »
          7 months 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 :)

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

            How's your perform in the contest :P

            • »
              »
              »
              »
              »
              »
              »
              7 months 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. :)

            • »
              »
              »
              »
              »
              »
              »
              7 months 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....

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months 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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the problem statements would be as short and concise as the announcement. Good luck to all!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Who found a palindrome here?

PS. I love palindromes.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yet another Chinese round...

»
7 months 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!

»
7 months ago, # |
  Vote: I like it -24 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it -57 Vote: I do not like it

    Meme

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Doki doki literature club!That's a miraculous game……

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it -33 Vote: I do not like it

      i know im dead inside and i hate my life and i suffer want to hear how my soul died and how demons took over my body? everyone bullies me at school and i keep teling them i will some day achieve great powers with which i will seek revenge they call me gay for some reason so with these powers i will kill all gay people and hang their bodies at bullies' doors and laugh ha ah ha ha at them

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it -33 Vote: I do not like it

      and you bertter delete that \gay anime profile or i will tell my dad who owns this website to get you banned

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

      Oh no, I am alive.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

BJLFZS

»
7 months ago, # |
  Vote: I like it +18 Vote: I do not like it

CONTEST, CONTEST and CONTEST...

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

    RATING, RATING and RATING...

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

      AIM Tech Mini Marathon 1 is an unrated contest.

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

        Then, RATING, TRAINING and RATING ;)

        • »
          »
          »
          »
          »
          7 months 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

          • »
            »
            »
            »
            »
            »
            7 months 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 :)

            • »
              »
              »
              »
              »
              »
              »
              7 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months 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...

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

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

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months 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.

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

  • »
    »
    7 months 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.

»
7 months 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..??

  • »
    »
    7 months 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.

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

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

      • »
        »
        »
        »
        7 months 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

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

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

      Thank you man.

      • »
        »
        »
        »
        7 months 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..

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

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

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

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to all!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is main character of this round this bear ?

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

This is a perfect time for afternoon brazilian students. Thanks

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

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

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

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

  • »
    »
    7 months 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

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

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

»
7 months 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?

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

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

»
7 months 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!!

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope for the short problem statements

»
7 months 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 :(

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

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Another contest without scoring distribution...

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

waiting....

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is registration time end?

»
7 months 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! ¯_(ツ)_/¯

»
7 months 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?

»
7 months 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!

  • »
    »
    7 months 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 :)

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

    one can have 0 friends as well :)

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

    It took two minutes for me!

»
7 months ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve D?

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

    topological sort & DP

  • »
    »
    7 months 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.

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

    i don't know weather it is correct or not. for each alphabet do a dfs.

    at each node select the child which gives maximum count for current alphabet and return it.

    if there's a cycle ans = -1.

  • »
    »
    7 months 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]

»
7 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Very nice round, with good difficulty distribution.

»
7 months ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve E?

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

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

  • »
    »
    7 months 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

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

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

      • »
        »
        »
        »
        7 months 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

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

          can you please elaborate a bit!

          • »
            »
            »
            »
            »
            »
            7 months 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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Time limit for problem Div2D is a bit tight ?

»
7 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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

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

    how you solved E?

    • »
      »
      »
      7 months 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.

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

    can you please explain the solution?

»
7 months ago, # |
  Vote: I like it +41 Vote: I do not like it

k=1 in problem C :)

»
7 months 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

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

    Do you take care of cycles?

  • »
    »
    7 months 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"?

  • »
    »
    7 months 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?

    • »
      »
      »
      7 months 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

      • »
        »
        »
        »
        7 months 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 :)

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

    • »
      »
      »
      7 months 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

      • »
        »
        »
        »
        7 months 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.

        • »
          »
          »
          »
          »
          7 months 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?

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

            Just use memoization.

    • »
      »
      »
      7 months 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

  • »
    »
    7 months 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

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

»
7 months ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

Problem C in a nutshell

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

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

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

    My god this is really accurate. Got hacked.

»
7 months 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

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

    My solution got hacked 10 second after I locked the problem. Couldn't correct it even though I knew what the hack case was :(

»
7 months 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... :<

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it
  • »
    »
    7 months 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.

»
7 months 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.com/contest/919/submission/34754490 code 2 in C++: http://codeforces.com/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 !

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

    because it is JAVA

  • »
    »
    7 months 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

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

      10^6 is fast enough in Java as well. I primarily use Java and have done many questions with such constraints but it was never an issue. Today is the first time I faced this anomaly

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

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

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

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

      • »
        »
        »
        »
        7 months 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?

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

    use BufferedReader for reading in Java

    • »
      »
      »
      7 months 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.

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

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

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

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

          My same code that gave TLE during the contest on prestest 6 is now getting accepted without a single change in the code. Seems like some trouble with the judge, neverthless unlucky me :(

      • »
        »
        »
        »
        7 months 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 ! :(

        • »
          »
          »
          »
          »
          7 months 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

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

            Bad luck comes in all forms :P Haha, thanks for the wonderful contest BTW :)

    • »
      »
      »
      7 months 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

»
7 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Thanks jinlifu1999, Good contest :)

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem C:

»
7 months 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

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

    only 10000 of course brute it

  • »
    »
    7 months 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

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

      You're reading 5 characters at most.

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

![Summary of the contest]()

»
7 months 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.com/contest/919/submission/34769724 LMissher

http://codeforces.com/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.

»
7 months 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 ?

  • »
    »
    7 months 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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone send a code of problem E?

思考熊

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A contest for memory, First time to solve problem in the last minute

»
7 months 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?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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?

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

        I used brute force and it passed.

        • »
          »
          »
          »
          »
          7 months 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.

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

            but it should give TLE .. IT MIGHT BE THAT IN ACTUAL TEST CASE K<10000

          • »
            »
            »
            »
            »
            »
            7 months 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

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

        8 digits is ~10^7

»
7 months 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?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

  • »
    »
    7 months 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.

»
7 months 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)

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

»
7 months 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?

»
7 months 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?

»
7 months ago, # |
  Vote: I like it -10 Vote: I do not like it

It was easy contest

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

jinlifu1999 Thankyou. This was very good contest and good difficulty distribution.

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

  • »
    »
    7 months 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.

»
7 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
7 months 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?

»
7 months 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 :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nyc contest. short and sweet problem statements. and it was exciting.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Recently, a student of my college was found cheating and copying codes in short contests from ideone.com https://discuss.codechef.com/questions/122305/ratings-over-learning

After realising that I was not making any progress on solving problem D, I thought of checking ideone and see whether it worked. I got a solution for problem D which was compiled as public while 20-25 minutes were left for the contest to end. I saved the solution locally.

I just submitted the code, and it resulted AC. A humble request to all, please make sure your codes are private at ideone and other such online IDEs.

My suggestion would be to use Codechef ide or CF custom invocation.

»
7 months 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.com/contest/919/submission/34773421

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

  • »
    »
    7 months 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...

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

»
7 months 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??

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months 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.

»
7 months 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

»
7 months 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 :)

  • »
    »
    7 months 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.