Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

niyaznigmatul's blog

By niyaznigmatul, 3 years ago, translation, ,

Hi, Codeforces!

Codeforces Round #402 (Div. 1) and Codeforces Round #402 (Div. 2) are going to happen on February, 26th, at 08:05 AM UTC. The round will run at the same time with Innopolis University Open, Olympiad in Informatics. Division 1 problems are the same as olympiad problems. Some of Division 2 problems are prepared by MikeMirzayanov, thanks to him.

The problems are developed by MikeMirzayanov, YakutovDmitriy, VArtem, firezi, burakov28, pashka.

We hope you enjoy the problems!

UPD:
problem scores for div1: 500 — 1000 — 1500 — 2250 — 2250
problem scores for div2: 500 — 1000 — 1000 — 1500 — 2000 — 2500

UPD 2: Congratulations to winners!

Top-10 (Div.1)

Top-10 (Div.2)

Editorial is here.

• +429

 » 3 years ago, # |   -17 too bad, I can't do this round :(
•  » » 3 years ago, # ^ |   +17 Is it the time issue?
•  » » » 3 years ago, # ^ |   -68 Actually no, I have some work to be done at the same time :\
•  » » » 3 years ago, # ^ | ← Rev. 4 →   -77 .
•  » » 3 years ago, # ^ |   -23 Brother Miss it . This problemset are very easy I think your rating must be Increased if you participate this contest
•  » » » 3 years ago, # ^ |   0
•  » » 3 years ago, # ^ |   0 problem C : http://codeforces.com/contest/779/submission/2532249 (Accepted).
 » 3 years ago, # |   -18 how many problemset sir ?
•  » » 3 years ago, # ^ |   -27
 » 3 years ago, # |   +32 LOL!!One problemsetter of each colorNow that's what I call justice
•  » » 3 years ago, # ^ |   +9 there are two reds, no cyan, no green, no grey and no whiteAre you having Color Blindness :3
•  » » » 3 years ago, # ^ |   +18 there are one grandmaster, and one international grandmaster
•  » » » » 3 years ago, # ^ |   +8 but it is the same color ;)
•  » » » » » 3 years ago, # ^ |   +114 only women can see the difference between these two colors.like this
•  » » » » » » 3 years ago, # ^ |   +27 This makes no sense, "green-yellow" is the shade of green farthest from yellow here...
•  » » » » » » » 3 years ago, # ^ |   +16 You're still thinking in masculine color space.Feminine color space has three dimensions. It's like the transition from flatland to 3-space; impossible to imagine unless you already live there.
•  » » » » » » » » 3 years ago, # ^ |   -10
•  » » » 3 years ago, # ^ |   +26 VArtem is International Grandmaster and pashka is Grandmastersorry man there's no thing called completely justice in this world :(
 » 3 years ago, # |   +1 Do you mean Sunday, 26th?
 » 3 years ago, # |   +237 Is there any reason that recently Codeforces Contests are announced in short time before contest start time?
•  » » 3 years ago, # ^ |   0 kind of a surprise :D
•  » » » 3 years ago, # ^ |   +57 It's not only surprise but also sad for me. The contest time is quite close to my training contest in group.In fact, I have moved the training contest time from Friday to Sunday because its original time overlap to CF #401...
 » 3 years ago, # |   -32 Though I have a lab exam at that time but I will try my best to attend this contest. Hope I'll be able to attend and can have positive ratings
•  » » 3 years ago, # ^ |   -8 if you actually miss the exam and do the contest, you Sir, are a legend.
 » 3 years ago, # |   +9 Nice time !
 » 3 years ago, # | ← Rev. 2 →   -42 Wow! Another chance to get high rating! :3
•  » » 3 years ago, # ^ |   -11 it depends on your rank not on the difficulty of the problemset
 » 3 years ago, # |   +75 I love it when there are contests on every 2-3 days. :)
•  » » 3 years ago, # ^ |   0 I love it,too.But I find it's difficult.
 » 3 years ago, # |   +66 It completely collides with Grand Prix of Wroclaw of OpenCup. Which one do you participate?
•  » » 3 years ago, # ^ |   0 If I'm not wrong the Gran Prix starts just when the CF Round ends...
•  » » » 3 years ago, # ^ |   +45 Grand Prix starts just when CF Round starts
 » 3 years ago, # |   +7 Why did codeforces start holding its contests at such an odd times? Earlier it was used to be around 16:00 UTC.
•  » » 3 years ago, # ^ |   +100 Maybe because of this The round will run at the same time with Innopolis University Open, Olympiad in Informatics.
 » 3 years ago, # |   -18 there is always a pole between you and things you love to do this pole is my school :( I'm not gonna participate in this round tomorrow
•  » » 3 years ago, # ^ |   0 Its Sunday in India..So no School :)
•  » » » 3 years ago, # ^ |   +38 actually in my country the weekend is on Friday and Saturday
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   -62 0.0
•  » » 3 years ago, # ^ | ← Rev. 4 →   -9 as I said before.there's no thing called completely justice in this world :( I face the same problem :(
•  » » » 3 years ago, # ^ |   -19 Nice picture.
 » 3 years ago, # |   -6 Five problems as usual ?
 » 3 years ago, # |   0 8:00 am GMT +6 is the best time!
 » 3 years ago, # |   -8 number problems ?
 » 3 years ago, # |   -91 Is it rated?
 » 3 years ago, # | ← Rev. 2 →   +45 Is this the first time that the two divisions have different number of problems?
•  » » 3 years ago, # ^ |   -17 lol
•  » » 3 years ago, # ^ | ← Rev. 4 →   -43 Also the the first time I see score of problem B and C in div2 are equal.
•  » » 3 years ago, # ^ |   +5 No, but it's really rare. round #364
•  » » 3 years ago, # ^ |   0 No it's not the first time..
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I mean it's the first time I see it like this.
 » 3 years ago, # | ← Rev. 5 →   -79 UPD : I didnt send that message,this guy send it with my account. I know that it is rated :D . pls stop down-voting me . my contribution was +3, but now -25 :'(
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 sorry
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -55 .
•  » » 3 years ago, # ^ | ← Rev. 3 →   -57 .
 » 3 years ago, # |   0 Hack for DIV — 2 B ???????
•  » » 3 years ago, # ^ |   0 others bug :-"
•  » » 3 years ago, # ^ |   +3 Mine was 11001 3Answer is 4.
 » 3 years ago, # | ← Rev. 2 →   +1 How to solve Div2D?
•  » » 3 years ago, # ^ |   +1 Binary search
•  » » 3 years ago, # ^ |   +1 I did Binary Search.
•  » » 3 years ago, # ^ |   0 can you explain a bit?
•  » » » 3 years ago, # ^ |   +6 You binary search on the number of elements to delete from the string (just mark the indices in a boolean array). Then, if the string I'm looking for is a subsequence of the original string with modified characters then it's possible for her to continue playing so I try a higher value. If it isn't a subsequence then I have to try lower. Checking if it's a subsequence can be done in O(n).
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Suppose i is the answer then it is possible to construct the pattern for any value less than or equal to i. So we can form a sequence like TTTTFFFFF (t=possible f=not possible). We have to find the last T where it is possible to construct pattern. Which can be done through Binary Search.25045586
•  » » 3 years ago, # ^ |   +5 Binary search(O(log(n))) on length of permutation and check till which index there exist a subsequence 'p' in it (in O(n)). Hence resultant complexity is O(n*log(n))
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +3 Hey, shouldn't we include the time it would take to delete the elements as well?Also, are you using some other method for deleting? Because otherwise, the deletion itself would take O(n) time.
•  » » » » 3 years ago, # ^ |   0 You don't actually have to delete elements from the string, replace characters at required indices with some special character and check for subsequence(which can be done in O(n)). Refer to my code to get the idea.
•  » » » » » 3 years ago, # ^ |   0 Cool. Thanks!
•  » » 3 years ago, # ^ | ← Rev. 4 →   0 I did it with online subsequence matching O(n) with a little twist. http://ideone.com/R9NbzHUPD: nvm, it got TLE :(
•  » » 3 years ago, # ^ | ← Rev. 6 →   -7 I think It can be done using hashing + BIT or hashing + Seg tree. Link: String Hashing If you read this you can link strategy to this problem. Of course, binary search is easy one solution but It would be worth to learn so it can be applied many problems like this( Sometimes it is easier to implement String Hashing than other Solution). PS: Accuracy of Solution depends on Probability of collisions.
 » 3 years ago, # |   0 Ideas on D div.2?
•  » » 3 years ago, # ^ |   +9 binary search
•  » » 3 years ago, # ^ |   +4 Take l=0 r=n-1 . DO binary search. Change the first (l+r)/2 elements as say '_' and check if p is a substring of t — http://www.geeksforgeeks.org/given-two-strings-find-first-string-subsequence-second/. If yes make l=(l+r)/2+1 and ans=(l+r)/2 else r=(l+r)/2-1.Display ans
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 binary search ... imagine that you have a query that answer if the current S has a subsequence T. This "function" is: true true true.... false false false.. You just have to find the last occur of true. You have to find the optimal prefix of the array permutation that answer TRUE on this query :) ! I hope it helps you ! Sorry for my bad english!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 .
 » 3 years ago, # | ← Rev. 2 →   -89 0.0
•  » » 3 years ago, # ^ |   +21 Hey guy stop it please
•  » » » 3 years ago, # ^ |   -9 so sorry...i'm a newbie...i don't know that... so sorry so sorry everyone
•  » » 3 years ago, # ^ |   -11 Usually I'd use a "strict <" in function "cmp". It could be the problem. Just a hint for you to dive in.However, please do not post your code everywhere, especially in unrelated posts.
•  » » » 3 years ago, # ^ |   0 so sorry...i'm a newbie...i don't know that... so sorry and thanks very very very much..
•  » » 3 years ago, # ^ |   0 share your code using idone or just give the link of your submission :| Dont spam the page
•  » » » 3 years ago, # ^ |   0 so sorry i'm newbie and thanks very much...
 » 3 years ago, # |   +56 Seems like problem E's parsing is harder than task itself lol.
•  » » 3 years ago, # ^ |   +8 I think so. It cost me too much time.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 How to solve it?edit-Just figured it out.
•  » » » 3 years ago, # ^ |   +3 I guess solving independently for each bit will work.
•  » » » » 3 years ago, # ^ |   +3 Handling the variables and parsing is the difficult part, yes.
•  » » 3 years ago, # ^ |   +5 I don't think so. You can use a map to point a variable to its declaration location in input, ignore the := operator and easily parse a binary string to an integer/boolean array.
 » 3 years ago, # |   +3 I misread problem E. I could have solved it :(
•  » » 3 years ago, # ^ |   +3 problem was quite easy but parsing it was hard.
•  » » » 3 years ago, # ^ |   0 Parsing was not an issue in my case.
 » 3 years ago, # |   +3 From problem E, how do you handle cases like this?:3 5 a := 10100 b := a OR ? c := b XOR ?
•  » » 3 years ago, # ^ |   +11 Notice that each bit for ? can be decided independently. So, for each column of bit, just try 0 and 1 and take the optimal one.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Oh. My train of thinking was along that line. Now I feel stupid :(RIP Rating
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Does the order of how I process the variables matter? If I chose to evaluate variable c first before evaluating b, then wouldn't I have to know what b could possibly be before I could calculate c?EDIT: Nevermind, just re-read the problem statement again. "Operands of the operation may be either variables defined before, or the number, chosen by Peter. "
•  » » 3 years ago, # ^ | ← Rev. 3 →   +5 For every bit in every variable, you should know it's value, for when the corresponding bit in ? is 0 and for when the corresponding bit in ? is 1. For example:a = [[1, 1], [0, 0], [1, 1], [0, 0], [0, 0]]b = [[1, 1], [0, 1], [1, 1], [0, 1], [0, 1]] (you calculate this using just variable a)c = [[1, 0], [0, 0], [1, 0], [0, 0], [0, 0]] (you calculate this using just variable b)E.g. the emphasized array in c means that if ? = "..0..", then c = ".. 1 .."; and if ? = "..1..", then c = "..0..".
 » 3 years ago, # | ← Rev. 2 →   +17 I believe that a large number of chinese can solve Div2E, for a similar problem has appeared in NOI2014. The similar problem's chinese name is "起床困难综合征", you can find it on many websites. NOI is olympics in infomatics in China. Sorry for poor english.
•  » » 3 years ago, # ^ |   -37 Hey man... Don't do that!(I've learned Chinese for years and the characters this man posted has nothing to do with "Olympics in Informatics in China". Don't waste your time on searching that)
•  » » » 3 years ago, # ^ |   +12 LOL~ The Chinese characters are the name of the problem that is similar to Div2E mentioned by __stdcall.
•  » » » 3 years ago, # ^ |   0 I mean that, the problem's name is "起床困难综合征". You can submit the problem on this website. http://uoj.ac/problem/2
•  » » » » 3 years ago, # ^ |   +11 Sorry, my mistake...But it's a really interesting title
•  » » » » » 3 years ago, # ^ |   +6 That's also my fault. I have updated my comment in order to prevent from misunderstanding.
•  » » » 3 years ago, # ^ |   +3 "Get up difficult syndrome."
 » 3 years ago, # |   +49 How to solve Div1 C?? Thanks in advance :)
•  » » 3 years ago, # ^ | ← Rev. 3 →   +27 I used DSU on tree technique. Removing character at index p is equivalent to removing all edges at depth p in the trie. The hash of a vertex is the hash of the string formed when I go from the root to this vertex. For each vertex v, I store the hashes of all vertices in its subtree.Then I can easily find out the number of distinct hashes in its subtrees after removing edges from v to its children. Code
•  » » » 3 years ago, # ^ |   +8 the link is broken.Please check it
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +2 Fixed. :)It's working for me. If it's still not accessible to you, just google "DSU on tree codeforces".
•  » » » 3 years ago, # ^ |   0 Okay, so, at some point, you will have a set S with the hashes of all vertices in the subtree rooted at v (using DSU on tree). But how exactly do you remove the edges leaving v? I imagine that you pass through each element of S applying some hash-related operation to remove the first edge, then you'll get a new hash and you'll put it in another set S'. After this pass over S, the size of set S' is the answer. Is that it? If yes, what is the hash-related operation to remove the first edge? Thanks for the help!
•  » » » » 3 years ago, # ^ |   0 Suppose I am at vertex u. And the heaviest child is v. After I have processed v, the global map I use already has the hashes of all nodes in the subtree of v. I need to check other subtrees of u. Let us consider node w in some subtree of u (let that be x) such that w is not the heaviest child of u. Now, I need to calculate the hash of w assuming that the edge u->x does not exist. This is equivalent to calculating the hash value of w assuming the edge u->x has the same character on it as the edge u->v. I do exactly this in my code. Then the number of nodes which remain after deleting the edges from u will be equal to the number of nodes in the trie-1 (because it includes v too which must be subtracted).The above explanation is very specific to my code.
•  » » 3 years ago, # ^ |   +5 I solved it in , where k = 26, the alphabet. Solution idea is pretty simple  –  "Let's try and merge all child tries of the current node and see what total size we get". You can merge two tries in time proportional to the size of lesser one, and it is well known that in worst case each node will be in mergers.So, the algorithm: Iterate over all nodes, and also compute their depths in order to update answer for correct value of p. Merge all child tries of current node and compute the size of this merged trie, then add size change to the answer for corresponding p. Roll back the changes and go to the next node.
•  » » » 3 years ago, # ^ |   +7 Could you elaborate why it is O(n k log n)? I thought of the same approach, but wasn't sure it would work.
•  » » » 3 years ago, # ^ |   0 I've tried to implement the similar approach but failed with the "rollback" part, could you please give some detail on that?
•  » » » » 3 years ago, # ^ |   +10 One of the simplest ways: every time you change any variable, push back {what was changed, what value it had before} into a vector, then reverse it and apply the same operations backwards.
•  » » » » » 3 years ago, # ^ |   0 Thank you, I will try that)
•  » » » 3 years ago, # ^ |   +13 I practically copied your code and submitted it without the nodes' size verification (i.e. the swap(u, v) in merge()) and the runtime was 200ms. Any idea why?
•  » » » » 3 years ago, # ^ |   0 fofao_funk 779C — Dishonest Sellers why i need to sort array with respect to a[i]-b[i] ? what is the proof ?a
•  » » » 3 years ago, # ^ |   +8 i thought your solution will fail on a test with binary tree where every left edge is "a" and right is "b" (quite a few vertices will be merged then), but it didn't. however, i also ran solutions of top-10 and only half of them where fast enough on my computer, some even getting 40s+.
 » 3 years ago, # | ← Rev. 2 →   +19 I almost solved problem E (DIV 2). but time ran out. I am such a slog. Treat each bit independent of other m-1 bits!!!
•  » » 3 years ago, # ^ |   +3 you are not alone
 » 3 years ago, # |   +4 How to solve problem D in Div.1?
•  » » 3 years ago, # ^ |   0 any ideas? What was the approach?
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +9 I read some AC codes and found this excellent idea: The operation is reversible and so we can try to turn both the current configuration and the desired configuration into a configuration like:UUUUUUUUDDDDDDDDUUUUUUUUDDDDDDDDUUUUUUUUDDDDDDDDand then you can combine the two sets of operations to get the final operations. Sorry for my poor English..
•  » » » » 3 years ago, # ^ |   +44 the idea works because each time we try to fix the top-leftmost block to be LR, if the block is originally UD then we fix the next block to UD and turn, and if the next block is LR then the block below it is LR(done) or UD and so on... eventually we will have a "ladder" and this ladder cannot continue indefinitely, so there will always be solution.
 » 3 years ago, # |   +27 Was it intended to fail MNlog(N) solution on Div 1B?
•  » » 3 years ago, # ^ |   +5 You have O(M*N*log(N)*len(var)) ~= 1/2 * 10^9. That's a lot to STL
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I changed map to unordered_map after the contest and got AC. How do you tell when unordered_map is faster?
•  » » » 3 years ago, # ^ |   0 unordered_map is generally (quite a bit) faster if nobody is attacking your hash (to cause collisions) and when you have sufficient buckets (check out c++ stl reserve()).
 » 3 years ago, # | ← Rev. 2 →   +8 The only thing that made problem E tougher was the input format. Takes loads of time to write the code to process the input variables.(String splitting n all). I missed solving it by 2-3 mins due to this.The crux idea of the problem was not that difficult according to me. Complexity of N × M × 2 is good enough.
 » 3 years ago, # | ← Rev. 6 →   +93 http://codeforces.com/contest/778/submission/25048949My solution to D.I just keep changing every LR to UD, and then every UD to LR, recursively, until it is done.Is this solution correct?
•  » » 3 years ago, # ^ |   +39 It's not the solution that we expected, I don't know how to prove it but it looks like it's correct.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +61 Suppose m is even. Let's call 'step' changing avery LR to UD and then every UD to LR, as done in matthew99's solution. We want to show that eventually all cells become L or R.A cell is 'stable' if it is L or R and it stays the same after performing an arbitrary number of steps. Suppose by contradiction there is a cell that never become stable, and consider the first one which has this property (it means that all the cells on the left and those placed in some preceding row eventually become stable. We can assume they are already stable, provided a sufficient number of steps has been performed). This cell must be U, and we can also determine the type of many other nearby cells, as shown: **************** ****ULR......... ....DULR........ .....DULR....... etc... (asterisks denote stable cells, dots denote unknown cells).The same pattern must continue in diagonal until the border of the grid is reached. But this is impossible because there's no way to tile the cells above that diagonal using dominos (if you color them like a chessboard, the number of black cells and the number of white cells would be different).
 » 3 years ago, # |   0 Even after getting good rank my rating won't go up just because there were 3000 people in the contest. Bad day!!!!
•  » » 3 years ago, # ^ |   +12 The fact that you got a good rank was because there were only 3000 people , if there were more people it would proportionally increase :P
•  » » 3 years ago, # ^ |   +10 roz shankar bhagwaan ko ek lota jal chadao, rating badhegi bacha! bum bum bhole!
 » 3 years ago, # | ← Rev. 2 →   0 Div2E TL on 33 testReplace map with unordered_mapAcceptedJust why....
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 I passed with map,maybe your code is ...
•  » » 3 years ago, # ^ |   0 me either :( and I wonder why map<> got TLE though it takes N * M * 2 * log2(N) which is less than 10^8
•  » » » 3 years ago, # ^ |   +5 map<> have log2(N) comparison. But 1 comporation for string = lenght. Your solution have O(N*M**Log2(N)*len). It is a lot.
•  » » » » 3 years ago, # ^ |   0 So I converted XOR OR AND to each 0, 1, 2 but still got TLE.http://codeforces.com/contest/779/submission/25049704
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +4 No, he is referring to the variable name you use as key for the map!You can use int IDs instead of string names to get very low runtime.
•  » » » » » » 3 years ago, # ^ |   0 I understood. thanks!
•  » » » » » » 3 years ago, # ^ |   0 Why is that so? For strings map checks for complete length thats why 10*log2(N) instead of log2(N) in integer?
•  » » » » » » » 3 years ago, # ^ |   +3 Yes, map is a BST, so it bases on comparisons, and string comparison is O(string size)
•  » » 3 years ago, # ^ | ← Rev. 7 →   0 unordered_map is O(1)(instead of O(log n) ) on avg. maybe it is crucial here
•  » » » 3 years ago, # ^ |   +3 Actually he is saying map<> got TLE and unordered_map got AC.
•  » » » » 3 years ago, # ^ |   0 sorry for the misunderstanding there.
 » 3 years ago, # | ← Rev. 2 →   0 -removed
 » 3 years ago, # |   +29 Div2 round was a race to see who types faster =(
•  » » 3 years ago, # ^ |   +3 100 % true. The harder part of problem E was processing the input Strings
•  » » 3 years ago, # ^ |   +3 and who reads faster
 » 3 years ago, # |   +12 Amazing problemset.
•  » » 3 years ago, # ^ |   -22 Here, take my downvote
 » 3 years ago, # | ← Rev. 3 →   +34 At problem div1E, is 47th test particular in any way? I am getting WA on it with an answer pretty close to the expected one...it must be something special about (47 is magical, isn't it:)) ) because I passed 46 tests and the solution makes sense.LE: I found a test that I was failing and now I have AC. So, if at any time, there is anyone in need of a test that might have some similarities with 47th test (or of a strong and really small test as it proved itself to be), here it is: 1 2 9 99 4 1 0 0 0 0 0 0 0 0 The answer should be 14, but my almost perfect program was returning 13
 » 3 years ago, # |   +9 This is the first time I solved 4 and I'm getting my ratings reduced :(
•  » » 3 years ago, # ^ |   0 Same here :(
 » 3 years ago, # |   +3 For div2-F/div1-C I saw a few submissions using dsu on tree technique.Can someone please explain the approach briefly.
•  » » 3 years ago, # ^ |   +9 I used the same and I've explained it here.
•  » » » 3 years ago, # ^ |   0 Cool..Thanks.
 » 3 years ago, # |   0 Africa > all
 » 3 years ago, # |   +7 Can someone prove complexity of this solution? 25040913
•  » » 3 years ago, # ^ | ← Rev. 2 →   -40 So let's prove asymptotic O(26 * n). 2 vertex have merged, so they won't be merge again. So my solution works 26 * O(count of merges).
•  » » » 3 years ago, # ^ |   +10 For each level O(N) merges, not?
•  » » » » 3 years ago, # ^ |   +5 for each level O(len(h)), sum(len(h)) = n
•  » » » » » 3 years ago, # ^ | ← Rev. 4 →   +28 Solution complexity is , right?And check(i) complexity is , right?And dfs(i) complexity is , right?So, depth is O(N). Then  =  N.  =  ,Since depth  =  O(N), solution complexity is UPD: I think that this piece of code in dfs reduces depth to log2(N) if (v.size() < 2) return 0; If there insted of this if will be this one : if(v.empty()) return 0; // v.size() < 1 apparently your code will take TLESo I think that complexity of your solution is . Isn't it?
•  » » » » » » 3 years ago, # ^ | ← Rev. 4 →   0 f(n) — complexity of sum dfs with n nodes. m <= 26, sum(s_i, i <= m) = n — 1, f(n) = max(sum(f(s_i)) + m * min(s_i)) if (m = 1) f(n) = 1let's prove f(n) = n log2 nif (max(s_i) <= n / 2): sum(f(s_i) < n ((log2 n) — 1) m * min(s_i) <= n f(n) <= n log2 n else: if m > 2, when we can found f'(n), that using m <= 2 and f'(n) more than f(n) so we need to prove, that (g(n) = a log a + b log b + min(a, b) * 2) g(n) = n log2 n. I didn't prove last step, but i checked it for n <= 1e5 and it is working
•  » » » » » » » 3 years ago, # ^ |   +18 Idea of your solution is: "merge subtrees of each vertex". Due to if (v.size() < 2) return 0; it works like a well known technique, when we return set in dfs and merge smaller set to larger, and in your case it merges smaller subtree to larger. So it does O(NlogN) operations of merging single element, and in your implementation it is done by dfs, for each iteration of which you create 26 vectors and in total it works O(NAlogN).In worst case (binary tree) you do more then 200N calls of dfs(): http://ideone.com/ngO6lG
•  » » » » » » » » 3 years ago, # ^ |   -10
 » 3 years ago, # |   -15 Can some please explain how to approach problem E of DIV 2 ?
•  » » 3 years ago, # ^ |   0 For bitwise operations (like AND, OR and XOR), this sort of optimization problem can be solved independently for each bit. Just evaluate and sum all variables for all (two) possible choices for bit i.
•  » » » 3 years ago, # ^ |   0 to calculate sum means to maximize the sum , mth bit of sum should be 1 , and to minimize the sum mth bit should be zero ?
•  » » » » 3 years ago, # ^ |   0 No, I mean the sum of the i-th bit for all variables. If the variables have values 0xf, 0x7 and 0xd, then sum(0) = 1+1+1 = 3, sum(1) = 1+1+0 = 2, sum(2) = 1+1+1 = 3 and sum(3) = 1+0+1 = 2. Now consider only sum(i). Let a = sum(i) when choosing the i-th bit of '?' as 0 and b = sum(i) when choosing the i-th bit of '?' as 1. Choose 1 for the minimum only if b < a. Choose 1 for the maximum only if b > a.
•  » » » » » 3 years ago, # ^ |   0 Didn't get this part Let a = sum(i) when choosing the i-th bit of '?' as 0 and b = sum(i) when choosing the i-th bit of '?' as 1. Choose 1 for the minimum only if b < a. Choose 1 for the maximum only if b > a. Could you please explain why you are doing this ?
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +4 Simulate the process taking ? as 0, the number of 1's is a. Do the same taking ? as 1, the number of 1's is b. Choose 1 for the minimum only if b < a. Choose 1 for the maximum only if b > a. Do this for all bits.
•  » » » » » » » 3 years ago, # ^ |   0 Thanks tfg
•  » » » » » » 3 years ago, # ^ | ← Rev. 5 →   +1 Remember that where xj, i is the i-th bit of the j-th number. Then . So minimizing/maximizing is the same as minimizing/maximizing for all i. Since bitwise operations do not have carry-in or carry-out (they're bitwise!!!), we can evaluate the i-th bit for all variables (xj, i for all j) for both choices of a bit (0 and 1) and minimize/maximize for each i independently. This is why I do what I'm doing in the part you didn't get!Edit: And sum(i) = .
•  » » » » » » » 3 years ago, # ^ |   +3 Thanks pimenta
•  » » » » » » » » 3 years ago, # ^ |   -11
 » 3 years ago, # |   0 Can someone tell me why I got WA on the contest 25046285 and why I needed to getline() one extra line?
•  » » 3 years ago, # ^ |   +5
•  » » » 3 years ago, # ^ |   0 Thanks for reply. can you explane me problem with input ? I will change my code to get AC easily.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 getline() takes input till end of line character. If you have input2 2abcdefIf you do cin>>a>>b and then getline(), you are actually taking empty string input terminated by EOL character of 1st line, not the 2nd.If you want to take line input n times, you should docin>>a>>bgetline(cin, str)for(i=0;i
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thanks I understood story about getline(), but again I am not sure about WA, actually for me it looks that our inputs are same. Diversity added onlyonr getchar more and it changes result. I understood it is for new line, but again I am readin n+1 lines.
 » 3 years ago, # | ← Rev. 3 →   0 Hello! I tried to solve problem C-Div2 using C++ by sorting the objects by their a-b value. The complexity should be O(N*logN). I tried both sort from
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 A code is usually nice to post here, if you're expecting help :) The idea is correct, though. One of the common mistakes you might have, ensure that your comparator to sort returns FALSE on equal objects.
•  » » » 3 years ago, # ^ |   0 Sorry, you're right. Here is a link to a my last submitted code that got TLE on pretest 8: http://pastebin.com/ZkrnPpXG.I think my cmp function makes sort skip swapping the current pair if they're equal by returning 1. Is that ok?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +1 https://en.wikipedia.org/wiki/Weak_ordering Here, you may want to read this for better understanding) In short, that's not ok, replace '>' with '>=' to avoid TLE)P.S. Also, seems to me your solution won't work when n == k, your first cycle (after sorting) would go out of array bounds.
•  » » » » 3 years ago, # ^ |   +1 Or just do like this:bool cmp_a(obiect x, obiect y) { return x.a — x.b < y.a — y.b; }
•  » » » » » 3 years ago, # ^ |   0 Thank you very much!
 » 3 years ago, # |   +6 I really like this round. I think Div.2 A has a little difficult, but B and C are easy. And my classmate FizzyDavid (Codeforces.com/profile/FizzyDavid) is Div.1 rank 7 and he becomes red. My rate also has a little rise! Congratulation to him!-- Sorry, I am a Chinese, so my English isn't good. Sorry for my bad English!
 » 3 years ago, # |   +17 Will editorials be published for this one?
 » 3 years ago, # |   0 While this is not a huge concern in competitive programming, is there a straight forward way to read a line of input into a vector/array in C++? (Just like foo = input.split() in python)
•  » » 3 years ago, # ^ |   +6 I don't think there's a very simple way.I usually do this: char tmp[1000111]; gets(tmp); stringstream ss(tmp); vector v; int u; while (ss >> u) v.push_back(u); 
•  » » » 3 years ago, # ^ |   0 I am also using stringstream for the task, but feeding the string back into a stream after reading it seems to be unnecessary intuitively. :/(Is there a less "simple" way, but we can feed it straight into the stringstream?)
•  » » 3 years ago, # ^ |   0 string s; getline(cin, s); should just work, since in most cases string works just like a vectorHowever, be careful when using this method: // Input: // 5 // abc int n; cin >> n; string s; getline(cin, s); // here s would be "" 
•  » » » 3 years ago, # ^ |   0 But getline only take cares of a delimiter, if there is an uncertain amount of spaces in a line then I can't split them without using other methods, can I? (For example, div2E)
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +3 In the div2E problem it's enough cin and cout to read the input properly. (http://codeforces.com/contest/779/submission/25044527)
 » 3 years ago, # |   0 Anybody solved Div2B with DP ? :P25035817
 » 3 years ago, # |   0 Can anyone help me figure out what I am doing wrong for div2E / div1A ?submissionI'm trying a simple binary search on a, coupled with a linear time check to see if p is part of t. It fails test 7.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 shoud be left = mid and right = mid not mid+1 and mid-1 int case left = 2 right = 3 => mid = 2 and after that right = 1
 » 3 years ago, # | ← Rev. 2 →   0 Why the first one gave runtime error but second passed? 25061791 25061827
•  » » 3 years ago, # ^ |   0 In first solution you use comparator which is wrong. It should not return true for cmp(a, a). Compare is used as a function object which returns true if the first argument is less than the second, and false otherwise.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 thanx ,but what if i want to return true for comp(a,a)?
 » 3 years ago, # |   0 waiting for edutorial~ brute force for F seems available- -but why?
•  » » 3 years ago, # ^ |   0 If you merge always merging the smaller subtrees into the largest one, the complexity will be O(n*logn*number of characters) as said here: http://codeforces.com/blog/entry/50658?#comment-346232 The proof is something like: You have a subtree of size 1, to use it on the merge you need some subtree of size at least 1, now you got size at least 2. Do the same, now you got 4... It's clear that you'll use some node at most logn times.
•  » » » 3 years ago, # ^ |   0 get it, thanks~
 » 3 years ago, # |   +40 where can I get editorials to div 1 problems?
 » 3 years ago, # | ← Rev. 2 →   0 Can somebody explain 402 D div2 in laymen trms with some test case or proper approach?
•  » » 3 years ago, # ^ |   +1 Notice that if you take out k letters from the string and you can still form the other word, then, if you take out less than k letters from the string, you can still form the other word. Then, you could see what happens if you take 1, 2, 3, etc. letters from the original string and see if even without those letters, you can form the other word. Of course, this is too slow to pass. Then, we have to binary search the amount of letters we can take, while being able to form the second string. For each length, evaluate if the original string minus the first k indexes still contains the objective string. If it does, you can take out more indexes. Else, you must take less indexes. My submission: 25066942
 » 3 years ago, # |   -8 I'm still waiting for the editorial.
 » 3 years ago, # |   0 My submissions did not get judged by system test but got rank-changed. I register late in the extra registration after contest start. Is this an intended system behavior or a bug?
•  » » 3 years ago, # ^ |   0 This does seem like a bug. I have joined in on extra registration before and rest of it is completely normal, Post Tests should have run for your submissions.
 » 3 years ago, # |   -34 it should be unrated
•  » » 3 years ago, # ^ |   0 Why?
 » 3 years ago, # |   +9 Why haven't we got the editorials till now ?? They should have been uploaded by now :)
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   0 I thought the round was held without any announcement :(
•  » » 3 years ago, # ^ |   -10
 » 3 years ago, # | ← Rev. 2 →   0 .
 » 3 years ago, # | ← Rev. 5 →   0 Sorry I mistake
 » 3 years ago, # |   0 779C — Dishonest Sellers why i need to sort with respect to a[i]-b[i] ? what is the proof ?
 » 2 years ago, # |   0 Can someone please explain the statement for Div1 C? Is it necessary that after eliminating the pth letter all words to be different? So that the language will have the same amount of words?