Блог пользователя M.Mahdi

Автор M.Mahdi, 8 лет назад, По-английски

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!

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

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

Very good time ! Thanks Mr.Shokri

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

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

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

    You should also hope both JIBANCANYANG and jqdai0815 will participate.

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

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

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

        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 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится

        R E K T

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

        Lucky jqdai0815... #:-s

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

      be glad. jqdai0815 will participate

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

    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 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Come on, now it becomes even more thrilling!

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

That is a good time

Good luck guys

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

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 лет назад, # ^ |
      Проголосовать: нравится -29 Проголосовать: не нравится

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

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

      No, she is a Korean I believe.

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

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

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

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

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

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

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

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

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

                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 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится

                Why do you not participate in contests?

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

            Wait how can you tell someone gender by typing style.

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

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

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

      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 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

But it is really quite too late for me..

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

excited for the round

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

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

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

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

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

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

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

      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 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

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

pari?!

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

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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

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

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

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

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

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

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

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

Pari must be a fake account of Arya.

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

Plus for Pari and Arya!)

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

Хотел бы стать зелёным после этого контеста

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

In fine :)

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

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

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

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

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

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

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

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

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

How many problems and score distributions?

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

Arya be like...

Today she will slay us with the statements!

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

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

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

[Temporary Deleted]

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

Good Fight Between tourist & jqdai0815 :)

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

How to solve D?

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

    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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How to prove such solution?

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

        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 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

        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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      "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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    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 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +16 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

Where's the editorial??

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

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

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

    How to solve C easily?

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

      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 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Will solution with bool array get TLE?

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

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

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

      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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I got TLE in TC 19, div2E...

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

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 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

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

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

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

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

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

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

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

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 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

        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 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

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

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

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

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

    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 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

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

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

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

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

Hints for Div1 D?

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

    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 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Terrible grammar. Someone send the statements to jacksfilm for YGS

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

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 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Here

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

I am quite surprised by JoeyWheeler's performance.

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

    Thanks mate >_>

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

    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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

        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 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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

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

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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

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

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    m<= 10^5

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

    """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 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Div2 ==> Finished

Div1 ==> Pending system testing

:/

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

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

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

    Seems like they've failed to construct such test

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

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

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

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

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

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

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

Before systests : ~600.
After systest : 296.

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

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

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

)

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

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 лет назад, # |
  Проголосовать: нравится +121 Проголосовать: не нравится

"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 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

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

    They probably realized it is a Div 2 contest.

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

      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 лет назад, # ^ |
          Проголосовать: нравится -13 Проголосовать: не нравится

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

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

    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 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    More fun facts, random_shuffle AC in div1C. 18807562

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

    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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    qm log(n) works in D too

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

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

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    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 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

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

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

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

The advanced algorithmic technique to get AC in div1D

18808466

18810544

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

tourist is't the first !

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

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://codeforces.net/contest/687/submission/18804476

AC solution: http://codeforces.net/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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Still tourist is first

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

touristPetr = 1 ! The game is still on :)

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

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 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

    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 лет назад, # |
Rev. 8   Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.net/contest/688/submission/18801250 vs http://codeforces.net/contest/688/submission/18811446

Time limit should not have been only 1 second.

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

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

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

    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 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

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

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

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

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

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

I wish that next begin time will be early

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

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://codeforces.net/contest/688/submission/18815978

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

    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 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Where is editorial?

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

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

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

waiting for the editorial ....

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

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

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

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 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

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

В задаче 688D - Игра с остатками я разобрал, что нужно проверить делимость LCM(c_all) на К и написал следующий код, который получил АС.

i64 d=1;
forn(i,n)
{
    scanf("%d",&t);
    d=((d*t)/__gcd(d,1ll*t))%k;
}

Это слабые тесты, или в данной задаче я действительно могу так брать остаток? Не могу доказать сам.

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

    Кажется, это правда нормально.

    Нужно просто понять, что для каждого простого d будет иметь разумную степень вхождения

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

How I use Chinese Reminder theorem to Problem number D?