M.Mahdi's blog

Codeforces Round #360
By M.Mahdi, 10 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. EvenImage
  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

Comments Comments (283)
| Write comment?
»
10 years ago, hide # |
 
Vote: I like it +70 Vote: I do not like it

Very good time ! Thanks Mr.Shokri

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

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

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

    You should also hope both JIBANCANYANG and EvenImage will participate.

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

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

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        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.

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

        R E K T

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

        Lucky EvenImage... #:-s

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

      be glad. EvenImage will participate

      → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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 :)

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

    Come on, now it becomes even more thrilling!

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

That is a good time

Good luck guys

→ Reply
»
10 years ago, hide # |
 
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. (๑>ᴗ<๑)

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

But it is really quite too late for me..

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

excited for the round

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

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

→ Reply
»
10 years ago, hide # |
 
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!

→ Reply
»
10 years ago, hide # |
 
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 =))

→ Reply
»
10 years ago, hide # |
 
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 :>

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

pari?!

→ Reply
»
10 years ago, hide # |
 
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 .

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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.

    → Reply
»
10 years ago, hide # |
← 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?

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

→ Reply
»
10 years ago, hide # |
 
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

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

Pari must be a fake account of Arya.

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

Plus for Pari and Arya!)

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

In fine :)

→ Reply
»
10 years ago, hide # |
 
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 .

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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

    → Reply
»
10 years ago, hide # |
 
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.

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

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

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

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

→ Reply
»
10 years ago, hide # |
← 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.

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

How many problems and score distributions?

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

Arya be like...

Today she will slay us with the statements!

→ Reply
»
10 years ago, hide # |
 
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

→ Reply
»
10 years ago, hide # |
← Rev. 2  
Vote: I like it -16 Vote: I do not like it

[Temporary Deleted]

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

Good Fight Between tourist & EvenImage :)

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

How to solve D?

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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

    → Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

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

      How to prove such solution?

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        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)

        → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
        ← 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

        → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
        ← 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
        → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        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.

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

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

    → Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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 :'(

    → Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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.

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

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

→ Reply
»
10 years ago, hide # |
 
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... :(

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

Where's the editorial??

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

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

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

    How to solve C easily?

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← 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.

      → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      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);
    }
  }
}
      → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
      ← 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)

      → Reply
»
10 years ago, hide # |
 
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?

→ Reply
»
10 years ago, hide # |
 
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!

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

I got TLE in TC 19, div2E...

→ Reply
»
10 years ago, hide # |
← 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
→ Reply
»
10 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
10 years ago, hide # |
 
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!

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

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

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

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

→ Reply
»
10 years ago, hide # |
 
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.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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 .

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

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

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, hide # ^ |
           
          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 :)

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, hide # ^ |
           
          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)

          → Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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

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

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

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

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

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

Hints for Div1 D?

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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 .

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

Terrible grammar. Someone send the statements to jacksfilm for YGS

→ Reply
»
10 years ago, hide # |
 
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!

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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?

    → Reply
»
10 years ago, hide # |
← 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)

→ Reply
»
10 years ago, hide # |
← 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

→ Reply
»
10 years ago, hide # |
 
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 -_-

→ Reply
»
10 years ago, hide # |
 
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

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

I am quite surprised by JoeyWheeler's performance.

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

    Thanks mate >_>

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

    → Reply
»
10 years ago, hide # |
 
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?

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
        ← 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

        → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

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

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

→ Reply
»
10 years ago, hide # |
 
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 ;).

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

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

→ Reply
»
10 years ago, hide # |
← 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 ?

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

    → Reply
»
10 years ago, hide # |
 
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?

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

    m<= 10^5

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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."""

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

Div2 ==> Finished

Div1 ==> Pending system testing

:/

→ Reply
»
10 years ago, hide # |
 
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 ?)

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

    Seems like they've failed to construct such test

    → Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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).

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      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?

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        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.

        → Reply
»
10 years ago, hide # |
← 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 ;_;

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

Before systests : ~600.
After systest : 296.

→ Reply
»
10 years ago, hide # |
 
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

→ Reply
»
10 years ago, hide # |
← Rev. 3  
Vote: I like it -64 Vote: I do not like it

)

→ Reply
»
10 years ago, hide # |
← 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 scanf — 680 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

→ Reply
»
10 years ago, hide # |
 
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 EvenImage coded bruteforces -_-. Stupid problem. Try doing some statistics on how many AC to that problem are brutes (I guess >=80%).

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      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.

      → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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"

    → Reply
»
10 years ago, hide # |
 
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.

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

    More fun facts, random_shuffle AC in div1C. 18807562

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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))

    → Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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

    → Reply
»
10 years ago, hide # |
 
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?

→ Reply
»
10 years ago, hide # |
 
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.

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

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

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

The advanced algorithmic technique to get AC in div1D

18808466

18810544

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

tourist is't the first !

→ Reply
»
10 years ago, hide # |
 
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.

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      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

      → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

    → Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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...

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

Still tourist is first

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

tourist — Petr = 1 ! The game is still on :)

→ Reply
»
10 years ago, hide # |
 
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).

→ Reply
»
10 years ago, hide # |
← 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.

→ Reply
»
10 years ago, hide # |
 
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??

→ Reply
  • »
    »
    10 years ago, hide # ^ |
    ← 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

    → Reply
»
10 years ago, hide # |
 
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!:(

→ Reply
»
10 years ago, hide # |
 
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 .

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

    → Reply
    • »
      »
      »
      10 years ago, hide # ^ |
       
      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 ?

      → Reply
      • »
        »
        »
        »
        10 years ago, hide # ^ |
         
        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 !

        → Reply
»
10 years ago, hide # |
 
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 :)

→ Reply
»
10 years ago, hide # |
 
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 (?) ... ._.

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

I wish that next begin time will be early

→ Reply
»
10 years ago, hide # |
 
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

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    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.

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

Where is editorial?

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

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

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

waiting for the editorial ....

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

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

→ Reply
»
10 years ago, hide # |
 
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.

→ Reply
»
10 years ago, hide # |
 
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!

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

How I use Chinese Reminder theorem to Problem number D?

→ Reply