mahmoudbadawy's blog

By mahmoudbadawy, history, 6 months ago, In English,

Hello Codeforces!

I'm glad to announce that on Feb/07/2017 17:05 UTC Codeforces Round #396 for the second division will take place. As usual, First division participants can take part out of competition.

This round was prepared by me and mohammedehab2002.

I'd like to thank moaz123 for helping us prepare the round, zoooma13 for testing some problems, KAN for helping us in contest preparation and for translating the statements into Russian and MikeMirzayanov for the great Codeforces and Polygon platforms.

You will be given 5 problems and 2 hours to solve them.

The scoring distribution will be announced later.

UPD 500-1000-1500-2000-2500

UPD editorial is ready

UPD Congratulations to the winners!

Div1+Div2:

  1. Verstand

  2. sd0061

  3. rajat1603

  4. gritukan

  5. ulna

Div2:

  1. Verstand

  2. zhfs_ga_pitona

  3. zelta

  4. AomeII

  5. bciobanu

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

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

A true Codeforces fan can not scroll down without upvoting this comment .

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

MikeMirzayanov mahmoudbadawy There is a bug with registration. Div1 users cant register unofficially.

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

    Sorry, please try again now.

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

Hope to be a good round. Good luck to all participants.

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

    you don't need to say "good luck" buddy. coz good luck is not related to contest anywhere

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

      coz luck is not rated)

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

      I don't know man... sometimes when the site doesn't lag at all I feel pretty lucky...

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

The email says the round will have 6 problems, but the post says 5. Which one is it?

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

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

is this the 1st Arabic official round on CF ??

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

Is it rated??

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

    There's always that one guy who asks this question.

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

mohammedehab2002 shares a name with an Egyptian weightlifting superstar. Guessing not the same guy but would be cool if so.

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

short blog :) I love it

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

Copy Codeforces testcases by clicking on them :O

An extension for chrome only Installation: Download from https://drive.google.com/file/d/0B4HQVLPL4OXRUHJNa0dnQkNYNzA/view

you can see GIF https://media.giphy.com/media/26xBNH5TzjX0z90R2/giphy.gif

Go to "chrome://extensions/" Drag and drop the file into the page

Good Luck And Have Fun <3

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

Here's to clever yet easy problems! Hoping to become candidate master finally...

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

Fast and accurate wins the race.

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

Rating != Knowledge
Even newbies can think of a beautiful problem, which can be challenging for masters!

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

    @VoR_ZaKon : All I wanted to say was that rating doesn't defines one's thinking ability.
    PS — He deleted his comment. His comment was — "Ok then I am better than tourist".

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

      He is banned (his comments and posts deleted automaticly). LOL :D

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

Prepare by pupil?

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

I have short.

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

    I think there were a lot of replys 5 minutes ago..

    UPD: I think admin deleted them.

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

the new contetst with specialist builder. this contest will be nice

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

New authors often surprise CodeForces community (in good way)... Trust on interesting contest, good luck to all!)

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

New contest, new opportunities to learn and possibly get better. Thank you CodeForces

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

What a stupid contest

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

    why do you think so?

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

      problem D and E are old problems

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

        how did you solve E ?

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

        Where did you see problem E before? I have seen it in a way that you are given weights for the edges but I have never seen it with weights for the vertices. And the solution for the "edge" version is different than the one for this problem.

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

          Solve the problem considering the weight on the edges and the starting distance is a[centroid]. Now you need to invert the bits that appear on a[centroid] because if the path goes throught it, you will count it twice. Do that and then the rest is identical.

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

          Hi can you mention the link of the problem which given weights are for the edges ? I'd like to practice on that one too. Thanks

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

already got these hackers

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

belive it or not, this was the worst contest I have ever seen

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

    Maybe your worst result ever ;)

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

    E was a genuinely interesting problem IMHO. ABD were around the average, C was way too tedious. This may not be the best contest, but there is no way I could call this the worst contest ever.

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

      C wasn't tedious(if what I did was correct). The second part of C was a simple for loop, and the first and third parts were n^2 DP.

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

        I did the same as you, but honestly I found that writing essentially three solutions was quite annoying. Maybe tedious is an overstatement.

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

I'll just leave this here...

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

Hi! I'm working on rating calculation tool. It's close to be ready! You could find this contest's rating prediction here. I hope chrome extension would be ready till next contest.

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

    Awesome, I love it :)

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

    Good job!

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

    Nice. But I think I will just use the page instead of the extension. Thank you for this.

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

    For me, it doesn't seem to be working? It says I got rank as 291 when I got 99th place, and predicts rating decrease even though seed is 620?

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

      It's because server isn't so powerful to process changes just in time. Your rank and rating will change soon:)

       It seems you are going well!

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

    By checking a few random contestants, I found that the predicted rating changes and real rating changes are always differ by 5.

    It would be awesome if this difference could be fixed as well :D Maybe it's something related to the unrated contestants? (Not sure)

    Can't wait to see the accuracy of your updated hardwork!

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

      Thank you! I will try to fix this)

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

In B, we can write O(n^2) because maximum value of n for which answer is NO is ~90 ?

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

    You can sort and itertate through in B.

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

    I tried to find a hack test case for O(n ^ 3) and O(n ^ 2) solutions.. :D

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

      For O(n^3) use the first let's say 10 fibonacci numbers and then their multiples For example 100000 1 1 2 3 5 8 13 21 34 55 110 165 220 275 330 385 etc

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

        Hm. I think this test case is wrong because "220 275 330" are valid sides

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

          The guy that I hacked checked if (v[ 1 ],v[ 2 ],v[ 3 ]) from a triangle, then(v[ 1 ],v[ 2 ],v[ 4 ])... then( v[ 2 ],v[ 3 ],v[ 4 ]) and so on, so on this test it gets TLE

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

    Have you proven that the maximum value is 90? Cause I was thinking for half an hour for a test that O(n^2) doesn't work for it but I couldn't come up with anything.

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

      The smallest test case of answer "NO" is the fibonacci sequence. So if N >= 45, it is always possible to make a triangle.

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

      Let's make sorted array with the answer "NO"

      1 1 2 3 5 ...

      Fibonacci numbers!

      ai <= 1e9, so n with an answer "NO" has to be small

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

      Yep, it is easy to prove that maximum value is less than 100.

      To build a correct triangle you need 3 values , lets say its a<=b<=c

      If a+b>c triangle can be build, then if we want to create maximum sequence of numbers that cant result in triangle we have to create something like fibbonacci sequence. t[i]=t[i-1]+t[i-2]

      You can look up at fibbonacci and see that 70th or 80th(i dont know exactly) is already bigger than 10^9.

      Then, if n>100 pritf yes, otherwise use O(n^3) algorithm

»
6 months ago, # |
Rev. 6   Vote: I like it +5 Vote: I do not like it

How to solve problem D? I could think of an approach using 2 dsu's. but did'nt code

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

    I used 1 dsu and an additional array of antonyms (if i-th and j-th sets are antonymical, ant[i]=j and ant[j] = i).

    You just have to update the sets_merge operation to handle antonyms: if you merge a and b, ant[a] and ant[b] should also be merged.

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

      how update and handle sets in this case?

      1  aba aca
      1  ada aea
      1  afa aga
      2  afa aea
      
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        you have to think this way:

        2 strings are synonims.you do a union operation on them.but what happends if one of them or both have an antonym?

        if they both have one,you unite their antonyms.if only one has,you make sure that the root knows who's that antonym. if they are antonyms you update the antonyms array.but,there are again subcases

        let's say the words are a and b if a had an antonym,then b and ant[a] are synonyms,so you unite them if b had an antonym,then a and ant[b] are synonims. again,be carefull that the root always knows who is his antonym

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

    Yes it can be solved using dsu, you just need to color the verticles (the words) and find the answer for each query

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

    You can use 2 nodes for a single node. The new graph will have 2*N nodes. For synonyms, add edge between (u,v) and (u', v'). For antonyms, add edge between (u, v') and (v, u'). Use DSU.

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

Can someone explain C? I thought it was DP but I couldn't figure out how to put it together.

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

    lets say string is from i to j then, for(k=i;k<=j;k++) { if(i,k is a valid substring ) dp[i][j]+=(dp[k+1][j]); }

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

    You are right, it was a DP indeed :)

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

    to calculate number of ways to split the substring(l,r) you have to choose the leftmost splitter i starting from l until it violates the conditions mentioned or reach r. after choosing leftmost splitter i you have to find number of ways to split substring (i+1,r) and add it with the result

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

    Yes, it's DP. I used two functions: 1) Number of different partitions of prefix with length i when rightmost word has length j 2) Minimum number of words in partitions of prefix with length i when rightmost word has length j

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

    Let dp[i] denote the number of ways to split the substring[0,i) in a valid manner. Then the answer is obviously dp[n]. We have base case dp[0] = 1. Then dp[i] += dp[j]%MOD if substring(j,i] is valid for 0 <= j < i. You can think of it as dp-ing on the possible spots to cut the string. Question 2 and 3 can be answered by updating along the way.

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

I loved D. Thanks for a great contest.

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

Lost a lot of points on C, because I thought there should be at least one cut :/

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

with 10 more minutes I would have finished debugging D and solved all problems. :(
contest is much easier than usual

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

    Can you tell me the idea behind E, please?

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

      I used centroid decomposition to solve E

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

        I suppose it shouldn't fit to TL (because it O(N*logN*logMaxA))

        UPD. Yes, you got TL14. The correct solution (dp on tree for each bit) doesn't use centroid decomposition and has O(N*logMaxA) complexity.

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

          Yeah you are right i got TLE :(

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

          Hmm... I solved it using centroid decomposition and it passed just fine.

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

      Perform DP for each bit counting the ways with xor = 1 and xor = 0.

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

      Root the tree at an arbitrary vertex. Let's calculate the answer for all bits separately.

      For each vertex u calculate the number of pairs (u, v), where v is some vertex in the subtree of u so that the path weight for that bit is 1, and also so that the path weight is 0. This can be done through dynamic programming.

      Handling paths (u, w) that pass through v (so that v != u and v != w) can be done through iterating through the children of v.

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

        I could not understand your approach. Can you elaborate a little please.

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

      For each bit i, assign value node u = bit i-th of a[u]. The problem become: Count number of path in tree that have odd number of 1. Then we multify it with 2^i.

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

    Although I agree with u based on D and E, C was better than usual. Just check out round #394, C was a cakewalk.

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

Awesome problemset! Devoted my whole time in solving E but couldn't. If there would have been integers attached with edges instead of nodes then it was quite easily solvable but this little twist made the contest complete fun for me. Thanks !

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

Can someone give an idea for D?

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

    While adding pairs, you can use disjoint-set union to see if the words are already associated with the same meaning (be it antonymous or synonymous). Ignore those edges when adding them. Run DFS for each component, coloring its synonyms white and antonyms black. Then you can answer the queries (of both kind)

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

Problem D is here Link However without the part of answering some queries on relations.

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

    And here is E :P

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

      I'm also pretty sure B is somewhere online

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

      It is different from E which has weights on vertices, not on edges.

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

        The solution would still be the same.

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

          Can you please explain how we can derive solution for weight on nodes. I had a solution with dfs and components counting if there were weights on edges. How to convert that in this problem ?

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

            Just consider the given graph is a rooted tree, and the weight of node i, a[i], can be transformed into the weight of the edge between i and the parent of i.

            While calculation the answer with DFS, just don't forget to special handle the current node. We should also add the weight of the current node cur, a[cur] to the cost of the paths passing through node cur.

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

            You have to deal with every bit alone. Dfs from the root and calculate the value of the bit i on the path from the root to each node.

            Now you only need the number of ones and the number of zeros in each subtree. You can combine the answers from different subtrees as for each two nodes the path length will be pathfromroot[x] ^ pathfromroot[y] ^ val[lca]

            There is only 2 outputs for each bit depending on the value of val[lca] so it can be calculated easily

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

Just a couple of minutes more and I would've solved D. It's nice to spend the entire contest on C and realize that D is solvable when you have only 15 mins left... Thanks for the contest, anyway.

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

Can i see some hack cases for 'A' that you people used. I tried hacking, but failed. Thanks

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

For problem B, what should be the hack case for O(n^3) solution which didn't use sorting?

Update: This is a hack case for O(n^3): 100000 1 2 3 4 5 6 7 8 9 .......... 100000

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

    100000 1 1 2 3 5 8 13 21 34 55 110 165 220 275 330 385 etc

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

      In this way, the value won't fit in integer and will be > 10^9, so I think this won't work.

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

        How would the values exceed 109?

        The elements excluding the first nine are all multiples of 55, and so the last element in this list would be 55 × (105 - 9) = 5499505 < 109

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

          The 44'th number of this sequence ( i.e. 1 1 2 3 5 8 13 ......) is 1134903170 which is > 10^9

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

            Dude, read it until the end.

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

            Didn't you notice the sequence Flavius mentioned is not simply Fibonacci sequence? It is not a Fibonacci sequence starting from 55. So the 44th element of that sequence is not exceeding 109, it is just 55 × (44 - 9) = 1925.

            I hope you can read carefully next time :)

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

      220 275 330 form a Valid Triangle.

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

        But the simplest O(N3) nested loop will still iterate long time through the first few elements until it finds the first valid triangle.

        FOR i FROM 1 TO n
          FOR j FROM (i + 1) TO n
            FOR k FROM (j + 1) TO n
              Check(A[i], A[j], A[k])
        

        In cases that the logic is similar to the above code, i iterates from 1 to 10 but still can't find any solution. Each iteration of i takes O(N2) as it will still check for all possible j and k that i < j < k. In other words, the code will TLE before finding a valid triangle.

        BTW, the first valid triangle should be 110, 165 and 220

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

      The sequence overflows after 43 terms. For O(N^3) solutions, the hack used can be any sequence with 100000 terms and the first term as 1: 100000 1 2 3 4 5 6 ...

      since for i=1, the loop runs O(n^2) times and we get NO for all cases, this will give TLE.

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

        Is it really hard to notice that the sequence is not just simply Fibonacci sequence?

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

    There isn't, with more than 45 elements it's always possible and O(n^3) obviously works for n = 45 http://codeforces.com/blog/entry/50280?#comment-342293

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

      O(n^3) solution got TLE on test case 33

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

        Test 33 is abcd abc, so I'm guessing there was a bugged while instead of 3 fors

        edit: disregard this comment, wrong problem

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

          You are talking about problem A, while were talking about problem B.

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

            Sorry, my mistake. Problem B's case 33 are just numbers from 1 to 10^5, so by checking in O(n^3) the first 45 numbers the solution (2, 3, 4) will show up

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    5
    2 2 2 100 1000
    

    and

    6
    1 10 100 10 1 1
    

    correct answers: YES | YES

    Edit: these are tests with which I generally hacked some B codes. Misread your comment a bit... O(n^3) might not be hackable, since for n approx. >100 the code should always say "YES". See discussion few posts up about Fibonacci Sequence.

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

      O(n^3) solution will also give AC output for your inputs.

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

      But have you seen that in system test, O(n^3) solution got TLE on test case 33 ?

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

        I tried to hack Atai solution for n=10000 with input as 1,2,3,4..........10000 but it showed unsuccessful.. But the same sol... is showing tle for test case 33 system test... how is my hack solution passing and system test failing... failed system soln http://codeforces.com/contest/766/submission/24500965 passed hack soln http://codeforces.com/contest/766/hacks/296935/test

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

          You unfortunately forgot to add an extra zero. The max input size is 10^5, where your hack is only 10^4.

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

            it was n^3 soln if it failed at 100000 it will also fail at 10000

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

              The reason is he selects 1 as his first side length, and then selects 2, and then iterates from 3-10^4 to find a valid length but fails. He then switches his second leg to be 3, and iterates third leg from 4-10^4. You see this will continue until he selects 2 as his first leg.Here, he will immediately find a triangle (2,3,4).

              This process is n^2 for this test case (because of the early break case). If you would have used 10^5, he would have done (10^5)^2, which is 10^10 and then he would have TLE'd. Sorry, bad luck.

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

    100000 1 1000 10004 10006 10008 10010 10012 10014 10016 10018 10020 10022...

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

How can this user, r_clover, solve both problem B and D within a minute?

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

    Wrote code for B, forgot submitting, then wrote code for D, submitted D, realized he had forgotten submitting B and submitted B.

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

    Exactly ! and the funny thing is that took him 4 mins to solve A and 7 mins for both A and D ...

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

    Coding styles are different too... He was not alone :)...

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

    His results/submissions have disappeared

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

    In the same way as you did here and got disqualified :

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

Problems are good i think...i hope there would be a chance today...

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

So, Codeforces started copying problem from UVa :\ :\ :P

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

That moment when you failed both C and E only because of wrong answer on n = 1 case...

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

Did anyone else failed system test on test 22 on problem C.

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

Thanks for this good contest .

I really like these problems.

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

Why codeforces div2 contests are becoming easy?

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

    Maybe you're getting better?

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

      E div2 in 'div1+div2 rounds', are harder than E div2 in 'only div2 rounds'...

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

        But it shouldn't be!

        div2 only contests should be interesting for div1 users too.

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

    What's the problem with it?

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

      Solving hard problems makes you strong.

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

        AB should be easy because before solving harder problems (CDE) we have to solve easier problems first.

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

    That's true for a d1,but it isn't true for d2,so i don't think it is a big problem since the round is destinated only for d2.

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

guys this guy i tried to hack his code for A

by test case

abc xyz

but it's weird that it was unsuccessful attempt ?

his code :

s=input() t=input() if s in t: if len(s)==len(t): print(-1) else: print (abs(len(s)-len(t))) elif t in s: if len(s)==len(t): print(-1) else: print (abs(len(s)-len(t)))
else: if len(s) > len(t): print(len(s)) else: print(len(t))

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

    The code works perfectly for your case. It is because your case belongs to the third condition (the else: line)

    As if s in t: in Python means checking if the string s is a substring of t, while in your case, abc is not a substring of xyz, so s in t returns FALSE in your case. And same for the t in s condition as well.

    As a result, the code goes here:

        if len(s) > len(t): print(len(s))
        else:               print(len(t))
    

    And thus, print 3 as the output, which is the correct answer.

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

Interesting thing about problem B is that stupid solution which uses random works fine and passes all tests. Solution: 24513380

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

    It's not so stupid. If n > 50 then you can always find such triangle so chance of finding one randomly is high. In other hand when n <= 50, randoming is pretty much like using n^3 brute force, so as I said it's not a dumb solution.

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

Div2 C, rip to all of those who got WA on test 36

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

Will be editorial?

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

I implemented B in a little bit bad way, I used 3 for loops but the third one is redundant then also time complexity of my solution is O(n^2). After locking and seeing other solutions I thought that my solution can be hacked by giving tle but it indeed passed the system testing. But by intuition it was clear that finding such a test case was difficult, so I wanted to know whether it is possible to hack my solution with certain sequence or not ? and how did it passed the system test . http://codeforces.com/contest/766/submission/24497421

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

I got time run exception for solution of second qn written in python. after rewriting it in C++; It I passed it. What does it mean?

n = input()
C= map(int,raw_input().split())
C.sort()
flag = False
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if C[i]+C[j]>C[k] and C[i]+C[k]>C[j] and C[k]+C[j]>C[i]:
        flag = True
        break
print "YES" if flag else "NO" 
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good round. Where I can find a tutorial of these tasks for training?

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

I know I'm a little late, I had to work yesterday :(

Problem D is exactly this problem (with different input/output format obviously)

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1099

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

I have calculated the complexity the code to be NlogN*maxl +MlogN*maxl+2*Mlog+N*logN+Q similar to the question authors (N+M+Q)logN*maxL, but getting TLE on test 13 please somebody can review my code. I know I havn't run the dfs from root node but this should pass too. please help!

http://ideone.com/EhwB7S

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    FIRST TRAVERSE WHOLE ARRAY ANF FIND SUM

    IF(SUM IS ODD) RETURN -1;

    THEN USE DP FOR SIZE=N/2 AND TOTAL=SUM

    DP[SIZE][TOTAL]=DP[SIZE-1][TOTAL] || ( DP[SIZE-1][TOTAL-Arr[i]] for all i )

    RETURN DP[N/2][SUM];

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

Hey guys. How to solve E? I can't get this prob.

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

Hey guys. How to solve this problem https://www.e-olymp.com/ru/contests/7949/problems/66445? I can't get this prob.