mahmoudbadawy's blog

Codeforces Round #396 (Div. 2)
By mahmoudbadawy, history, 8 years 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. vintage_Vlad_Makeev

  5. Bedge

Div2:

  1. Verstand

  2. zhfs_ga_pitona

  3. zelta

  4. AomeII

  5. bciobanu

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

Comments Comments (175)
| Write comment?
»
8 years 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 .

→ Reply
»
8 years 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.

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

    Sorry, please try again now.

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

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

→ Reply
»
8 years 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?

→ Reply
»
8 years ago, # |
  Vote: I like it -20 Vote: I do not like it

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

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

→ Reply
»
8 years 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.

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

short blog :) I love it

→ Reply
»
8 years 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...

→ Reply
»
8 years 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!

→ Reply
  • »
    »
    8 years 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".

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

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

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

Prepare by pupil?

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

I have short.

→ Reply
  • »
    »
    8 years 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.

    → Reply
»
8 years 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!)

→ Reply
»
8 years 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

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

What a stupid contest

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

    why do you think so?

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

      problem D and E are old problems

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

        how did you solve E ?

        → Reply
      • »
        »
        »
        »
        8 years 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.

        → Reply
        • »
          »
          »
          »
          »
          8 years 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.

          → Reply
        • »
          »
          »
          »
          »
          8 years 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

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

already got these hackers

→ Reply
»
8 years 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

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

    Maybe your worst result ever ;)

    → Reply
  • »
    »
    8 years 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.

    → Reply
    • »
      »
      »
      8 years 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.

      → Reply
      • »
        »
        »
        »
        8 years 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.

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

I'll just leave this here...

→ Reply
»
8 years 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.

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

    Awesome, I love it :)

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

    Good job!

    → Reply
  • »
    »
    8 years 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.

    → Reply
  • »
    »
    8 years 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?

    → Reply
    • »
      »
      »
      8 years 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!

      → Reply
  • »
    »
    8 years 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!

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

      Thank you! I will try to fix this)

      → Reply
»
8 years 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 ?

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

    You can sort and itertate through in B.

    → Reply
  • »
    »
    8 years 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

    → Reply
    • »
      »
      »
      8 years 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

      → Reply
      • »
        »
        »
        »
        8 years 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

        → Reply
        • »
          »
          »
          »
          »
          8 years 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

          → Reply
  • »
    »
    8 years 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.

    → Reply
    • »
      »
      »
      8 years 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.

      → Reply
    • »
      »
      »
      8 years 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

      → Reply
    • »
      »
      »
      8 years 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

      → Reply
»
8 years 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

→ Reply
  • »
    »
    8 years 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.

    → Reply
    • »
      »
      »
      8 years 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
      → Reply
      • »
        »
        »
        »
        8 years 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

        → Reply
  • »
    »
    8 years 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

    → Reply
  • »
    »
    8 years 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.

    → Reply
»
8 years 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.

→ Reply
  • »
    »
    8 years 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]); }

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

    You are right, it was a DP indeed :)

    → Reply
  • »
    »
    8 years 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

    → Reply
  • »
    »
    8 years 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

    → Reply
  • »
    »
    8 years 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.

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

I loved D. Thanks for a great contest.

→ Reply
»
8 years 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 :/

→ Reply
»
8 years 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

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

    Can you tell me the idea behind E, please?

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

      I used centroid decomposition to solve E

      → Reply
      • »
        »
        »
        »
        8 years 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.

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

          Yeah you are right i got TLE :(

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

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

          → Reply
    • »
      »
      »
      8 years 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.

      → Reply
    • »
      »
      »
      8 years 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.

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

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

        → Reply
    • »
      »
      »
      8 years 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.

      → Reply
  • »
    »
    8 years 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.

    → Reply
»
8 years 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 !

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

A Problem copied? where?

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

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

Can someone give an idea for D?

→ Reply
  • »
    »
    8 years 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)

    → Reply
»
8 years 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.

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

    And here is E :P

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

      I'm also pretty sure B is somewhere online

      → Reply
    • »
      »
      »
      8 years 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.

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

        The solution would still be the same.

        → Reply
        • »
          »
          »
          »
          »
          8 years 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 ?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years 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.

            → Reply
          • »
            »
            »
            »
            »
            »
            8 years 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

            → Reply
»
8 years 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.

→ Reply
»
8 years 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

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

    I could only hack one submission that returned -1 when one string contained the other, so my hack case was: aaaa aa

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

    24496013

    → Reply
»
8 years 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

→ Reply
  • »
    »
    8 years 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

    → Reply
    • »
      »
      »
      8 years 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.

      → Reply
      • »
        »
        »
        »
        8 years 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

        → Reply
        • »
          »
          »
          »
          »
          8 years 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

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

            Dude, read it until the end.

            → Reply
          • »
            »
            »
            »
            »
            »
            8 years 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 :)

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

      220 275 330 form a Valid Triangle.

      → Reply
      • »
        »
        »
        »
        8 years 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

        → Reply
    • »
      »
      »
      8 years 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.

      → Reply
      • »
        »
        »
        »
        8 years 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?

        → Reply
  • »
    »
    8 years 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://mirror.codeforces.com/blog/entry/50280?#comment-342293

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

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

      → Reply
      • »
        »
        »
        »
        8 years 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

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

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

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years 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

            → Reply
  • »
    »
    8 years 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.

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

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

      → Reply
    • »
      »
      »
      8 years 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 ?

      → Reply
      • »
        »
        »
        »
        8 years 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://mirror.codeforces.com/contest/766/submission/24500965 passed hack soln http://mirror.codeforces.com/contest/766/hacks/296935/test

        → Reply
        • »
          »
          »
          »
          »
          8 years 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years 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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years 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.

              → Reply
  • »
    »
    8 years 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...

    → Reply
»
8 years 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?

→ Reply
  • »
    »
    8 years 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 ...

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

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

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

    His results/submissions have disappeared

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

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

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

guys is that site is true ?! http://cfpredictor.us-west-2.elasticbeanstalk.com/roundResults.jsp?contestId=766

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

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

→ Reply
»
8 years 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...

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

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

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

Thanks for this good contest .

I really like these problems.

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

Why codeforces div2 contests are becoming easy?

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

    Maybe you're getting better?

    → Reply
    • »
      »
      »
      8 years 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'...

      → Reply
      • »
        »
        »
        »
        8 years 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.

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

    What's the problem with it?

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

      Solving hard problems makes you strong.

      → Reply
      • »
        »
        »
        »
        8 years 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.

        → Reply
  • »
    »
    8 years 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.

    → Reply
»
8 years 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))

→ Reply
  • »
    »
    8 years 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.

    → Reply
»
8 years 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

→ Reply
  • »
    »
    8 years 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.

    → Reply
»
8 years 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

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

Will be editorial?

→ Reply
»
8 years 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://mirror.codeforces.com/contest/766/submission/24497421

→ Reply
»
8 years 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"
→ Reply
»
8 years 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

→ Reply
»
8 years 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

→ Reply
»
8 years 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.

→ Reply