By mahmoudbadawy, history, 5 years ago,

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 Congratulations to the winners!

Div1+Div2:

Div2:

• +319

 » 5 years ago, # | ← Rev. 2 →   -332 A true Codeforces fan can not scroll down without upvoting this comment .
•  » » 5 years ago, # ^ |   +23 *without downvoting this comment
• »
»
»
5 years ago, # ^ |
-26

# Первый выпуск моего стэндапа

Уже доступен

 » 5 years ago, # |   +25 MikeMirzayanov mahmoudbadawy There is a bug with registration. Div1 users cant register unofficially.
•  » » 5 years ago, # ^ |   +35 Sorry, please try again now.
 » 5 years ago, # |   +3 Hope to be a good round. Good luck to all participants.
•  » » 5 years ago, # ^ |   -19 you don't need to say "good luck" buddy. coz good luck is not related to contest anywhere
•  » » » 5 years ago, # ^ |   +1 coz luck is not rated)
•  » » » 5 years ago, # ^ |   +40 I don't know man... sometimes when the site doesn't lag at all I feel pretty lucky...
 » 5 years ago, # |   +2 The email says the round will have 6 problems, but the post says 5. Which one is it?
•  » » 5 years ago, # ^ |   +5 They are 5 problems.
 » 5 years ago, # |   -20
•  » » 5 years ago, # ^ |   +5 That's FlapJack not Chowder.
 » 5 years ago, # |   0 is this the 1st Arabic official round on CF ??
•  » » 5 years ago, # ^ | ← Rev. 2 →   +12 No, round #67 was written by ahmed_aly: Codeforces Beta Round #67 (Div. 2)
•  » » » 5 years ago, # ^ |   0 problems are really good
•  » » 5 years ago, # ^ | ← Rev. 2 →   +2
•  » » » 5 years ago, # ^ |   +19 That's Great , one day we will have a round prepared by us
•  » » » » 5 years ago, # ^ |   0 Actually in Syria we have some great problem seters, they should have prepared a round here long time ago :D
 » 5 years ago, # |   -107 Is it rated??
•  » » 5 years ago, # ^ | ← Rev. 2 →   -18 There's always that one guy who asks this question.
 » 5 years ago, # |   +9 mohammedehab2002 shares a name with an Egyptian weightlifting superstar. Guessing not the same guy but would be cool if so.
 » 5 years ago, # |   +19 short blog :) I love it
•  » » 5 years ago, # ^ |   -9 Don't have character?
•  » » » 5 years ago, # ^ |   0 I think it might be president Elsissi :P
 » 5 years ago, # |   -36 Copy Codeforces testcases by clicking on them :OAn extension for chrome only Installation: Download from https://drive.google.com/file/d/0B4HQVLPL4OXRUHJNa0dnQkNYNzA/viewyou can see GIF https://media.giphy.com/media/26xBNH5TzjX0z90R2/giphy.gifGo to "chrome://extensions/" Drag and drop the file into the pageGood Luck And Have Fun <3
•  » » 5 years ago, # ^ |   -14 Thank you :(
 » 5 years ago, # |   -22 Here's to clever yet easy problems! Hoping to become candidate master finally...
•  » » 5 years ago, # ^ |   0 Your new rating is determined by your contest rank.
 » 5 years ago, # |   0 Fast and accurate wins the race.
 » 5 years ago, # |   0 Rating != Knowledge Even newbies can think of a beautiful problem, which can be challenging for masters!
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 @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".
•  » » » 5 years ago, # ^ |   +4 He is banned (his comments and posts deleted automaticly). LOL :D
 » 5 years ago, # |   -29 Prepare by pupil?
•  » » 5 years ago, # ^ |   -16 Prepared by a specialist and Candidate Master
 » 5 years ago, # |   +34 I have short.
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 I think there were a lot of replys 5 minutes ago..UPD: I think admin deleted them.
 » 5 years ago, # |   0 the new contetst with specialist builder. this contest will be nice
 » 5 years ago, # |   +3 New authors often surprise CodeForces community (in good way)... Trust on interesting contest, good luck to all!)
 » 5 years ago, # |   +5 New contest, new opportunities to learn and possibly get better. Thank you CodeForces
 » 5 years ago, # |   +135 What a stupid contest
•  » » 5 years ago, # ^ |   +4 why do you think so?
•  » » » 5 years ago, # ^ |   +4 problem D and E are old problems
•  » » » » 5 years ago, # ^ |   +1 how did you solve E ?
•  » » » » 5 years ago, # ^ |   -8 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.
•  » » » » » 5 years ago, # ^ |   +3 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 years ago, # ^ |   0 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
 » 5 years ago, # |   0 already got these hackers
 » 5 years ago, # |   -6 belive it or not, this was the worst contest I have ever seen
•  » » 5 years ago, # ^ |   +7 Maybe your worst result ever ;)
•  » » » 5 years ago, # ^ |   0 Should I say something or you know what I'm thinking about ?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +1 Come on :)I was just kidding!
•  » » » » » 5 years ago, # ^ |   +3 Cool :)
•  » » 5 years ago, # ^ |   +15 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.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 5 years ago, # ^ |   +5 I did the same as you, but honestly I found that writing essentially three solutions was quite annoying. Maybe tedious is an overstatement.
•  » » » » » 5 years ago, # ^ |   +4 Maybe they intended the problem to look difficult.
 » 5 years ago, # |   +23 I'll just leave this here...
•  » » 5 years ago, # ^ |   +8 now, may I'll see legendary newbie rate !
 » 5 years ago, # | ← Rev. 2 →   +98 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.
•  » » 5 years ago, # ^ |   +8 Awesome, I love it :)
•  » » 5 years ago, # ^ |   +5 Good job!
•  » » 5 years ago, # ^ |   0 Nice. But I think I will just use the page instead of the extension. Thank you for this.
•  » » 5 years ago, # ^ |   0 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?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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!
•  » » 5 years ago, # ^ |   +9 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!
•  » » » 5 years ago, # ^ |   +5 Thank you! I will try to fix this)
 » 5 years ago, # |   +5 In B, we can write O(n^2) because maximum value of n for which answer is NO is ~90 ?
•  » » 5 years ago, # ^ |   +3 You can sort and itertate through in B.
•  » » 5 years ago, # ^ |   0 I tried to find a hack test case for O(n ^ 3) and O(n ^ 2) solutions.. :D
•  » » » 5 years ago, # ^ |   0 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
•  » » » » 5 years ago, # ^ |   0 Hm. I think this test case is wrong because "220 275 330" are valid sides
•  » » » » » 5 years ago, # ^ |   0 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
•  » » » » » » 5 years ago, # ^ |   0 Oooh. ok)
•  » » 5 years ago, # ^ |   0 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.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +14 The smallest test case of answer "NO" is the fibonacci sequence. So if N >= 45, it is always possible to make a triangle.
•  » » » 5 years ago, # ^ |   0 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
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 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<=cIf 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
 » 5 years ago, # | ← Rev. 6 →   +5 How to solve problem D? I could think of an approach using 2 dsu's. but did'nt code
•  » » 5 years ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » 5 years ago, # ^ |   0 how update and handle sets in this case? 1 aba aca 1 ada aea 1 afa aga 2 afa aea 
•  » » » » 5 years ago, # ^ |   +3 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 subcaseslet'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
•  » » 5 years ago, # ^ |   +6 Yes it can be solved using dsu, you just need to color the verticles (the words) and find the answer for each query
•  » » 5 years ago, # ^ |   +18 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.
 » 5 years ago, # |   +5 Can someone explain C? I thought it was DP but I couldn't figure out how to put it together.
•  » » 5 years ago, # ^ |   0 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]); }
•  » » 5 years ago, # ^ |   0 You are right, it was a DP indeed :)
•  » » 5 years ago, # ^ |   0 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
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   +12 I loved D. Thanks for a great contest.
 » 5 years ago, # |   0 Lost a lot of points on C, because I thought there should be at least one cut :/
 » 5 years ago, # |   0 with 10 more minutes I would have finished debugging D and solved all problems. :( contest is much easier than usual
•  » » 5 years ago, # ^ |   0 Can you tell me the idea behind E, please?
•  » » » 5 years ago, # ^ |   +8 I used centroid decomposition to solve E
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » 5 years ago, # ^ |   +5 Yeah you are right i got TLE :(
•  » » » » » 5 years ago, # ^ |   +5 Hmm... I solved it using centroid decomposition and it passed just fine.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Perform DP for each bit counting the ways with xor = 1 and xor = 0.
•  » » » 5 years ago, # ^ |   +1 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.
•  » » » » 5 years ago, # ^ |   0 I could not understand your approach. Can you elaborate a little please.
•  » » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   0 Although I agree with u based on D and E, C was better than usual. Just check out round #394, C was a cakewalk.
 » 5 years ago, # |   +5 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 !
 » 5 years ago, # |   +18
 » 5 years ago, # |   0 Can someone give an idea for D?
•  » » 5 years ago, # ^ |   +1 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)
 » 5 years ago, # | ← Rev. 2 →   +17 Problem D is here Link However without the part of answering some queries on relations.
•  » » 5 years ago, # ^ |   +16 And here is E :P
•  » » » 5 years ago, # ^ |   +22 I'm also pretty sure B is somewhere online
•  » » » » 5 years ago, # ^ |   0 Second POI.
•  » » » » 5 years ago, # ^ |   +4 B is a simpler version of this https://www.codechef.com/FEB17/problems/MAKETRI
•  » » » » » 5 years ago, # ^ |   +39 That's like saying A is a simpler version of the KMP algorithm...
•  » » » » 5 years ago, # ^ |   0
•  » » » 5 years ago, # ^ |   +28 It is different from E which has weights on vertices, not on edges.
•  » » » » 5 years ago, # ^ |   0 The solution would still be the same.
•  » » » » » 5 years ago, # ^ |   0 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 ?
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +10 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.
•  » » » » » » 5 years ago, # ^ |   +4 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
 » 5 years ago, # |   +1 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.
 » 5 years ago, # |   0 Can i see some hack cases for 'A' that you people used. I tried hacking, but failed. Thanks
•  » » 5 years ago, # ^ |   0 I could only hack one submission that returned -1 when one string contained the other, so my hack case was: aaaa aa
•  » » » 5 years ago, # ^ |   0 +1
•  » » 5 years ago, # ^ |   0 abc abc 24496013
•  » » » 5 years ago, # ^ |   0 +1
 » 5 years ago, # | ← Rev. 2 →   +3 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
•  » » 5 years ago, # ^ |   +1 100000 1 1 2 3 5 8 13 21 34 55 110 165 220 275 330 385 etc
•  » » » 5 years ago, # ^ |   0 In this way, the value won't fit in integer and will be > 10^9, so I think this won't work.
•  » » » » 5 years ago, # ^ |   +10 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
•  » » » » » 5 years ago, # ^ |   -16 The 44'th number of this sequence ( i.e. 1 1 2 3 5 8 13 ......) is 1134903170 which is > 10^9
•  » » » » » » 5 years ago, # ^ |   +10 Dude, read it until the end.
•  » » » » » » 5 years ago, # ^ |   +15 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 :)
•  » » » 5 years ago, # ^ |   0 220 275 330 form a Valid Triangle.
•  » » » » 5 years ago, # ^ |   +5 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
•  » » » 5 years ago, # ^ |   0 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.
•  » » » » 5 years ago, # ^ |   +5 Is it really hard to notice that the sequence is not just simply Fibonacci sequence?
•  » » » » » 5 years ago, # ^ |   0 Sorry. My bad.
•  » » 5 years ago, # ^ |   +3 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
•  » » » 5 years ago, # ^ |   0 O(n^3) solution got TLE on test case 33
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Test 33 is abcd abc, so I'm guessing there was a bugged while instead of 3 forsedit: disregard this comment, wrong problem
•  » » » » » 5 years ago, # ^ |   0 You are talking about problem A, while were talking about problem B.
•  » » » » » » 5 years ago, # ^ |   0 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
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 5 2 2 2 100 1000 and 6 1 10 100 10 1 1 correct answers: YES | YESEdit: 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.
•  » » » 5 years ago, # ^ |   0 O(n^3) solution will also give AC output for your inputs.
•  » » » 5 years ago, # ^ |   0 But have you seen that in system test, O(n^3) solution got TLE on test case 33 ?
•  » » » » 5 years ago, # ^ |   0 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
•  » » » » » 5 years ago, # ^ |   +5 You unfortunately forgot to add an extra zero. The max input size is 10^5, where your hack is only 10^4.
•  » » » » » » 5 years ago, # ^ |   0 it was n^3 soln if it failed at 100000 it will also fail at 10000
•  » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » 5 years ago, # ^ |   0 100000 1 1000 10004 10006 10008 10010 10012 10014 10016 10018 10020 10022...
 » 5 years ago, # |   +20 How can this user, r_clover, solve both problem B and D within a minute?
•  » » 5 years ago, # ^ |   0 Wrote code for B, forgot submitting, then wrote code for D, submitted D, realized he had forgotten submitting B and submitted B.
•  » » 5 years ago, # ^ |   0 Exactly ! and the funny thing is that took him 4 mins to solve A and 7 mins for both A and D ...
•  » » 5 years ago, # ^ |   +37 Coding styles are different too... He was not alone :)...
•  » » 5 years ago, # ^ |   0 His results/submissions have disappeared
•  » » 5 years ago, # ^ |   +26 In the same way as you did here and got disqualified :
•  » » » 5 years ago, # ^ |   0 S for SAVAGE
 » 5 years ago, # |   0 Problems are good i think...i hope there would be a chance today...
 » 5 years ago, # |   +3 guys is that site is true ?! http://cfpredictor.us-west-2.elasticbeanstalk.com/roundResults.jsp?contestId=766
 » 5 years ago, # |   -16 So, Codeforces started copying problem from UVa :\ :\ :P
 » 5 years ago, # |   +1 That moment when you failed both C and E only because of wrong answer on n = 1 case...
 » 5 years ago, # |   0 Did anyone else failed system test on test 22 on problem C.
 » 5 years ago, # | ← Rev. 2 →   0 Thanks for this good contest . I really like these problems.
 » 5 years ago, # |   +3 Why codeforces div2 contests are becoming easy?
•  » » 5 years ago, # ^ |   +47 Maybe you're getting better?
•  » » » 5 years ago, # ^ |   +7 E div2 in 'div1+div2 rounds', are harder than E div2 in 'only div2 rounds'...
•  » » » » 5 years ago, # ^ |   0 But it shouldn't be!div2 only contests should be interesting for div1 users too.
•  » » 5 years ago, # ^ |   -6 What's the problem with it?
•  » » » 5 years ago, # ^ |   -18 Solving hard problems makes you strong.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   -14 AB should be easy because before solving harder problems (CDE) we have to solve easier problems first.
•  » » 5 years ago, # ^ | ← Rev. 2 →   -11 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.
 » 5 years ago, # |   0 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))
•  » » 5 years ago, # ^ |   0 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.
 » 5 years ago, # |   +24 Interesting thing about problem B is that stupid solution which uses random works fine and passes all tests. Solution: 24513380
•  » » 5 years ago, # ^ |   +5 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.
 » 5 years ago, # |   0 Div2 C, rip to all of those who got WA on test 36
 » 5 years ago, # |   0 Will be editorial?
•  » » 5 years ago, # ^ |   0 It's already here: link
 » 5 years ago, # |   0 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
•  » » 5 years ago, # ^ |   0 check the editorial and you will understand why O(n^3) passed system test
 » 5 years ago, # |   0 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" 
•  » » 5 years ago, # ^ |   0 It means python is slowsee it for more information
 » 5 years ago, # |   0 Good round. Where I can find a tutorial of these tasks for training?
•  » » 5 years ago, # ^ |   0 I'm sorry I have found — http://codeforces.com/blog/entry/50294
 » 5 years ago, # |   0 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
 » 5 years ago, # |   0 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
 » 5 years ago, # |   0 who can solve this problem http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=3092&run_id=249r32910#1
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 FIRST TRAVERSE WHOLE ARRAY ANF FIND SUMIF(SUM IS ODD) RETURN -1;THEN USE DP FOR SIZE=N/2 AND TOTAL=SUMDP[SIZE][TOTAL]=DP[SIZE-1][TOTAL] || ( DP[SIZE-1][TOTAL-Arr[i]] for all i ) RETURN DP[N/2][SUM];
•  » » » 5 years ago, # ^ |   0 Can you send the code
•  » » » » 5 years ago, # ^ |   0 I don't understand
 » 5 years ago, # | ← Rev. 2 →   0 Hey guys. How to solve E? I can't get this prob.
 » 5 years ago, # |   0 Hey guys. How to solve this problem https://www.e-olymp.com/ru/contests/7949/problems/66445? I can't get this prob.