### hitman623's blog

By hitman623, 5 months ago, ,

Hello Codeforces!

I would like to invite you to Manthan, Codefest'19, which will take place on Sunday, August 25, 2019 at 8:05 PM IST. This is a combined Div. 1 + Div. 2 round and is rated for participants from both divisions.

The Department of Computer Science and Engineering, IIT (BHU) is conducting Codefest from 23rd August — 25th August. Manthan, the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules.

All problems in this round were created and prepared by drastogi21, _shanky, enigma27, navpun31, KAN and me (hitman623).

A lot of thanks to KAN, 300iq, V--gLaSsH0ldEr593--V, opukittpceno_hhr, Rox for the testing and valuable comments, and to MikeMirzayanov for the awesome Codeforces and Polygon platforms!

#### Prizes -

• 1st place — INR 25,000

• 2nd place — INR 18,000

• 3rd place — INR 12,000

• 1st place in India — INR 6,000

• 1st place in IIT(BHU) — INR 3,000

• 1st place among freshers (1st/2nd Year) of IIT(BHU) — INR 1,000

• Codeforces T-shirts to the participants who will be the first to solve each problem.

Participants will be offered 8 problems and 2 hours to solve them. As usual, the scoring distribution will be announced later.

Hope you guys enjoy the contest! See you on the leaderboard!

UPD: The scoring is 500 — 1000 — 1500 — 2000 — 2250 — 2500 — 3000 — 3750

UPD: The contest has ended. Congratulations to the winners.

1. tourist

2. Um_nik

3. wxhtxdy

First place in India: cerberus97

Following are the participants who were the first to solve each problem and have won a Codeforces T-shirt. Congrats!

A. IgorI

C. icecuber

D. ILoLy

E. nocriz

F. GoGooLi

G. wxhtxdy

H. tourist

UPD: We decided to give the 8th T-shirt to IgorI for problem A. Congrats!

The editorial has been published.

Hope to see you next year!

• +661

 » 5 months ago, # |   -56 Finally some Indian Contest ..waited for it ..hoping for great problems.. last one was great
 » 5 months ago, # |   -131 Waited for the whole year! Hope the legacy of greatness continues!
•  » » 5 months ago, # ^ |   +172 Lol, waited the whole year and didn't take part ....
•  » » » 5 months ago, # ^ |   -32 Well, Such comments are only supposed to get upvotes. I am glad they both got downvoted.
•  » » » » 5 months ago, # ^ |   0 Yeah lol, they "both" got downvoted.
 » 5 months ago, # | ← Rev. 3 →   +6 Probably tourist will win the prize for 1st place ...
•  » » 5 months ago, # ^ |   -19 Probably? :)
•  » » » 5 months ago, # ^ |   +1 Maby he doesn’t participate!
•  » » » » 5 months ago, # ^ | ← Rev. 5 →   +1 MOOONI ,he has been participating in Manthan since last two years :)
•  » » » » » 5 months ago, # ^ |   -9 Maybe there will be surprises
•  » » » 5 months ago, # ^ |   +7 It should be "must"!
•  » » 5 months ago, # ^ |   +9 You nailed it
 » 5 months ago, # |   -13 The Legends battle are coming
 » 5 months ago, # |   -49 Hope that I'll become a candidate master after this round! Div.1 + Div.2 is a great chance to promote my rating and I only need +8 rating to become a candidate master :D. And also, good luck to everyone!
•  » » 5 months ago, # ^ |   -41 Hope I'll become a grandmaster I need 65 rating and it is kinda impossible
•  » » » 5 months ago, # ^ |   -40 Mr. Grandmaster orz
•  » » » 5 months ago, # ^ |   -42 Mr. Grandmaster orz
•  » » » » 5 months ago, # ^ |   0
•  » » » » » 5 months ago, # ^ |   -27 cfantasy wowowo
•  » » » » » 5 months ago, # ^ |   -22 What is wrong with orz?
•  » » » » » » 5 months ago, # ^ |   -22 Nothing. Let's just orz. orz grandmaster who has 4 times the rating as me
•  » » » » » » 5 months ago, # ^ |   +30 If people spam something too much, it will become annoying. galaxybrain.jpg
•  » » 5 months ago, # ^ |   +18 I don't understand. Why this kind of comments should be downvoted...
•  » » 5 months ago, # ^ |   -30 Glad your comment wasn't welcomed. Please stop this shit. Nobody cares what you want to become and what you actually become. So please.
 » 5 months ago, # |   +150 "Codeforces T-shirts to the participants who will be the first to solve each problem.", well, this gonna be interesting
•  » » 5 months ago, # ^ | ← Rev. 3 →   -20 Well yes!! I wish everyone to get codeforces t-shirts. but everyone will not succeed because there are not so many tasks in comparison with us)))
•  » » 5 months ago, # ^ |   +45 Yes,it will.And I think it doesn't matter if you do a great job or win a T-shirt or not,I think thefeeling during the contest is the most exciting thing！ And good luck to all of you!
 » 5 months ago, # |   +13 Wow, an awesome contest ^_^
 » 5 months ago, # |   +25 1st place is constant for tomorrow's contest if he participates.
•  » » 5 months ago, # ^ |   +3 Nothing is already played! wait for the leaderboard.
 » 5 months ago, # |   +15 8 problems, 4 for div 2, 4 for div 1 or another?Sorry for my bad english
•  » » 5 months ago, # ^ |   +33 There are 8 problems for all participants. Div1 + Div2 means that everybody can participate. For example above 2100 can't participate in Div2. or the same for above 1600 and Div3.
•  » » » 5 months ago, # ^ |   0 Thank you very much
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 it mean that the contest for all participants. I think if you can achieved rank 1 in this contest, you will be +800 rating =)) good luck for u ^^
•  » » » 5 months ago, # ^ |   0 Thank you and good luck
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   -8 Fan one piece :v
•  » » » » » 5 months ago, # ^ |   0 Please comment in English or Russian
•  » » » 5 months ago, # ^ |   0 I practiced hard in the last couple of months. not 800+ but a pupil rating will boost my confidence even higher.
•  » » » » 5 months ago, # ^ |   0 It must be above all a fun game where you want to be the best player. Good luck to you.
 » 5 months ago, # | ← Rev. 7 →   -27
•  » » 5 months ago, # ^ |   0 Yeah bro!
 » 5 months ago, # | ← Rev. 2 →   -7 I'm disappointed they scraped my e-mail from my profile and decided to send me spam.It is an old e-mail, meaning that they did it some time ago and not just now near this contest, and I've never registered in their site.The closest I got was participating in Codefest '18, here in Codeforces, but at that time, I used a different e-mail (a third one).PS.: And even if they did it at that time (they didn't), nowhere it says they would send e-mails to registered participants.
 » 5 months ago, # | ← Rev. 3 →   +30 Manthan, Codefest 18 (rated, Div. 1 + Div. 2) The Previous Manthan codefest contest .
•  » » 5 months ago, # ^ |   -8 last?
•  » » » 5 months ago, # ^ |   +4 previous*
 » 5 months ago, # |   +5 8 problems for 2 hours?? Isn't that too tight?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +23 It's combined round (Div. 1 + Div. 2), the high rated coders will be bored if they solved all the problems quickly. you can see that tourist solved all the 8 problems of Good Bye 2018 in less than 2 hours, also few contestants solved all the 8 problems of last year Manthan, Codefest 18 in less than 2 hours.
•  » » » 5 months ago, # ^ |   0 i think tourist will continue to win
 » 5 months ago, # |   0 I hope that I will raise my rating to 1500-1600
 » 5 months ago, # | ← Rev. 2 →   +17 Wow.... Such a big prize$出题人家里有矿_{泉水}$
 » 5 months ago, # |   +6 Any update on scoring distribution?
 » 5 months ago, # |   -49 Downvote kar karke iss comment ki gaand mardo....
 » 5 months ago, # |   +1 I relize that lots of people use anime avatar like me ^______________^
•  » » 5 months ago, # ^ |   0 Wow, it's so InTeReStInG !1!! (No)
 » 5 months ago, # |   0 None of the other severs (m1.codeforces.com), (m2.codeforces.com), (m3.codeforces.com) seem to have the contest added in there?!
 » 5 months ago, # |   0 Have been participating regularly for the past 2 editions of this contest and had lots of fun.Hope everyone has fun this time too :)
 » 5 months ago, # |   0 not able to register before 5 minutes of contest... why??
 » 5 months ago, # |   +1 can someone submit? it keeps loading
 » 5 months ago, # |   0 It's legendary grandmaster battle. I can't wait to see that. All top 3 highest CF rating have already register, who will win???
•  » » 5 months ago, # ^ |   0 let's guess who will win .. tourist ofcourse
•  » » » 5 months ago, # ^ |   0 He is on 1st place =))
 » 5 months ago, # |   0 R.I.P queue
 » 5 months ago, # |   0 VERY long queue
 » 5 months ago, # |   0 What was the pattern for 1208C - Magic Grid?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +2 Use subsquares 4x4 of numbers 0-15 MOD 16 like (0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15) — it has zero XORs and prefixes are repeated 4 times, thus their XOR is also 0.
•  » » » 5 months ago, # ^ |   0 Very nice solution bro, I also thought about that thing, I saw with n=4 and n=8 we can easily solve the problem, just write sequence 0..(n^2-1) from left to right and from top to bottom, but then I couldnt figure out how to use them for another multiple of 4 numbers and your solution helps me a lot. Thanks again!!!
•  » » 5 months ago, # ^ |   0 0 1 2 3__________16 17 18 19 4 5 6 7__________20 21 22 23 8 9 10 11________24 25 26 27 12 13 14 15______28 29 30 31 32 33 34 35_____48 49 50 51 36 37 38 39_____52 53 54 55 40 41 42 43_____56 57 58 59 44 45 46 47_____60 61 62 63
•  » » 5 months ago, # ^ |   +47
•  » » » 5 months ago, # ^ |   +5 Why not doing it in a nice order?  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Everyone is giving example of 8x8, how to extend this to 12x12?Edit: To extend, order doesnt matter, just place those new 4x4 matrices anywhere. All will be 0. Good god.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +1 It is simple: every 4x4 subsquare has 0 XORs, so you can arrange them in any way.
•  » » » » » 5 months ago, # ^ |   0 Yeah, just realized.
 » 5 months ago, # | ← Rev. 2 →   -36 B question was good. Took more than 1 and half hour to understand it what's it trying to say and implement it.Thanks for this contest IIT BHU :) . Cheers!
•  » » 5 months ago, # ^ |   0 It also took me 1 and a half hour. I am not even sure whether it is correct or not. Let's see the system testing results.
 » 5 months ago, # |   +23 How to solve C, it seems much harder than D and E
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Fill that array in increments of 4 like 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15This way xor will always be zero of all rows and columns.
•  » » » 5 months ago, # ^ |   -8 not necessarily zero. When n%8 equals 0 then it will be zero else it will be 13.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Some one here said that B was harder than C. And you say that C is harder than D and E. It took me more than one and a half hours to get the B pretests correct. I am thinking whether I should I have skipped B.
 » 5 months ago, # |   +1 tourist achieved top 1 is really very normal =))
 » 5 months ago, # |   0 How to solve C? I feel D was easier than C :(((
•  » » 5 months ago, # ^ |   0 Oh dear, I got bug at D. Dunno whether my C is correct. Btw I use the fact that I can construct a grid for numbers 0->15, then I could construct numbers for 16k->16k+15
•  » » 5 months ago, # ^ |   +3 U can find a pattern that if you break the given nxn matrix into 4x4 matrices with increasing values (For ex: 0 to 15, 16 to 31 etc) , you can make all the rows and columns have xor sum = 0.Find my submission here :)
•  » » » 5 months ago, # ^ |   0 nice trick, thanks
•  » » » » 5 months ago, # ^ |   0 Could you please share your idea for D? :)
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Mine is Nlog^2(N)basically binary search + segment treeI start filling the answer array in reverse order, Binary search on all feasible values to check the following condition if array[mid]+query(0,mid-1) == mid(mid-1)/2, then mid is at current position else array[mid]+query(0,mid-1) >= mid(mid-1)/2, then lo=mid+1 else hi=mid-1 I used pbds for convenience. thats not needed.
•  » » » 5 months ago, # ^ |   0 How did you find this pattern ?
•  » » » » 5 months ago, # ^ |   +3 They had emphasized that n is a multiple of 4. So I wrote down the binary representation of 0 to 3 ( i.e first 4 numbers, and realized their xor was 0).That was the beginning of the idea, and developed the pattern.
•  » » » » » 5 months ago, # ^ |   0 Great! :D
•  » » 5 months ago, # ^ |   +3 This is my approach:Divide the whole matrix into 4 * 4 matrices. Then fill every matrix with slight modification of a valid answer for a 4 * 4 matrix. I used the result of test case 1 of the problem statement. Keep a variable that tells us the number of matrices that has been processed. Left shift counter variable by 4 and then perform bitwise OR operation with the corresponding number of the initial matrix while assigning.Will it be correct? Yes, because the XOR of each row and column of every 4 * 4 matrix will be the same. So, if you use test case 1, then the XOR of each row and column of the whole matrix will be 13 or 0.Will any number repeat? No, because we are using counter variable. Every number has 4 initial bits with 2 ^ 4 possible combinations. These are covered by the initial matrix. We just need to cover the extra bits. The counter gives us new combinations of the extra bits, starting from the lowest. By performing bitwise OR, we are reaching each bitwise combination. So, we will hit each number once.My submission can be found here.
 » 5 months ago, # |   +3 How to solve D ?
•  » » 5 months ago, # ^ |   +10 I did it with a lazy segment tree, but there seems to be a way to do it with just a regular segtree/fenwick tree. In the sequence you get, the last 0 is always the 1 in the original. If you imagine that you remove the 1 you found and subtract 1 from every item after that you would get a similar sequence for 2..N. Then you find the last zero again, which now is the 2 and you subtract 2 from everything after etc. You use a lazy min segment tree to find the last zero (order by value and index) and to do the range subtractions.
•  » » » 5 months ago, # ^ |   +6 I thought of this idea last 5 mins before contest end, indeed can't implement it.Thank you anyway :)
•  » » » » 5 months ago, # ^ |   +6 Pretty much the same. Thought of it 15 mins before, but min segment tree + lazy, gave up there itself >.<
•  » » » » » 5 months ago, # ^ |   +3 I also got the solution quite late, but I copy pasted the segment tree from kactl. It's a really nice repo with lots of standard CP things.
•  » » 5 months ago, # ^ | ← Rev. 6 →   0 SpoilerTry to recover the answer from the end of the array.. SpoilerWhen $n\ =\ 4$, you can notice that when the last element of the given array is 0, 1, 3, 6, then the last element of the answer array is 1, 2, 3, 4. Depending on this info, the corresponding (value of the last element of the given array, value of the last element of the answer array) for prefixes change. Try to draw and think about that -- it's pretty easy from this point. SpoilerProbably, if you got here, you want to know how to compute that -- use Fenwick tree with range update and point query. You can search for an article on geeksforgeeks and check tourist's solution.
•  » » » 5 months ago, # ^ |   0 Oh dear, that's so simple. I don't know I have done.
•  » » » 5 months ago, # ^ |   0 Fenwick tree with range query and point update I think
 » 5 months ago, # |   +3 most of the WA10 because of something like this :
•  » » 5 months ago, # ^ |   0 1 2 3 3 10 11 3 12 13 14 . I know where my solution was failing , but couldn't solve it . I have seen some people solve it using bs . How ? .
•  » » » 5 months ago, # ^ |   0 just solve it from left and once again form right and print the minimum of these answers bs ?! hmmm...
•  » » » » 5 months ago, # ^ |   0 I think i was also doing the same . use a set and iterate array from left and if any element is previously present in set mark the start index , otherwise insert the current element in the set . Did the same and mark the end index , keeping in mind that end > start . Final answer was end-start+1 . But I couldn't handle the case which i mentioned you earlier . Here is my submission for that .
•  » » 5 months ago, # ^ |   0 My code passes this but fails on system test 50. 59469362
 » 5 months ago, # |   +3 What is test #5 of D?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 // 1 4 3 240 1 1 1
•  » » » 5 months ago, # ^ |   0 Are you sure? I failed on pretest 5 but my code gives correct answer here.
•  » » » 5 months ago, # ^ |   0 no it could not be that. My code gives the correct answer
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 //9 5 3 4 1 6 2 8 790 0 0 3 0 13 1 21 21
 » 5 months ago, # |   -8 I was able to solve C but couldn't solve B. :( Was B more tough than it is supposed to be??
 » 5 months ago, # |   +59 Thanks for the short statements
 » 5 months ago, # |   -15 I must be crazy. I think the problem should be like ABEDCFGH...
 » 5 months ago, # |   0 Is there any way to solve D without converting it into a Segment tree RMQ problem? I saw the number of submissions and thought I probably need to think simpler.
•  » » 5 months ago, # ^ |   0 You can use fenwick tree with range update and point query.
•  » » 5 months ago, # ^ |   0 I only used std::priority_queue.
•  » » » 5 months ago, # ^ |   0 Could you explain your solution?
•  » » » » 5 months ago, # ^ |   0 I break each range into two “operations” one is insertion and another one is deletion. Then I sort the operations in ascending order of position to solve it offline
•  » » » » » 5 months ago, # ^ |   0 Can it be done offline? Don't you need to update every range to know the next range to be updated?
•  » » » » » » 5 months ago, # ^ |   0 I divided the array into 2k non overlapping interval, where k is the width of the bar. So we can update them in any order
 » 5 months ago, # | ← Rev. 2 →   +12 When in the last 20 minutes of the contest you start doing problem D but in the last 9 seconds you submit it without any tests, because you just finished coding it, and you misstyped a -=, instead of typing +=. I've neve felt this bad before ;(PS: Submission during the contest: https://codeforces.com/contest/1208/submission/59484539Submission after the contest, after changing the signal: https://codeforces.com/contest/1208/submission/59486030
 » 5 months ago, # |   +5 hard contest for me but I enjoy it very much. Thanks :)
 » 5 months ago, # |   +3 How to solve E in time? I had a made a sparse table solution and then just iterated over all of the columns but I couldn't figure out the final optimization. At the end I tried to use a lazy seg tree to propogate the maximum over all columns where the the array can take all of it's values. Is this the right approach?
 » 5 months ago, # | ← Rev. 2 →   -35 B and D are not good problems. C is nice
 » 5 months ago, # |   +81 I love how Tourist was able to get 500 on A (submision time 52s) :-)
•  » » 5 months ago, # ^ |   -14 Keep up to date (hipozhor)
•  » » 5 months ago, # ^ |   +68 3 miniutes for D and 2 minutes for C is unbelieveable
•  » » 5 months ago, # ^ |   +118 Guys, I know what happened. tourist obviously cheated. See for yourself:How can he start coding at 17:33:16 if the contest started at 17:35:00? I knew something wasn't right about him, but now he gave himself away!I would disqualify everybody whose handle starts with t as a warning.
•  » » » 5 months ago, # ^ |   -7 majk Come on. It can be possible that he might have created pre template file for A problem before the contest. We all do a little preparation.
•  » » » » 5 months ago, # ^ |   +74 How would he know there's a problem A? You're only making this worse.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   -10 I think there is no point for tourist to cheat on problem A.
 » 5 months ago, # |   +72 The best utilization of last ( extra ) five minutes : tourist submitting H at 2:03
 » 5 months ago, # |   +1 How to solve 1208E - Let Them Slide?
 » 5 months ago, # |   +1 Can someone give a quick editorial of B.
•  » » 5 months ago, # ^ |   0 You can delete either: some prefix some suffix something in the middle You will be left with (respectively): some suffix some prefix some prefix + some suffix Basically, (1) and (2) are the same as (3) if you assume that there is an empty prefix/suffix. So, what you can try to do is for each prefix (empty, too) find the largest suffix satisfying the conditions -- what is left between them is exactly what you delete, take the minimum of all such gaps.
•  » » 5 months ago, # ^ |   0 The simplest way, according to the given constraints would be to add each element in the array to a set. Then for every index i starting from 0, we traverse j left to right from i, generating every subarray starting at i, and trying to remove each element from the set and check if size of the set at any point is N- (j-i+1). We stop the first time it happens and we've found the smallest subarray starting at i. Then we increment i again, but before doing that make sure you add back the i'th element to the set. It will be O(N^2 lgN) There's also an O(N) solution by the way, that I used.
•  » » » 5 months ago, # ^ |   0 N2logn is giving TLE
•  » » » » 5 months ago, # ^ |   0 My solution passed with 358 ms having the same complexity :)
•  » » » » 5 months ago, # ^ |   0 My solution got Accepted with the $O(n^2\ log\ n)$ complexity too
•  » » » » 5 months ago, # ^ |   0 Yours is a $O(n^2 log^2 n)$ I think.
•  » » » 5 months ago, # ^ |   0 I also got a TLE in n^2logn.My submission
•  » » » » 5 months ago, # ^ |   0 You are using a $map$ inside the binary search. That would make it $O(n^2 log^2n)$
•  » » 5 months ago, # ^ |   0 you can try two pointers to solve that...i am not sure,but I have passed the pretest
 » 5 months ago, # |   +13 Okay, why lot of system test fail on B?
 » 5 months ago, # |   +26 I solved C with something really easy: I print all even numbers first then I print what is left. For example for n=4 my output will be : 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15 
•  » » 5 months ago, # ^ |   +1 Incredible.
•  » » 5 months ago, # ^ |   +21 Definitely the best solution here :D. It is also easy to prove that it is correct — lines have XOR of 0 trivially (split them by 4) and every consecutive even-odd pair in each column have XOR of 1. There is even number of such pairs, so the total XOR is also 0.
•  » » 5 months ago, # ^ |   0 How did you came up with it ?
 » 5 months ago, # |   -8 so sad I thought C xor will be zero because it looked impossible to guess some number but didn't know how :'(
•  » » 5 months ago, # ^ |   +8 you can solve it with xor equals zero, just look at my comment
 » 5 months ago, # |   +183 At least 3 persons on my friend list who got F accepted fail this test: 3 2 4 2 Please look into this.
•  » » 5 months ago, # ^ |   +10 I got uphacked (59479538) by 3 0 0 1 Because I looped the number to or with up to the last number, instead of to the third-to-last. The tests were definitely pretty weak :P
 » 5 months ago, # |   +9 why codeforces don't compare codes like this 59482093 and this 59481769tihs is not fare
 » 5 months ago, # |   +2 Can we solve B using Binary Search?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 Yes. I solved it using binary search. Code Search space is the answer range i.e. [0,n]. isValid function checks if it's possible to delete 'mid' number of values such that rest of them are distinct. I used map to store the values and their frequencies in the 'undeleted' array. If the size of map is n-mid for some undeleted part, it means that all the undeleted elements are distinct.
•  » » 5 months ago, # ^ |   0 I think you can.If deleting a large portion from a given position gives you a valid sequence then you can check for even smaller portion.
 » 5 months ago, # |   +1 What id test 54 for B ?
 » 5 months ago, # |   0 Guys, I've found a really nice solution for C.The Ideea is this: Put even numbers in increasing order on odd rows and odd numbers on even rows.Ex: n=4 0 2 4 6 1 3 5 7 8 10 12 14 9 11 13 15 This is 100% correct and much easyer to implement. :)
 » 5 months ago, # |   +8 How to solve F?
•  » » 5 months ago, # ^ |   +11 Could anyone explain why this solution 59478005 for F works?
•  » » 5 months ago, # ^ |   +29 My solution: We want to be able to fix a_i and compute the best (a_j&a_k) for that a_i quickly. To do so, we iterate through i from large to small, and maintain an array cnt[bit] which stores the number of elements among $a_{i+1}, a_{i+2}, ..., a_{n}$ that have bit as a submask. How to we update cnt? Note that we only need to know if cnt is >= 2 or not. Now, when we have a new element $x$ to be added, we do something like a dfs, starting by adding 1 to $cnt[x]$, and then recursing on all submasks of $x$ that are one bit away from $x$. If at any point of time we visited the same number or cnt[x]>=2, we can terminate because we know all submasks must also have cnt>=2. Thus, the complexity of updating cnt is amortized $O(n\log a_i)$. Finally, with the values of cnt you can also find the best answer for a fixed $i$ in $O(\log a_i)$ time.
•  » » » 5 months ago, # ^ |   +3 thank you a lot!!By the way is there any method which allows an update in sos dp?
 » 5 months ago, # |   +1 can you tell, where my code for B fails?My Solution
•  » » 5 months ago, # ^ |   +4 Check this test case: 8 1 2 3 4 1 6 5 4 The correct answer is 2.But your code gives 4 as the output. I guess most of the solutions got failed at system testing in these type of test cases.My solution got failed too.
•  » » » 5 months ago, # ^ |   +1 Thanks, got your point.I think we went wrong in trying to implement B in o(n).Constraints are the real insights to the problems.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Try this one: 6 3 2 5 3 1 5 
 » 5 months ago, # | ← Rev. 2 →   0 Why does solution for B in $n^2 \log^n$ give TLE? I used both binary search and sets (I know it's not the most efficient), and couldn't get it accepted. TLE on test 18. Can anyone help?$n^2\log^2n$ is roughly 43587196 ops at n=2000 which should work in under 2secs imo.Submission
•  » » 5 months ago, # ^ |   +14 You might have a miscalculation.4million*log*log is around 400 million, which might not pass because of set constant.
•  » » 5 months ago, # ^ |   +11 You took the log to the base 10. Base 2 would be more realistic and then it's already $5*10^8$, also set::insert probably has some additional constant factors.
 » 5 months ago, # | ← Rev. 2 →   +4 Can someone please point out the logic flaw in my solution for problem B?PS: Found my mistake. Thanks everyone.
•  » » 5 months ago, # ^ |   0 Same for me mine also getting wrong at testcase 54.
•  » » 5 months ago, # ^ |   0
•  » » 5 months ago, # ^ |   0 Try this one: 6 3 2 5 3 1 5 
 » 5 months ago, # | ← Rev. 4 →   -21 The countest is very difficult
 » 5 months ago, # | ← Rev. 2 →   0 I didn't leak code to anyone but I receive system's message :'(. May be this is an accident
 » 5 months ago, # |   0 My Solution for B, fails on test 54 but I don't know why? Someone please help! LinkL: https://codeforces.com/contest/1208/submission/59459333
•  » » 5 months ago, # ^ |   0 Edit: I found my mistake, Thanks
•  » » » 5 months ago, # ^ |   0 what was it? I am having the same problem....
 » 5 months ago, # |   +59 So tourist doesn't get two T-shirts? :sad:
 » 5 months ago, # |   -128 It is totally unfair to me . I have solved the second problem completely with required time complexity even than your website is showing TLE . Why? Do something otherwise it is totally waste of time for me to participate in challenges on your website
•  » » 5 months ago, # ^ |   +6 Maps are not constant complexity. Expected complexity was O(n²log(n)), not O(n²log(n)log(n))
•  » » 5 months ago, # ^ | ← Rev. 2 →   +17 The CF judge is fair to everyone. It's just because your solution is too slow. Having a solution of intended time complexity does not necessarily mean it must pass.
•  » » 5 months ago, # ^ |   +27 No one cares if you participate or not. This platform is for everyone to learn and improve. If you have done a mistake try to accept it and learn from it, instead of complaining.
 » 5 months ago, # |   +51 I was able to pass pretests with my too complicated solution for G, but I got TLE on one of the pretests during system testing. Moreover, after the contest I submitted the same code 10 times, 9 of those 10 attempts got AC. Maybe solutions should not be rerun on pretests during final testing, to prevent such disappointing situations in the future xD
 » 5 months ago, # |   +59 1179 contestants solved segment tree problem. It seems like CF is "growing up" or I am "growing down".
•  » » 5 months ago, # ^ |   0 I solved B in more than 13 minutes and solved D in less than 10 minutes.I think I need more "IQ"...
•  » » 5 months ago, # ^ |   0 I can't solve C because I'm not good at constructive problems. I think I should practise it more.
 » 5 months ago, # |   +27 tourist returned to 3700+ in 31 months.
 » 5 months ago, # |   0 Can someone tell why my code 59471606 of B problem gave wrong answer on pretest 9? It gives same output as jury's output when I run it in my system.
 » 5 months ago, # |   0 How to solve D,I don't understand the editorial ?
•  » » 5 months ago, # ^ |   +3 If the input is valid, as the problem statements says, there is always an answer and it will be unique.Let's build from the last element in the array to the first one. Also create a data structure that can query the sum of all values in range[0, r] and update a point in log. Whenever you try to put some number into the answer, it will have sum of all the other unused numbers, because they will be somewhere before it in the answer. Initially, all numbers are available. So you can do N updates like: update(i, +i).As you know the sum of all numbers before it in the array, just binary search what element have exactly the same sum as the input, then remove it from the answer like: update(i, -i).Suppose that you initially have 1, 2, 3, 4, 5. So, your data structure will be: 1, 3, 6, 10, 15.If you want to put an element with sum 6, you should put element 4 as the last one, then your data structure will look like this: 1, 3, 6, 6, 11.Keep doing this and you will end up with the answer.
•  » » » 5 months ago, # ^ |   +6 It seems a same approach with mine (and different with the editorial).However, I don't know how to deal with such condition:n=5, the sequence is 0 4 0 1 10 1 3 6 10(the last one is 2)0 1 1 4 8(the last one is 3)0 1 1 1 5Now, there are three 1 can be chosen (in fact, the third 1 is correct), and how can my program deal with such condition in appropriate complexity.
•  » » » » 5 months ago, # ^ |   0 You should always try to find the last one element that have the same sum. If the data structure is like ... 0 1 1 1 1 2 ... And you are searching for 1, just get the last 1.If you put another value except from the last, you can't build the answer.
•  » » » » » 5 months ago, # ^ |   0 Thx! I do exactly the same thing as you say and got WA on 9. However, it turned out to be that it is "long long" which made me get WA. QAQ
•  » » » » » » 5 months ago, # ^ |   0 You can also improve your answer by removing the binary search, just traversing the segment tree.If you are in a vertex searching for something with sum x, then: if left node have sum >= x, then call left vertex with x otherwise call right vertex with x - left_sum
•  » » » 5 months ago, # ^ |   0 Thanks
 » 5 months ago, # |   +54 How is it possible to solve A in 52 secs if statement loads for half a minute xD?
•  » » 5 months ago, # ^ |   -9 I believe the writers of problems couldn't have beaten tourist for the first 7 problems if they implemented the solutions from scratch.
•  » » 5 months ago, # ^ |   +22 Read the statement in 6s, write the code in 13s and submit in 3s
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 You can open problem statements much faster using m1.codeforces.com
•  » » » 5 months ago, # ^ |   0 Tried to do it, didn't help at all :P
•  » » » » 5 months ago, # ^ |   0 BTW, it took me less than 15 seconds to load the problems.
 » 5 months ago, # |   +16 Tourist is such a monster！
 » 5 months ago, # |   0 I think we should swap problem C and problem D.....
 » 5 months ago, # |   0 I tried to solve the second question using binary search on the length of segment to be removed. The pretests passed but I got TLE in the final testing. http://codeforces.com/contest/1208/submission/59462841Can someone tell me what went wrong ?
 » 5 months ago, # |   -6 why I dont see the prize for first solve of problem H in the list above while there is someone has solved this in the contest, can anyone explain this for me?
 » 5 months ago, # |   0 How to solve G? It seems like a math problem about divisors, and the AC code looks very simple. However, I did not understand the behind logic yet. Anyone can help?
•  » » 5 months ago, # ^ |   0 Have you read the editorial?
•  » » » 5 months ago, # ^ |   0 I did not notice the editorial. Now I understand. Thanks!
 » 5 months ago, # |   0 Can someone help me with the code for B problem? Here is my code: #include #define ll long long int ll n,m; ll a[4004]; // sets; mapmp; int last[4004]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; a[n+i] = a[i]; } for(int i=1;i<=2*n;i++) { last[i] = mp[a[i]]; mp[a[i]] = i; // cout<
 » 5 months ago, # |   0 Can Any one explain Problem D ??
 » 5 months ago, # |   +7 Request for future contests :: Please make large inputs downloadable
 » 5 months ago, # |   0 If you've solved problem D. And want to solve another interesting problem like this. Try Lightoj — Lining Up Students In Lightoj one need a account in case of view a problem. In case you don't have an account there you can read the problem here
 » 5 months ago, # |   -23 very good
 » 5 months ago, # | ← Rev. 2 →   -23 good
 » 5 months ago, # |   -34 asd
 » 5 months ago, # |   -35 hello my fan
 » 5 months ago, # |   -44 Codeforces is too easy to me
 » 5 months ago, # |   +3 Can I get some help to solve B...This was my code https://codeforces.com/contest/1208/submission/59474361 ...Why am I getting TLE...As much as I can see, the solution will execute 6.4*10^7 instructions at max
•  » » 5 months ago, # ^ |   +4 Operations on unordered_map are often more than 1 instruction, and the $O(n^{2}logn * map)$ will probably have a bad constant and run for longer than expected.Some improvements:The actual elements in the array don't matter, only that they're unique. Therefore, you can compress coordinates and use a boolean array (or bitset, if you really want) instead of a map. This alone should get you under TL.The binary search doesn't actually help you. Since the check function is $O(n)$ anyway, you may as well get rid of the $logn$ factor by just finding the first location, iterating from the right to r, that creates a duplicate (of course, include the elements to the left of l first and account for duplicates there)And because three is a good number, even though this isn't necessary, your loop in check skips over a lot of elements. Each continue can cost you, and it will be better to split check into two loops.
•  » » » 5 months ago, # ^ |   +8 Thanks :-)
 » 5 months ago, # |   0 Was anyone able to get AC with binary search on B ? If yes can you share your solution ?
•  » » 5 months ago, # ^ |   0
 » 5 months ago, # | ← Rev. 2 →   +14 The problems are good.
 » 5 months ago, # |   0 Hmmm. Is the difficulty point of H right???
•  » » 5 months ago, # ^ |   0 It seems to be fixed now, I've messaged Mike about this.