M.Mahdi's blog

By M.Mahdi, 8 years ago, In English

Hi!

We're glad to invite you all to participate in Codeforces Round #360(Div. 1 and Div. 2) which will take place on Wednesday, 29 June, 20:05 Moscow time. Check it in your timezone!

The problems are designed by Man (Parsa Abdollahi) and me. It's our first Codeforces round and we hope you enjoy competing it as much as we enjoyed preparing it! (^◡^)

Our special thank goes to JeBeK (Peyman Jabbarzade) who helped us a lot in preparing and testing the round. Many thanks to GlebsHP (Gleb Evstropov) for his help in preparing the contest, and MikeMirzayanov (Mike Mirzayanov) for great platforms Polygon and Codeforces. We also want to thank Zlobober (Max Akhmedov) for testing our round.

We wish (and expect!) you all many Accepted solutions! ( ゚▽゚)/

UPD: Problems are going to be about Pari and Arya.

UPD2 Congratulations to the winners!

Div. 1:

  1. jqdai0815
  2. tourist
  3. Egor
  4. xyz111
  5. subscriber
  6. riadwaw
  7. ainta
  8. jcvb
  9. Um_nik
  10. Shik

Div. 2:

  1. Julek
  2. polygonia
  3. Snipx
  4. I_love_littlechild
  5. AminAnvari
  6. Shayan
  7. yashkumar18
  8. Archies
  9. Clone3
  10. lature

Editorial + some challenges will be published soon.

UPD3: The editorial is out!

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

| Write comment?
»
8 years ago, # |
  Vote: I like it +70 Vote: I do not like it

Very good time ! Thanks Mr.Shokri

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

    Yeah , same for us. :)

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

    Very terrible time! It is 01:05 in china.If my mom find the light in my room at that time, she must kill me! Awfully!

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

      Then try to win the round and you'll have an excuse! :)

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

      Same in China T_T

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

        Actually, that was China too. :|

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

          I think he might have meant, "It's the same for me, I'm in China as well."

»
8 years ago, # |
  Vote: I like it +114 Vote: I do not like it

I hope both tourist and Petr will participate. And let the battle begin!

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

    You should also hope both JIBANCANYANG and jqdai0815 will participate.

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

      But you can't compete in the same division right?

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

        When I was in America, I used Facebook, Twitter, and many other social networks that Americans are using.

        Usually the first thing I feel when I open either online web pages or their mobile apps is that the UI is simply ugly, untidy and not easy to read. And when I look deeper into them, I found the logic of menus are usually not user-friendly. Company as large as Facebook spent too much space of their app menus to show the privacy settings or other. Are these settings necessary? Maybe. But Facebook puts them their to avoid law suit rather than help the users to achieve some useful function. (Sometimes few people like to sue a company who provides them free service for the service is not good enough lol)...

        Regarding the mobile app. I noticed that Facebook and Twitter consume a lot of data but providing no more information than WeChat and QQ. I think they just don't care about optimizing app performances. The iOS version of Quora is another example. Is it really necessary to refresh the entire frame every time I move into the detail page of a question and move back to main feed? The app works like a web broswer rather than an app. It is slow and waste too much data.

        As a person who uses Chinese apps more often, I have to say that the user-experience of these popular International social apps s-u-c-k...Forgive me for bad words. But before I explore the content, the web design and app performance are already pushing me away.

        Once I look into the content. I feel that there is nothing more interesting or more important as well. I can not even come up with an example about the important and valuable information I acquired from Facebook (Trump is winning? China does not have democracy? lol). Even my American classmates do not really like using Facebook any more...

        In terms of functions. Alipay and Wechat Pay in China has achieved I believe everything Apple Pay are still trying to achieve. We scan our phones to check out in restaurants, super markets. We order tickets, hotel rooms and we call cabs with one finger, in one app...

        As a whole, I do not see any significant advantages Facebook or other social networks have over convenient and beautiful local apps...If there is one, maybe arrogance and ignorance? Because they even believe that the reason why they do not have too many Chinese users is that China Government bans them...

        Maybe they will experience a user number explosion at the first several weeks of cancelling the banning order. But everything probably just returns to the beginning after all.

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

        R E K T

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 3   Vote: I like it +26 Vote: I do not like it

        Lucky jqdai0815... #:-s

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

      be glad. jqdai0815 will participate

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

    Petr didn't participate but tourist is currently 2nd and last time he was second he had a -48 rating change. Petr still has a chance :)

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

    Come on, now it becomes even more thrilling!

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

That is a good time

Good luck guys

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

    That is a good time Good luck gays

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

    i hope to get into the same room to take my revenge and hack you as you hack me last contest

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

      It's a good thing to hacked :3

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

        Unlucky me , didn't get in the same room maybe i'll take my Great Revenge later ,,,, time pass and revenge grow up

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

      Better to get hacked than to get system test failed.

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

        In case you have not locked. Otherwise, you feel bad due to locking in case of hack.

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

      You should thanks hacker because your solution is Wrong and you can fix before contest end :)) :))

»
8 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Whoa, it starts at 2:00 AM and ends at 4:00 AM... I'll have to go to bed early in the evening and wake up then.

And I couldn't but add some emojis. (๑>ᴗ<๑)

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

    It is really sorry, and I guess you are Indian from your time.

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

      No, she is a Korean I believe.

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

        Is there any reason to believe this person is a 'she'?

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

          It just doesn't feel right if she is a boy based on her profile picture and her typing style.

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

            Hmm... well I wouldn't hold such prejudice. Cause well...I'm pretty sure your wrong on the gender thing.

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

              As a matter of fact I am a girl. Why do you think I am not a girl?

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

                I don't believe you're not a girl. Nor have I expressed that belief. I myself am gender fluid, I literally can't make gender distinctions.

                Okay, I was being vague on purpose. I happen to know that person. You may observe we go to the same school...

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

                  I see. I misunderstood your words because I am still learning English...

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

                Why do you not participate in contests?

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

                  Because I sleep early and codeforces round are always so late in the midnight.

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

            Wait how can you tell someone gender by typing style.

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

              Because he used cute emojis and boys I met never use emojis... Maybe I should meet more people.

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

      The time difference between this round and the previous one is only half hour, I don't think half an hour is a big deal!!!

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

But it is really quite too late for me..

»
8 years ago, # |
  Vote: I like it -12 Vote: I do not like it

excited for the round

»
8 years ago, # |
  Vote: I like it +79 Vote: I do not like it

So it's in radians :) :D :v

»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

11:05 pm to 01:05 am(Bangladesh) then wait for system testing.... then wait for rating.......DAMN!

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

    After That Bangladeshi people have "sehri" and Sleep :)

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

      I think the time is perfect for Bangladesh people this time...

      "tarabi" > diner > contest > wait for system testing > ("sehri" + wait for rating ) > go to sleep :)

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

whoa, I can sleep longer =))

If CF contest starts at usual time, I just have 2 hours to sleep; but today I can sleep in ~3 hours (maybe)

Although the contest starts a half an hour later, I feel very comfortable and excited =))

Hope the contest goes well =))

*p/s: sorry for bad English =))

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I have Linux embedded system final tomorrow, but nothing stops me from participating this round :>

»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

pari?!

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

    napari ?

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

    Pari is a Hindi word for 'fairy'/'angel' in English.

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

      I think it means an angel and not a fairy .

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +46 Vote: I do not like it
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        Exactly, India was once part of Persian Empire and thus origin of a lot of Indian words is Iran, not India.

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

          india became india after 1947, earlier it was(at the time of mughals and before) just indus valley civilization!

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          India has many different language derived from many different language branches. Using the term "Indian words" is like using the term "European words". It doesn't make sense. Most of the Indian languages were developed before the Muslim conquest of India so has very little to do with Muslim/Mughal empires.

          The only language influenced by Muslim/Mughal rulers of India is Urdu which is spoken by Muslims across India.

          Some of the Indian languages like Sanskrit and Hindi might have similarities with Persian language because they were derived from a single source. Refer: https://en.wikipedia.org/wiki/Proto-Indo-European_language.

          Though I am not going to debate on exact origin of word Pari, I would definitely disagree with your sweeping statement that "origin of lot of Indian words is Iran". It's complete BS.

»
8 years ago, # |
  Vote: I like it -16 Vote: I do not like it

plz tell me the name of the BOOK or link of VIDEO tutorials from which i can learn PYTHON from very BASICS.I know C .

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

    I started to learn from this link. I really recommend this. This link is the best resource that you'll ever get.

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

Hello, I am a new user here. I was wondering whether editorials are released for every contest and where do I find them?

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

    Go to contest page(problemlist), after that find "Tutorial" in the bottom of the right panel, next to "Announcement".

»
8 years ago, # |
  Vote: I like it +208 Vote: I do not like it

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

    A girl is Arya Stark of Winterfell and is going home.

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

    Pari, she calls herself.

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

    : |||||| People never want to stop spoiling ...

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

      People never want to stop not watching GoT on time and complain about the spoilers.

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

    Actually Arya meant in this statements is a Persian boy, not Arya Stark (But it'd be great, right?).

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

SUPER COINCIDENCE: We have national team trainings currently going on and at every break we play tank trouble game just like Arya :D

»
8 years ago, # |
  Vote: I like it +82 Vote: I do not like it

Pari must be a fake account of Arya.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Plus for Pari and Arya!)

»
8 years ago, # |
  Vote: I like it -17 Vote: I do not like it

In fine :)

»
8 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Actually, trying to get AC with suboptimal solutions is a good strategy quite often — for example vs .

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

    I'm pretty sure by unoptimal solutions he means "tofs" (thats what we call it in farsi) it means spits, things that aren't supposed to work but take advantage of the tests, like Submitting a solution which is n ^ 2 but has a lot of breaks or a wrong solution which passes because there were no tests against it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if the girl has a name a man can bring back her eyes - the girl has no name.

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

    it looks like someone banged your head on keyboard while registration ,no offence intended :)

»
8 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Ac is an Ac, no matter if it's optimal or not

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

    of course but trying to get AC with non-optimal solutions isn't so smart

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

      I thought so, but then I saw people getting ac with brute force solution in this gym problem Polycarp and Palindromes in a contest where I couldn't come up with an optimal solution...

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

    hacks are coming and they will be here soon

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

      So it's gonna be your day today :D

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

        in div2 rounds I hack others , but in div1 I'm the one who will be hacked hahaha

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

          loool

          the hunter becomes the prey :3

          Good luck up there :D

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

            thank you

            Good luck down there :D

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

            down there , here I come

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's holiday here \o/!!..hope weird problems haha

»
8 years ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

tourist has been already registered , waiting to see Petr too in the contest.

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

    when I was div2 few days ago , I was just like you waiting for them to register and see what they can solve , but now I'm not waiting for them at all . just wishing to stay pink as long as I can hahaha

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

    tourist 1st on CodeForces , peter 1st on TopCoder

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

How many problems and score distributions?

»
8 years ago, # |
  Vote: I like it -46 Vote: I do not like it

Arya be like...

Today she will slay us with the statements!

»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

The name of the problme E in div 2 should be "SUCH THAT". :p :p

»
8 years ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

[Temporary Deleted]

»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Good Fight Between tourist & jqdai0815 :)

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

How to solve D?

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

    If you know value of , then you can know value of . Infact, it will be same.

    Proof is very simple. . You know value of t. Write x = k * (a * b * c) + t, where k is some integer. Now, you can see that
    $x \, \% \, a = t
    $x \, \% \, b = t
    $x \, \% \, c = t

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

    I have used this approach: (c1*c2*c3___*cn + 1) and 1 will give same modulo (equal to 1)on dividing with c1,c2,c3___cn. Now check whether (c1*c2*c3___*cn + 1) and 1 give same remainder on diving with k. If yes ,print yes else print No. EDIT:It will fail system test as it is WA on: 2 4 2 8

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

    You need to compute LCM of all numbers and check that it is divisible by K. To avoid overflow after each LCM operation you can do GCD with K. Then the final number should be equal to K.

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

      How to prove such solution?

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

        Two numbers x and y have the same remainder modulo c[i]'s if and only if abs(x-y) = lcm(c[1], c[2], ... c[n])

        Now if x mod k and y mod k are not the same, then there will always be ambiguity for Arya. x mod k and y mod k will be the same iff lcm(c[1], c[2], ... c[n]) % k is 0 since the differ by this amount (or a multiple of this amount)

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

          from where i can learn those type of theory?

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

            From the CF comments section after a failed attempt to solve a problem :P

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

        If LCM of c1,c2..cn is not divisible by K, then (x+ m*LCM) (m= any +ve integer), would give different remainder for K, but same for c1,c2..cn as m is increased. Hence, not possible to uniquely determine remainder with K

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

        Here is another view on the problem and explanation.

        Any set of distinct numbers C (e.g. c = {3, 4, 6} as below) "generates" unique remainder sets for increasing positive numbers X with Period = LCM(c1, c2, .. cn). Those unique remainder-sets allow to uniquely distinguish remainders x mod k. E.g. remainders row "2 1 5" always correspond to (x mod k) == 5, or "1 2 4" to (x mod k) == 10. So to have things unique CycleLength = LCM(C) needs to be "syncronized" with K, more presicely it needed CycleLength % K == 0.

        Out of that two solutions come:

        1. Find LCM and check if it is divisible by K. If true "Yes", otherwise "No". Solution #1

        2. Factorize K to prime powers. E.g. factorize K=108 to 4 * 27, or K=12 to 3 * 4. If EACH of that prime powers divides any number from C-set — the answer is "Yes", otherwise "No". In fact it has the same meaning as in "1": if each prime power from K can be found in some subset of C numbers then => (c1*c2*c3*..cn) % K == 0, which leads to LCM(c1,c2,c3..cn) % K == 0. Solution #2

        k = 12, c : {3, 4, 6}
          x = 01, rems: 1 1 1 , i mod k = 1
          x = 02, rems: 2 2 2 , i mod k = 2
          x = 03, rems: 0 3 3 , i mod k = 3
          x = 04, rems: 1 0 4 , i mod k = 4
          x = 05, rems: 2 1 5 , i mod k = 5
          x = 06, rems: 0 2 0 , i mod k = 6
          x = 07, rems: 1 3 1 , i mod k = 7
          x = 08, rems: 2 0 2 , i mod k = 8
          x = 09, rems: 0 1 3 , i mod k = 9
          x = 10, rems: 1 2 4 , i mod k = 10
          x = 11, rems: 2 3 5 , i mod k = 11 !!! Cycle end.
          x = 12, rems: 0 0 0 , i mod k = 0  !!! New cycle iteration.
          x = 13, rems: 1 1 1 , i mod k = 1
          ...
          x = 22, rems: 1 2 4 , i mod k = 10
          x = 23, rems: 2 3 5 , i mod k = 11
          x = 24, rems: 0 0 0 , i mod k = 0
        
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      LOL. I have checked if K is divisible by LCM(a, a + n) ._.

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

      "To avoid overflow after each LCM operation you can do GCD with K" How can we prove that after taking GCD with k answer will not be affected.

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

        We are interested only in divizors of K. Other numbers give no information about X mod K (by Chinese Remainder Theorem). Therefore with GCD we will not interesting divizors.

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

    Check if k is divisible by (LCM of all c[i]).

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    lem1: if you have reminder of x to two numbers p&q that gcd(p,q)=1 you can understand reminder of x to pq.

    lem2: if you know reminder of x to ba so you know reminder of x to a.

    so if k = p1^a1 * p2^a2 * ... you have to check that all p1^a1 & p2^a2 & .. are in all c's or not.

    i forgot to check ai s & i get wrong answer :'(

  • »
    »
    8 years ago, # ^ |
    Rev. 5   Vote: I like it +16 Vote: I do not like it

    Let's say we have input:
    n = 6 k = 7
    c1 = 1 c2 = 2 c3 = 3 c4 = 4 c5 = 5 c6 = 6

    Now we can create the table of remainders R[ci][xj]. Each cell contains the value x mod c:

    ci \ xj 1 2 3 4 5 6 7 8 9 10 11 12 13 14
    1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    2 1 0 1 0 1 0 1 0 1 0 1 0 1 0
    3 1 2 0 1 2 0 1 2 0 1 2 0 1 2
    4 1 2 3 0 1 2 3 0 1 2 3 0 1 2
    5 1 2 3 4 0 1 2 3 4 0 1 2 3 4
    6 1 2 3 4 5 0 1 2 3 4 5 0 1 2
    7 1 2 3 4 5 6 0 1 2 3 4 5 6 0

    Now let's look at the 1'st column (from top to bottom):

    ci 1 2 3 4 5 6 7
    0 1 1 1 1 1 1

    We can think that the vector  = (0, 1, 1, 1, 1, 1) corresponds to 1 mod 7 = 1.

    Now let's look at the 2'nd column (again, from top to bottom):

    ci 1 2 3 4 5 6 7
    0 0 2 2 2 2 2

    This column can also be represented as a vector  = (0, 0, 2, 2, 2, 2) corresponding to 2 mod 7 = 2.

    Each column is a vector representation of the corresponding value x.

    Depending on the value of x, we get different columns of remainders. If it is possible to form a function , then the answer is "Yes" (we can determine the value x mod 7 by using only remainders x mod ci). If you cannot form a function (i.e. the same input vector can lead to different values:  =  and f( )  ≠  f( ) ), then we cannot properly encode a single remainder x mod 7 with a vector of remainders of ci. In that case, remainder x mod 7 has more capacity to store information about x, then the capacity of the whole set of ci values.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Who else got Div2 C: Wrong answer on case 15?

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

    Me, because I forgot that the graph may have more than 1 connected component.

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

    I got too many TLE on testcase 15 and it turned out to be I was using global "i" in bfs function. ;((

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

    connected components!

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

      Also, even if it was given that there is only one connected components formed by the edges, another issue might have been using 1 as a root for BFS. It might be the case that 1 is actually disconnected.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

dat feeling when u finished div2C solution with 40 seconds on the clock, submit, but forgot you used zero-based indexing... :(

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where's the editorial??

»
8 years ago, # |
  Vote: I like it +225 Vote: I do not like it

After solving ABC I checked whether I didn't register for Div2 contest ._.

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

    How to solve C easily?

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

      Note that picking a good subset (k; x) is like picking two subsets — one with sum x, the other with k-x.
      That leads to an obvious O(N * K^2) dp solution.

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

      I hope this will be descriptive enough (dp are bitsets):

      dp[0][0][0] = 1;
      RE (i, n) {
        int a;
        cin>>a;
        FOR (prv, 0, k) {
          dp[i][prv] |= dp[i - 1][prv];
          if (prv + a <= k) {
            dp[i][prv + a] |= dp[i - 1][prv];
            dp[i][prv + a] |= (dp[i - 1][prv] << a);
          }
        }
      }
      
      
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Will solution with bool array get TLE?

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

          No. 500^3 is still pretty fast (my code took 15ms xd). I chose bitsets, because they were pretty handy here.

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

            I recieved TLE on test 19 using a O(N*K^2) solution. :-(

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

      Maintain an array of sets S[i][j] = numbers you can make if you get a subset of c[1..i] which has sum j (bitset recommended). Consider the cases:

      i) Your subset doesn't contain c[i]

      ii) Your subset contains c[i], but you don't use it (to make sum j)

      iii) Your subset contains c[i], and you use it

      Bitset can help you union these sets quickly. It is obvious that you just have to maintain last 2 rows of array S, so the space complexity is O(K^2)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a very good contest! Thank you! My favorite task is c! And can anybody explain d?

»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

User fakee clearly got some sweet revenge against Barichek:

On another note: Thanks to the authors for a nice contest I enjoyed solving the problems a lot. I hope you will make more contests!

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I got TLE in TC 19, div2E...

»
8 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

A lot of solutions will fail in Div2D including mine. I hacked all the solutions (there were only 2 :p ) in my room with this case.

2 8
2 4
Output should be: No
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I'm sorry, but why?

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

      X=1 and X=5 give the same remainder when divided by 2 or 4 but they give different remainders when divided by 8.

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

      For example, you can't tell if its 5 mod 8 or 1 mod 8

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

      For X = 1, 1%2 = 1, 1%4 = 1

      For X = 5, 5%2 = 1, 5%4 = 1

      So, you can't really uniquely identify X % 8.

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

      Check 1 and 5, they have same reminders mod 2 and mod 4.

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I don't think div1 C should be div1 C.

»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

It took me whole contest to solve Div2 C,D,E. It took tourist and TooSimpIe just 12 minutes to do that!

»
8 years ago, # |
  Vote: I like it +49 Vote: I do not like it

Is O(qm) intended complexity for div1-D?

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

    If it was, then the task was all about optimization and luck. I got TLE in pretest 15 with O(qm) but kllp passed pretests in 2600ms with the same idea and time complexity.

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

    my (NlogN + M * (DSU)) per query passes in 2 seconds.

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

    Our solution is .

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

    I got O(q·(m + n·logn)) in 967ms: 18804248

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

    I've got O(mq3 / 4α(n))

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please check my solution for Div2C 18806227 ? Thank you.

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

    Try to add g[v].push_back( u ); your code.

»
8 years ago, # |
  Vote: I like it +58 Vote: I do not like it

I'm curious if the O(qmα (m)) is intended solution in div1D. If so — why limitations are so strange (n, m ≤ 105 will be ok). If no — seriously?!

And Oscar goes to foreach .. break in div1E. Spend about 20 minutes trying to solve problem without break. With break problem becames... div1C.

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

    FYI, I have in D.

    How to solve it with that break? At the end, I came up with the following solution but don't know if it's correct. Find SCC's and for each SCC from which there is no edges find the smallest cycle. The answer is .

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

      I think it is correct (I hope so :) )

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

        It's funny that for much time I tried to solve a version without break too. Still, it's our fault, not organizers. And I'd say it's at least div1D difficulty, not div1C.

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

          Yeah, but they could write much more readable code. It looks like it was intended :)

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

          I wouldn't say it's like D, I don't solve D in 20mins like it solved E)

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

    I think using segment tree to store the useful edges in its range can solve div1 pD in , which is asymptotically faster but...:P

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

    OMG, that break is not within if --___--?? Where is the hidden camera??

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

    n, m ≤ 10^5 still holds when n, m ≤ 10^3.

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

      There was no m ≤ 1000 condition.

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

      but m is up to 5·105

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

      = = I meant the pretests are probably weak that it looks like n, m <= 10^3.

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Hints for Div1 D?

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

    suppose k = 2^3*3^7*5^3, then you just need modulo wrt to 2^3,3^7,5^3 to find modulo wrt k. Note that if you have modulo 2^2 and not 2^3, we will fail

    To find modulo wrt to 2^3, just check if on of the numbers is divisible by 2^3.

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

    sort edges in descending order . You need to find the first index such that edges taken till that index form a non bipartite graph .

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Terrible grammar. Someone send the statements to jacksfilm for YGS

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is what I tried for Div 2 C. Can someone tell me the fault in my algorithm. So I maintain two hash maps for the two Vertex Covers. Initially I pick up the first edge, and put each of the vertices in this edge in each hash map. So if edge is (u, v), then A hash map will contain u and B hash map will contain v. I then have 2 copies of the edges of the graph, namely s1 and s2. For s1, I remove all the edges incident on u. For s2, I remove all the edges incident on v.

Now I call a function that processes my logic. So basically I check all the edges from s1, Let the current edge at any time be (u1, v1). So if u1 is present in hashmap B, and v1 is also present in hashmap B, then its not possible to split and I print -1. However if one of them is present in hashmap B, for example say u1 is present in hashmap B, I add v1 to hashmap A, and remove all the edges incident on v1 from s1, and continue the same procedure for other edges in the set. I am unsure of the case where neither of them is present in hashmap B. In that case I do not know which vertex I should add in hashmap A.

Finally, after removing all the edges from s1, and no problem was encountered. I proceed to call the same function for s2, but now interchange the roles of hashmap A and hashmap B. If after doing the same process, if s2 set becomes empty, and there was no problem. I print out the keys of the hashmap in sorted order. So my question relates to that step when neither of the vertices in a given edge are present in the other hashmap. In that case which, edge should I consider adding. I thought of a solution to add the vertex with higher degree, but I guess it won't be correct. Any help would be appreciated. Thanks!

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

    Consider a square-shaped graph, and pick any edge as the first edge. If when processing s1, the edge opposite to this edge is checked, since this edge is also in s2, the function fails. However a square shaped graph has an answer in the form of opposite vertexes (A: (1, 3), B: (2, 4)). Is this what you meant?

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

Last time tourist got on second place at CROC he got -48 in rating. Toady he is on second place again and 30 minus points is enough for getting petr #1 at codeforces. (let's just wait for the rating changes :D)

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

In Div1-C Problem. What i and j are here ? Are they 2 subset sum ? Errichto Solution 18788820

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

    Yes, two subset sums. Consider dividing elements into three parts with sums i, j and s - i - j where s denotes the sum of elements so far.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What a round. It felt like i was giving an English Language exam -_- Wasted 90+ minutes to understand the problem D (Div 2) and still i didn't get what it actually asked -_-

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How funny!!! What were the system tests for Div2 B? My wrong code got AC! :p

Here

»
8 years ago, # |
  Vote: I like it -77 Vote: I do not like it

I am quite surprised by JoeyWheeler's performance.

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

    Thanks mate >_>

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

    What is so surprising? He solved 3 easy problems with a little mistake in one and got stuck on harder problems (D's acceptance rate is inflated because of passing bruteforces). Happens to me all the time and remember about tourist's 168th place once.

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It seems that Div2D simple solutions are getting AC just taking lcm. I believe that it wouldn't be difficult to construct a counterexample using large primes and the product will overflow. Can someone tell me if I'm right or it can be proved that it will fit in unsigned long long?

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

    Even if you calculate lcm as a*b/gcd(a,b), the a*b part cannot exceed 1000000*1000000, which fits under long long int range.

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

      It is just in the first operation, but after it should overflow. Anyway, in the submission I saw, the guy used some smarter approach to make it pass.

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 3   Vote: I like it -10 Vote: I do not like it

        I used gcd instead of lcm so that it would never overflow. (Failed in systests because of a bug but this one works.)

        Submission

        Edit: sorry, just realized I had previously put the wrong submission

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

    I tried to hack such submission, but finally noticed that the guy made a[i] = gcd(a[i], K) before. Then LCM will not overflow K.

»
8 years ago, # |
  Vote: I like it -15 Vote: I do not like it

fuck cin/cout.... (problem D div 2)

»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Today I managed to be solving three (!) problems which were not tasks prepared by organizers :). In Div1D I considered intervals of cities not intervals of roads and wasted more than hour on that. In Div1E firstly I didn't notice break. Then I noted break, but I considered version with that break within if :P. I didn't solve any of them ;).

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Waiting for Editorial ...............

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

The first idea for solving div2B was to generate first one hundred even palindroms ( yes, i know that it would get TLE ) , but when checking results i saw that the n-th palindrom is equal to n+reverse n , and solution which displays n+reversen is accepted , but i dont understand why .. why ?

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

    Start by noticing that palindromes with even number of digits are made of two equal parts. That is, if you cut them in half, both parts will be equal, but reversed.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2, Problem C (NP Hard) — I was not able to represent the graph as an adjacency matrix (boolean) due to memory constraints (Since 1 <= V, E <= 100,000). However, I see that the accepted solutions have used an array of vectors of the same size. I am confused if the test case uses a complete graph with V equal to max-limit, won't this exceed the 256M memory limit, even if a vector is used?

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

    m<= 10^5

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

    """two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the prize graph, respectively."""

»
8 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Div2 ==> Finished

Div1 ==> Pending system testing

:/

»
8 years ago, # |
  Vote: I like it +164 Vote: I do not like it

There is no systest because you are trying to construct test aganist O(qmα (m)) in D ?)

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

    Seems like they've failed to construct such test

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +70 Vote: I do not like it

    The time complexity is at most O(q(m + n2)) instead of O(qmα(m)). Because the distance of each vertex to the root of the disjoint-union set is at most O(n).

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

      Isn't O(q*n^2) with given constraints is ~ 10^9 instructions. I was under the impression that this will get TLE. Looks like that is not the case. How to predict whether a solution design will get TLE or not?

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

        You are right, and the constant factor is not 1 (more like 3 or 4). But TL is 6 seconds.

»
8 years ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

Before the system test: finally i will be a div1 user :D

After the system test: good bye div1 for ever ;_;

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Before systests : ~600.
After systest : 296.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

get rekt but i can get much of experience,thanks authors for nice problems TT

»
8 years ago, # |
Rev. 3   Vote: I like it -64 Vote: I do not like it

)

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

    Do you even meme bro?

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

      No, I am doing this first time :/
      All I want to have editorials to learn something new.

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

        Keep trying, eventually you will find the correct meme (or realize that it doesn't exist at all).

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

        Meme editorials (bro)?

»
8 years ago, # |
Rev. 8   Vote: I like it +26 Vote: I do not like it

TLE on 1B with cin and ios :: sync_with_stdio(false) :(
Why can't authors add a proper max-test in the pretests! :/

AC Code with scanf680 ms
AC Code with cin and ios :: sync_with_stdio(false) and cin.tie(0)982 ms
TLE Code with cin with ios :: sync_with_stdio(false) ≥ 1000 ms

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

    I got TLE due to cin too -> 18790984.

    Got AC with scanf in 342 ms -> 18809097

    It sucks to get tle just due to slower I/O :(

»
8 years ago, # |
  Vote: I like it +121 Vote: I do not like it

"Pari never tries to get ac with non-optimal solutions" — aren't constraints in D explicit invitation to code bruteforce ._.? Even tourist and jqdai0815 coded bruteforces -_-. Stupid problem. Try doing some statistics on how many AC to that problem are brutes (I guess >=80%).

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

    I'm curious why so many red guys are confident with bruteforce.

    They probably realized it is a Div 2 contest.

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

      There was two reasons why I complain:
      1. It is too easy for div1D
      2. Why n ≤ 1000, I don't use it.

      But the constraints are small enough for this solution to pass.

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

        These may happen for everyone who is preparing a contest for the first time.

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

    So that explains it... I found the actual solution (or something that has the same complexity at least) and it was some ugly Frankenstein union of a bunch of different algos, when I looked at the standings and thought "no way 70 people coded that :o"

»
8 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Fun facts:

using a O(n lg^2 n) or O(n sqrt n) approach gets TLE in B

using a O(qm alpha n) approach gets AC in D

As Swistakk says, I thought I registered for Div 2 after solving ABC.

Well, I should have gone back to office and let my mother participate this round for me.

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

    More fun facts, random_shuffle AC in div1C. 18807562

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

      random_shuffle has become quite an efficient problem solving tool recently!

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

    Another fun(?) fact: Around 70 div1 participants got TLE in B because of input speed.

    TFW you set a need-to-optimize problem's TL to 6s and a ****ing huge input one to 1s.

    If you ask me, yes I'm butthurt))

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

    qm log(n) works in D too

    I now understand that my solution is qm + qnlogn. Sorry for being misleading

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

    using a O(n lg^2 n) or O(n sqrt n) approach gets TLE in B

    n = 10^9 an O(n) solution passes and everybody loses their minds

    n = 10^6 an O(n sqrt n) solution doesn't pass and everybody loses their minds

    STFU people :3

    no offences, just kidding, i'm a noob

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Got wa on 25th test case for div2B.i just increased size of string to 200005 from 100005 and it got accepted.can anyone explain why?

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

    the answer can be as long as 200000 as given n will have 100000 digits... hope that helps.. :)

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

    maybe because your string b didn't have a proper '\0' null terminator in the right place. why still it gives correct output for increased array size I don't really know.

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Lol, so stupid idea in Div1D really passed... I wonder, what did authors expect to see when they set 6 (!!!) seconds TL.

»
8 years ago, # |
  Vote: I like it -21 Vote: I do not like it

When you see jqdai0815 solved Div2 E in a period of 4 mins

»
8 years ago, # |
  Vote: I like it +22 Vote: I do not like it

The advanced algorithmic technique to get AC in div1D

18808466

18810544

»
8 years ago, # |
Rev. 2   Vote: I like it +42 Vote: I do not like it

tourist is't the first !

»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I am really surprised, my solution in B div1 is nlogn

TLE using cin even with ios::sync_with_stdio(0) and cin.tie(0) and cout.tie(0)

Used scanf and printf it got AC

TLE solution: http://mirror.codeforces.com/contest/687/submission/18804476

AC solution: http://mirror.codeforces.com/contest/687/submission/18810350

I never saw this happen on a site like Codeforces, I really can't believe it happened and why time limit is too strict?!!!

I wish i see good explanation to what i saw today and why the author made the time limit so small !!

If he made time limit 1.5 seconds as an example only intended solutions will pass too.

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

    Your solution is slower than the intended one. Cin/cout is slower than printf/scanf.

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

      I think gcd is log or more

      so total is nlogn, only my constant factor is bigger, i know, but the same complexity, if time limit is too tight it means other languages will not get AC

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

    sieve() takes a lot of time. My method just takes gcd() and does not take sieve() method, with " ios::sync_with_stdio(0) and cin.tie(0) and cout.tie(0)", and faster than your AC solution more than 100ms.

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

    My Python solution was judged TLE on pretests, then submitted a C++ version and got AC =) I tought there were multiplicative factors on execution time to equalize results...

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

      I think that if they make some updates like special Time Limit for each lang that's will be better

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

        Yeah, but it's a huge amount of work =P

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Still tourist is first

»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

touristPetr = 1 ! The game is still on :)

»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Some time limits were definitely problematic :/ Enough people mentioned Div1B (input), but my problem was with Div1C — my O(N*K^2) solution got TLE, which I fixed easily with some microoptimizations but I didn't expect them to be needed... Was there some good reason for this time limit (e.g. a worse solution that might've passed otherwise)? If not, it's frustrating that constant factor optimizations made such a big difference in this contest (also in Div1D apparently).

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    Well after enough optimizations my O(n^4) for Div2E/Div1C got AC'd

    18812616

    Maybe they are justified about their strict time limits after all...

»
8 years ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

On Div2D/Div1B, many C++ codes which get TLE31 get AC by just adding one line of code at the beginning of main:

ios_base::sync_with_stdio(false);

example:

http://mirror.codeforces.com/contest/688/submission/18801250 vs http://mirror.codeforces.com/contest/688/submission/18811446

Time limit should not have been only 1 second.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solutions are showinh the verdict skipped what do i do are my submissions wrong or what??

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

    If more than one submission for a problem pass the pretests, the most recent one will be considered and the rest will be skipped

»
8 years ago, # |
  Vote: I like it +50 Vote: I do not like it

I think it is intetesting that tourist-Petr is 1. But I don't deem it interesting that my rating is now 2899!:(

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

    Matches your username ... I think that's pretty interesting

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

      lol

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

        The last chance to be a lgm before retiring? lol.

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

          Possibly. It should be informed that retiring means the end of OI contests(for high school students) in China. If I fail in the contest in july(NOI 2016), I will retire and this is my last chance. And I should mention that programming contests in China are easy to fail.

          But whatever it is I narrowly missed this chance. :(

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any body tell why this submission 18804553 is WA ? I saw some AC solutions and its the same idea .

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

    I think you are not handling multiple connected components correctly. For example, on the case "4 2 1 2 3 4" your code does not put vertices 3 or 4 in either group.

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

      Thanks, but as it said in the statement we can keep vertex for ourself , so i can keep vertex 3 and 4 , and give vertex 1 to Pari and give vertex 2 to Arya , right ?

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

        You can keep a vertex to yourself . Not an entire component -_- . See the sample input , there are 4 nodes but node 4 isn't in the output !

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am thankful that my solution got hacked. Or else would have gone back to Div 2 today :)

»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Uh ... So there is UPD3 but no UPD2 ...

I think that's why we didn't see the score distributions, they skipped it (?) ... ._.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish that next begin time will be early

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Help needed!!

I tried to solve the problem DIV2 C in this way . Consider a component of graph if there is an odd cycle leave that component. Otherwise do a 2 Coloring of that component . Suppose two colors are red and green. Then for every component red vertices belong to one set and green vertices to other set. If we can find no component without odd cycle we print "-1".

But I am getting WA on 30th test case. Can somebody help me? Here is my submission :- http://mirror.codeforces.com/contest/688/submission/18815978

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

    A graph G will have two disjoint vertex covers if, and only if, it is bipartite.

    G is bipartite two disjoint vertex covers:

    Choose partition A to be the first vertex cover. Since there are no edges (u, v) such that , one of the end points, say u, is in A and the other v is in partition B. Therefore, for every edge we have that it is covered by both a vertex of A and another by B, and each partition is a disjoint vertex cover.

    Two disjoint vertex covers G is bipartite:

    Suppose G is not bipartite, then, for any pair of partitions A, B, including our vertex covers, there exists an interior edge (u, v) in at least one of the partitions, say A. That is, we have an edge untouched by B. Which is an absurd, since both A and B are vertex covers.

    I think that should be it (didn't find any hole in the second step of the proof). With this we have that the problem becomes a matter of determining if G is bipartite.

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Where is editorial?

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

No rating change for me! Now that's called consistency. :p

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

waiting for the editorial ....

»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

where is the editorial?. when it will be published?

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

In div2 B problem, constrants were n<10^100000. If constrants would be n<10^5, then it would be little difficult for me to think over that.

»
8 years ago, # |
  Vote: I like it -13 Vote: I do not like it

So Petr chose to sit still and defeat tourist without coding himself. Wow, he is about to win!

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How I use Chinese Reminder theorem to Problem number D?