By Vladik, 4 years ago, translation,

Hello everyone!

27 May, 12:35 MSK new codeforces round takes place for participants from the second division. Participants from the first division can participate out of competition. Round consists from 5 problems, and you will be given 2 hours to solve them. Pay attention on round start time.

The problems will be almost the same as on Open Olympiad of Mozyr State Pedagogical University, which takes part parallel to the round. The full problem set would be in codeforces gym soon. I am also going to tell you about the Olympiad a bit later.

• The problemsetters are: me (Vladislav Vishnevski), Valery Kameko (Valerich) and Yury Shilyaev (hloya_ygrt).
• The testers are: Alex Kernozhitsky (gepardo), Arseniy Kolosov (KArs) and Ilya Klimko (klinchuh).
• The coordinator of the round was Alexey Vistyazh (netman).
• Alex Dryapko was reading the statements (sdryapko).
• And of course, the round would be impossible without Mike Mirzayanov (MikeMirzayanov), author of polygon and codeforces systems.

Thanks everyone for contribution you did to the setting of the round.

The main character of the round is Vladik, who loves to solve problems and himself.

Good luck to everyone! :)

UPD 500-1000-1500-2000-2500

UPD Editorial.

• +149

 » 4 years ago, # |   +2 Can't register. Showing "rating should be 0...1899 to register ..."
•  » » 4 years ago, # ^ |   -20 According to your profile page, your rating in not is this range.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +34 According to this post: Participants from the first division can participate out of competition.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 "Participants from the first division can participate out of competition"
 » 4 years ago, # |   +31 3 consecutive rated rounds from hloya_ygrt . Amazing.
•  » » 4 years ago, # ^ |   0 well, there was only 1 problem of his in tinkoff challenge.
 » 4 years ago, # |   +12 Is netman international grandmaster?
•  » » 4 years ago, # ^ |   +14 no
•  » » 4 years ago, # ^ |   +7 Might be they have prepared the post long back and drafted it.
•  » » 4 years ago, # ^ |   +34 Once a international grandmaster, alway a international grandmaster :P
 » 4 years ago, # |   +19 What is MSPU Olympiad 2017 ????
•  » » 4 years ago, # ^ |   +8 looks like no one knows what is MSPU !
•  » » » 4 years ago, # ^ |   +16 even google lol !!!
•  » » » 4 years ago, # ^ |   +13 looks like no one knows what is MSPU ! It's because the onsite contest is not very well-known, especially outside of Belarus. The contest is held in Mozyr, Belarus by a local university.By the way, as it's mentioned in the post, The problems will be almost the same as on Open Olympiad of Mozyr State Pedagogical University, which takes part parallel to the round.
•  » » » » 4 years ago, # ^ |   +8 ty
•  » » 4 years ago, # ^ |   +25 Well, it's more like Vladik and friends wanted to organize an onsite contest for other highschoolers from Belarus. Since it happens on-site and Vladik currently lives in Mozyr (which is a minor town in Belarus with about 100k population), the only possible venue is the local university called MSPU. So that's why is's called "MSPU Olympiad".None of problemsetters studies there (and none of then will, lol), so in other terms it has nothing to do with MSPU.You can think of it as of a mirror of an onsite contest for Belarusian highschoolers, if it's more convenient for you.
 » 4 years ago, # | ← Rev. 2 →   +15 Div 1 Users are not able to register. Update — It's fixed now.
 » 4 years ago, # |   0 Good start time , to prevent conflict between it and SnackDown Pre-elimination.
 » 4 years ago, # |   -26 Is this contest rated?
•  » » 4 years ago, # ^ |   +12 Asking the real question: Is it also rated for Div1? (Nah, probably will be fixed soon)
•  » » 4 years ago, # ^ |   -19 Why people are downvoting my comment? Did I say something wrong or unnecessary?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 I think all #codeforces_rounds are rated (if they did not say it is not) for people who are able to register so you should not ask about that every time :)
•  » » » » 4 years ago, # ^ |   -30 Not all contests are rated. I found that in previous contests. And whenever codeforces announces a contest they mention that if that contest is rated or not. But, in this post, they didn't say anything.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +6 The best way to bring down your contribution is to ask the question "Is it rated?". Most of all contests are rated, and in the announcement of the contest autors always indicate if it is unrated. Welcome to CF:)
 » 4 years ago, # |   -24 Unfortunately I am having a final exam tomorrow at contest time. I am thinking about not going to my faculty to be able to register =D
•  » » 4 years ago, # ^ |   +2 Do it bro, you can have the final exam another time so you have to register, even if the same thing happened again next year, register again and have your exam later { listen to me and say "Good Bey" to your future :) }
 » 4 years ago, # |   +3 Something wrong with registration. When I registered, I wasn't considered "out of competition".
•  » » 4 years ago, # ^ |   +69
 » 4 years ago, # |   +6 Just wanted to point out that the time link on "Codeforces Round #416 (Div. 2) has been moved to start on 27.05.2017 09:35 (UTC)." leads to The World Clock.
 » 4 years ago, # |   +12 Codeforces round, Codechef May lunchtime and snackdown pre elimination all in same day == Busy day for me :3
•  » » 4 years ago, # ^ |   +29 And AtCoder Grand Contest 015 also :'D
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 Too bad the contest starts 30 minutes after the start of this round. :(Edit: I had the time zones wrong, it's actually 30 minutes after the end of this round!
•  » » » » 4 years ago, # ^ |   0 *end of this round
•  » » » 4 years ago, # ^ |   +2 and Yandex.Algorithm round 2 also :)
 » 4 years ago, # |   +16 hopefully short statements !!!
 » 4 years ago, # | ← Rev. 3 →   +19 how about the scoring distribution ? UPD : fixed
 » 4 years ago, # |   -7 Am I the only one who loves standard scoring distribution?
•  » » 4 years ago, # ^ |   +18 Am I the only one who is afraid of seeing the "double final-boss distribution" (500-100-1500-2500-2500)?
 » 4 years ago, # | ← Rev. 2 →   0 Submission stuck on the same pretest for over 8 minutes =/ Edit: fixed
•  » » 4 years ago, # ^ |   +9 Please write it to clars of contest, because we are not updating the comments often.
 » 4 years ago, # | ← Rev. 3 →   +2
•  » » 4 years ago, # ^ |   -10 He was not sure and did additional testing!
•  » » 4 years ago, # ^ |   0 How is this suspicious? I have been through such moments. I code one task, it has some bug, I code another one and then it occurs to me how to fix the bug in the first one.
•  » » » 4 years ago, # ^ |   +7 Fix the bug within 1 minute??
•  » » » » 4 years ago, # ^ |   0 Yes.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +12 He also used different headers for A,B,D and E,C
 » 4 years ago, # |   0 could anyone tell me if I can unregister from any contest after submitting one solution, or it is not allowed ?
•  » » 4 years ago, # ^ |   0 Then your rank won't --; and it means that everyone here can do the same. So, no. :)
•  » » 4 years ago, # ^ |   +1 No, you can't unregister after submitting a solution.
 » 4 years ago, # | ← Rev. 2 →   0 C is little bit tougher than usual :(
•  » » 4 years ago, # ^ |   +7 This is becoming usual
 » 4 years ago, # |   0 This contest was awesome but I'm really afraid of systest!!!:)
 » 4 years ago, # |   0 What is the hack for Div2B?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +7 Time limit. O(n^2*logn) does not pass time limit. Generated random output on n=10000 that's it.
•  » » » 4 years ago, # ^ |   0 Does C++ solutions fail that too?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Yup, I hesitated at first, but than I saw hacks on B, now I have +10 ;)
•  » » » » » 4 years ago, # ^ |   +9 Did same got 2 wrong attempts. Values of element I provided were in reverse. Does that affect sorting?
•  » » » » » » 4 years ago, # ^ |   +12 C++'s std::sort is fastest on reversed arrays AFAIK. I used "random_shuffle" for generator.
•  » » » » » » » 4 years ago, # ^ |   0 std::sort gave me TLE on case 32.
•  » » » 4 years ago, # ^ |   0 So the solution O(nm*logn) will pass?
•  » » » 4 years ago, # ^ |   0 Got TLE on 44th test case with O(m*n) solution.
•  » » » 4 years ago, # ^ |   0 I make a test case like this- 10000 10000 10000 9999 9998 9997 9996 9995 ..... 1 10000 1 1 10000 2 1 10000 3 1 10000 4 . . . Full test case is here in this link.This test case give me unsuccessful hacking attempt. Can you explain why It pass in 0.997 sec while in my pc (Operating System: Linux Mint 18.03 Processor: Intel Core i5 4th Gen, Ram: 8 gb) it takes 37 sec to run the same code in this test case ?
•  » » » » 4 years ago, # ^ |   0 Add -O2 while compiling! It will run in < 0.5 seconds :) You can make this hack successful. Try taking the first number last. I mean 9999 9998 9997 9996 ....... 5 4 3 2 1 10000
•  » » » » » 4 years ago, # ^ |   0 9999 9998 9997 9996 ....... 5 4 3 2 1 10000This case run in .904 sec in codeforce's custom invocation.
•  » » » » » » 4 years ago, # ^ |   0 Whats wrong with randomization? :PYou can just write random_shuffle(p, p+n); :)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I just calculated the no. of numbers in the range (l,r) which are less than x, if it is equal to (x-l) then that means if we sort the number in range (l,r) position of x won't change. Also answer is No if x is out of range (l,r). So I just spent O(r-l) in each query, and passed the pretest. Expected Complexity = O(m*n)
•  » » » 4 years ago, # ^ |   0 Both M and N are of order 10^4 then m*n = order of 10^8 Then why This approach didn't Exceeded Time Limit?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 The Time Limit is 2sec. I think it is enough for a 10^8 which I think runs around in 1sec.Correct me if I am wrong. Link to code.
•  » » » » » 4 years ago, # ^ |   0 You're right !! I just figured it out. O(N) – 10^8 O(N^2) – 10^4 Thanks.
 » 4 years ago, # |   +1 After coding a solution for C i understood that it's wrong. So, how to solve C?
•  » » 4 years ago, # ^ |   0 dp[i] = max_sum with first i elements.
•  » » » 4 years ago, # ^ |   +4 Can you give more details?
•  » » 4 years ago, # ^ |   0 precalculation + DP
•  » » » 4 years ago, # ^ |   0 What was your approach? In precalculation, I considered all codes minimum and maximum(which can be influenced by other codes in between). I couldn't get an idea in DP
•  » » » » 4 years ago, # ^ |   0 First calculate the beginning and ending of every segment and its comfort value then DP it by using DP(pos_of_the_seg_that_I'am_considring, the_pos_of_the_last_member_of_the_last_seg)here's my code it might help you to understand: code
•  » » » » » 4 years ago, # ^ |   0 Thank you. my dp parameters were 3 so my dp table was 5000*5000*5000 and I could not think of anything else. Bye bye expert :'(
 » 4 years ago, # |   0 Hack case for B?
•  » » 4 years ago, # ^ |   0 I just used counting sort, so i can't imagine a hack case except TLE one.
•  » » » 4 years ago, # ^ |   +4 I solved in O(m * log(n)) :D
•  » » » » 4 years ago, # ^ |   0 Me too.
•  » » 4 years ago, # ^ |   0 n=1e4 and m=1e4 :p for each m , l=1 , r=1e4 :p this will give TLE for them who used sort ..
•  » » » 4 years ago, # ^ |   +5 I tried that to some solutions, but failed :/
•  » » » » 4 years ago, # ^ |   +1 I tried that to some solutions ,but succeeded :3
•  » » » 4 years ago, # ^ |   +1 O(nm) for counting sort is 10^8 operations, it goes in less than two seconds
•  » » » » 4 years ago, # ^ |   +2 How? since when 10^8 goes in less than two seconds?
 » 4 years ago, # |   +4 I got Unsuccessful hack for hacking a solution in Problem B that sorts every time.How ? Isn't the complexity for this solution O(n * m * log(n)) ?
•  » » 4 years ago, # ^ |   0 Try to remove the log(n) factor.
•  » » » 4 years ago, # ^ |   +5 noelnadal You didn't understand what I mean.
•  » » » » 4 years ago, # ^ |   +5 I am sorry for that.
•  » » » » » 4 years ago, # ^ |   0 NVM
•  » » 4 years ago, # ^ |   0 The setters code works in O(n * m), but as you see some highly-optimized solutions in O(n * m * log) also passed.
•  » » » 4 years ago, # ^ |   0 hloya_ygrt Please look at Mohamed_Sakr'B code and tell me what is the complexity of this code.
•  » » » 4 years ago, # ^ |   0 My O(n * m) code in Python produced TLE, however the same passed in C++. There appears to be some issue in tester I believe.
•  » » » » 4 years ago, # ^ |   0 Python is much slower than C++, so you were lucky and you didn't pass a case which was not the worst case.
•  » » » » » 4 years ago, # ^ |   0 Normally, the settings are normalized in such a way that the choice of language wouldn't matter. However, I guess there was an oversight in this problem.
•  » » » » 4 years ago, # ^ |   0 Python is much more slower than c++.
•  » » » » 4 years ago, # ^ |   0 Sorry, this time we couldn't guarantee that python solution will pass.
•  » » » » » 4 years ago, # ^ |   -9 Why It wasn't mentioned in Problem statement?His complexity is O(NM) That should pass! Doesn't matter which language he was using -_-Lets make this round unrated -_-
•  » » » » » » 4 years ago, # ^ |   +16 Probably it is about participants should estimate their program's real time, not only complexity. The task was stupid itself and giving straightforward solution to pass would be even more stupid.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 My expected case O(n * m) solution in C++ also got TLE. I cannot generate a case on my machine that takes more than 0.4 seconds.http://codeforces.com/contest/811/submission/27374505
•  » » » » » » 4 years ago, # ^ |   0 nth_element doesn't always works in O(n). Your amortized complexity is O(n * m) but worst case complexity is still O(n * m * log n)
•  » » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 Yes, I know. That's why I said "expected case".The chances of it being should be extremely low using a "median of 3" style approach.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Use PyPy compiler interpreter next time: 27395525.
•  » » » 4 years ago, # ^ |   0 What do you mean highly-optimized? Solutions which do exactly what is said in the statement get accepted.
•  » » » » 4 years ago, # ^ |   +8 Where did you get that information? :) The system testing is still pending.
•  » » » » » 4 years ago, # ^ |   0 Okay, I couldn't hack them with a maximum test was what I mean :D Let's see :)
•  » » » 4 years ago, # ^ |   0 Why O( n*m ) works? N,M <= 10^4, dont tell me solution that counts number of elements smaller than x after x and bigger than x before x in range gets AC. I tried to come up with something better...I even tried solving it with segment tree but I didnt found solution.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I think complexity of 100M (10^8) should be able to pass in 2 seconds. That's only 50M in a second which is passable.Of course it depends on the code and language, but generally it should pass. I've seen some optimized codes where complexity of 100M passes in one second.
•  » » » » » 4 years ago, # ^ |   0 Thank you..I recognized O(n*m) solution quickly but didnt code it..poor me
•  » » 4 years ago, # ^ |   +8 I think, sort function can work faster than nlog(n) in some special cases. suppose if the array is completely sorted or sorted backwards. I too got Unsuccessful hack when I tried to hack with reverse sorted numbers like 10000 9999 9998.....Then I tried random numbers and then I got successful hack for every solution that used a sort.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 This is the response that I was waiting for.
•  » » » » 4 years ago, # ^ |   0 I had that in my mind but I was tooooooo Lazy to generate Random Permutation :D
•  » » » » » 4 years ago, # ^ |   +2 Its actually very easy to generate random permutation.Suppose N=5000.Put all elements from 1 to 5000 in a vector.Then use random_shuffle() on the vector and print the elements in order.
•  » » 4 years ago, # ^ |   0 The elements in your test case were in reverse order? If yes, C++ sort() works fastest for reverse order. A similar situation happened with me.
•  » » » 4 years ago, # ^ |   0 Yes that was the Problem, TY :D
 » 4 years ago, # |   0 How to solve E? I thought about counting how many components we add/subtract on every prefix/suffix and then using that we can answer queries, but I don't know whether that's correct.
 » 4 years ago, # |   0 how to solve D ?
•  » » 4 years ago, # ^ |   +9 Since there's guaranteed to be a path to finish, there has to be a . next to (1,1), either to the right or down, so you can check whether there is a swap on that direction. I assume I know that left = left, right = right, rest is symmetrical. Since there is a path you can go right until there's a '.' underneath you to test whether down/up are swapped. Right now you either reached the finish state or you have checked for both swaps. So you can get a path to finish state by using BFS and then just write all corresponding turns.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 1, If (1,1) is not a good place to test if R and L is swap, then test D and U, then use the result to find a good place to test R and L.2, If (1,1) is not a good place to test if U and D is swap, then test L and R, then use the result to find a good place to test U and D.3, Use normal DFS/BFS with tracing to find the path.4, Remember to terminate if you accidentally reach the finish square.
•  » » » 4 years ago, # ^ |   0 missed by a minute :(
•  » » 4 years ago, # ^ |   +3 just find out if Up and Down are swapped and if Right and Left are swapped then BFS it.My code:code
 » 4 years ago, # |   +9 nice problems, but I hate interactive problems.
 » 4 years ago, # |   +3 After locking B I saw very easy solutions of B without segment tree :D
 » 4 years ago, # |   0 What is the solution for E? And what do people hack on B? I could hack only one guy who used a segment tree to answer queries :D
•  » » 4 years ago, # ^ |   +2 You can use the same idea as in APIO 2017 problem 1.
•  » » » 4 years ago, # ^ |   +6 Where can I find APIO 2017 problems/solutions? Google didn't help.
•  » » 4 years ago, # ^ |   0 Which case for B? I used segment tree too.
•  » » » 4 years ago, # ^ |   0 Max case :D
•  » » 4 years ago, # ^ | ← Rev. 2 →   +9 I got through pretests on E by using segment tree. Complexity: m*logm*n*alpha(n) (Not sure if it will pass)Just maintain the component id's of left and right border of segment [l, r]. While merging two segments [l, mid] and [mid+1, r], you only need to find combinations along [mid, mid+1] You can do this this using dsu
•  » » » 4 years ago, # ^ |   +3 There can be many component ID's along a border right? Can you explain more?
•  » » » » 4 years ago, # ^ |   0 I think because n <= 10 so there are maximum 10 ID's along a border
 » 4 years ago, # |   +4 Just wanted to know.Is O(N*M*LOG(N)) passing for B?
•  » » 4 years ago, # ^ |   +6 Many people failed to hack the solutions with std::sort.
•  » » » 4 years ago, # ^ |   0 I tried to hack, but it works less than 2 sec. Can you explain hack test for std::sort?
•  » » » » 4 years ago, # ^ |   0 I also failed (I typed exactly same code in custom invocation form and tried many cases but...)
•  » » 4 years ago, # ^ |   0 It is, apparently. I tried to hack a guy who used that in my room. His solution ran in 967 ms. Idk why :/
•  » » » 4 years ago, # ^ |   0 I know what you probably used. You probably did this ..n = 10000 , m = 10000 all integers in inc order from 1 to 10000and then l = 1 , r = 10000 , x = some random numberI believe it must be this .. or close to this .
•  » » » » 4 years ago, # ^ |   0 Yeah, except that mine was reverse sorted. I found out that it's better to use random, but there's still no guarantee. I've seen the same brute-forces timing out on different test cases ~30. Some time out at 29, some at 35
 » 4 years ago, # | ← Rev. 3 →   0 Got some mysterious bug in D, and it's almost impossible to debug input which works when I test it and gets WA on first pretest.And my 10+ wrong submissions don't even seem to appear in standings.
 » 4 years ago, # |   0 Did somebody get runtime error in Div2D on 5th test? What is kind of test?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +6 Your program accidentally goes to the finish square, and your program must terminate (but your program didn't)
 » 4 years ago, # |   0 For problem C I got TLE on pretest 12, I understand the problem is : checking if it's ok to add segment [i,j] which work's in O(n) can it be calculated in O(1)?
•  » » 4 years ago, # ^ |   0 I think it can be calculated in O(1). For every element(city) keep its least appearance and highes appearance. Now we will precalculate ok[i][j]. Go from i to j, and for every next element ask where its highest appearance and lowest appearance is. Also, keep track of how many elements are bad (we call element bad if it appeared from i, but its highest appearance is after current right pointer (right border). When highest_appearance[current_number] == current_index that means one element is not bad anymore, so cnt--. If at any point cnt ==0, than that range is OK, othervise its not.
 » 4 years ago, # |   +3 What is the intended approach for the problem E? is it DP-like one?
 » 4 years ago, # |   0 The same algorithm for Div2B gave Time Limit Exceeded on Pretest 10 in Python 2.7 (http://codeforces.com/contest/811/submission/27381826), however passed for C++ 14 (http://codeforces.com/contest/811/submission/27386544). This is wrong behavior, right?I ended up spending all my time on this :(
•  » » 4 years ago, # ^ |   +6 No, it is not wrong behavior :D Python is just slow :D
•  » » 4 years ago, # ^ |   0 Just because cycles are really slow in python
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 Welcome to the disadvantages of python. I was gonna use python but then I thought as there was a tight bound to code in c++ only.
•  » » » 4 years ago, # ^ |   0 Yeah, I didn't realize that sometimes problems are not normalized to work irrespective of the choice of language. Not many python users here I guess.
•  » » 4 years ago, # ^ |   0 however this code http://codeforces.com/contest/811/submission/27378308 is passing pretest 10
 » 4 years ago, # |   0 Didnt check B's constraints and used seg tree :/
•  » » 4 years ago, # ^ |   0 I can understand that feeling :(
•  » » 4 years ago, # ^ |   0 Can u explain me solution with segment tree? I tried to come up with seg tree solution but I couldnt because each query you are searching for elements smaller than x or higher than x, but x is different each time.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +1 In each node of segment tree, store the numbers in the range start-end and sort it.Now, when there's a query like: 1 100 50Then split it into two ranges:1. 1-502. 50-100.In the first range find the number of elements greater than val[50](let it be x) and in the second range find the number of elements less than val[50](let it be y).Getting this number can be done through binary search in the required nodes since the elements stored in each node are sorted.If x==y, then position wouldnt change.
•  » » » » 4 years ago, # ^ |   0 I am not experienced too much with seg trees. I never saw a seg tree whose node stores literally vector of elements. Isnt it too much that every node has more elements? also, can you send me code, so i can see implementation of that?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Code: 27377920, http://ideone.com/wHHPs1It might seem that it might take too much memory but in reality it only requires NlogN memory since each element will appear in atmost logN nodes.
•  » » » » » » 4 years ago, # ^ |   +3 http://codeforces.com/blog/entry/15890 in this blog there is section segment tree with vectors. This could help a lot for your approach! Thank you for explanation.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Memory is O(nlogn)
 » 4 years ago, # | ← Rev. 2 →   +5 Please start systest fast before AGC starts ;Dedit: denied :D
 » 4 years ago, # |   0 https://ideone.com/SlRErLCan someone tell me what's wrong with my Solution for C?
•  » » 4 years ago, # ^ |   0 If I understand right your code, you are wrong for two reasons: First, you only make operation XOR to value iff mx[ a[ i ] ] >= x && maxx[ a[ i ] ] == i, so if the previous sentence is ok you perform the XOR operation but all values between [ mx[a[i]], maxx[a[i]] ] that are different to a[i] and have a maxx greater than maxx[ a[i] ] you doesn't include them, so it is wrong because for definition in the problem statement the XOR operation includes all different values in the segment [l, r].Second, if you find an a[i] that have mx[ a[i] ] < x, you can't include the segment [ x, i ] in your current answer, because you never could take a valid segment that include all values equals to a[i].Maybe you have more mistakes but these are the most easiest to see.
•  » » » 4 years ago, # ^ |   0 My bad ,didn't read statement carefully and to add to it this logic was passing for 11 test cases so never bothered to read statement again.Bdw thanks for your help.I got it accepted by minor change.:(http://codeforces.com/contest/811/submission/27391034 In case you want to take look . Thanks again
 » 4 years ago, # |   0 What is the intended solution for B?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Counting inversions (though I used quickselect)?
•  » » » 4 years ago, # ^ |   0 Won't using quickselect result in TLE?I mean using quickselect will give you O(n*m) time complexity which is 10^8 in worst case. This idea came to my mind but I didin't implement it because of time constraint
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Why would 10^8 not pass?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 O(n * m) is fine because tl is 2 seconds, there is only simple operations like adding and comparing integers, and codeforces is very fast.
•  » » » » 4 years ago, # ^ |   +3 Actually, computers are so fast that is absolutely fine with n,m  ≤  10000.
•  » » » » 4 years ago, # ^ |   0 My solution with quickselect got TLE: http://codeforces.com/contest/811/submission/27376379
•  » » » » » 4 years ago, # ^ |   +1 Notice the TLE case, though. It may be that nth_element is not well implemented in the standard library linked by codeforces, since it appears to only TLE for reverse sorted data.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 You can just count how many elements are smaller than p_x in that range, and thereby check if position stays the same.
•  » » » 4 years ago, # ^ |   0 Can you please elaborate on how to calculate elements smaller than p_x in a given range efficiently?
•  » » » » 4 years ago, # ^ |   +6 I just calculated it with linear scan, pretests passed in 31ms.
•  » » » » 4 years ago, # ^ |   +3 My solution was based on a segment tree, were each leaf stores respective sorted segment of original sequence. So, complexity is perhaps O((m+n) *log(n)). (build () in n*log(n) + answer m queries for log(n))
•  » » » » » 4 years ago, # ^ |   +12 overkill.
•  » » » » » » 4 years ago, # ^ |   0 It was just my second thought. First was simple sorting for each query I did not believed them it can pass
•  » » » » » 4 years ago, # ^ |   +5 I'm sure the query on your code is O(log^2(n)), for it to be logn it should use fractional cascading (not needed since it usually doesn't speed up much).
•  » » » » » » 4 years ago, # ^ |   0 I thought during contest Maybe we can solve C using similar segment tree. And can we actually solve C using that?
•  » » » » » » » 4 years ago, # ^ |   0 I don't think so. Especially since some people got TLE using a set.
•  » » » » 4 years ago, # ^ |   0 Here the code. http://ideone.com/qTlcB5
 » 4 years ago, # |   0 Can anybody help me figure out the reason behind memory limit exceeded in Problem D? http://codeforces.com/contest/811/submission/27386058
•  » » 4 years ago, # ^ |   0 Maybe that is not a memory limit exceeded but a runtime error; those two errors usually not classified correctly.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I'm not sure, but you should do this ans[p.a][p.b] = p.ch; when you push node to queue
 » 4 years ago, # |   +7 How come O(n*m*log(n)) solution is passing for the problem B?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Same question! I attempted to hack one's code but failed! O(nm log n) algorithms terminated in 1.2 seconds in the worst case!My poor 50 pts...Shouldn't O(n√nlogn) MO's algorithm or O(nlogn) functional segment tree be the intended solution?Why the bruteforce passed?
•  » » » 4 years ago, # ^ |   0 Because n,m<=10^4.Intended soln was O(N*M) bruteforce because 10^8 fits in TL.
•  » » » » 4 years ago, # ^ |   +3 Yes, it did, but should it? And what about O(nm log n)? Then I get nothing more but less pts because of MO's algorithm and Binary Indexed Trees?
•  » » » » » 4 years ago, # ^ |   0 Because its generally known that upto 10^8 operations would fit in 1-2 secs.I too used seg tree because I didnt check the constraints properly.I dont like this question too.
•  » » » » » » 4 years ago, # ^ |   0 Sorry for bothering but... Is it generally known that up to 10^8 operations would fit in 1-2 secs? Am I out? For long time the number was 5×10^6 for me……
•  » » » » » » » 4 years ago, # ^ |   +5 Answer by yeputons: hereAlso check this: http://codeforces.com/blog/entry/21772?#comment-264557
•  » » » 4 years ago, # ^ |   0 The entended algorithm is O(n * m). I also tried to hack a O(n * m * log(n)) solution (which theoritically results in 10^9 operations) but my hack was unsuccessful. I wonder if codeforces servers are that fast.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 This problem should be problem D with n,m <= 10^6. I solved with Merge Sort Tree O(m log^2 n), and then wondered how a merge sort tree problem can be solved by 2800+ contestants :|
•  » » » » 4 years ago, # ^ |   +1 Yeah, I finished MO's algorithm at arount 00:36, but I found that a lot had finished way before that!
•  » » » » » 4 years ago, # ^ |   0 But I think MO is overkill :3
•  » » » » 4 years ago, # ^ |   0 Exactly, I was making a segment tree but the same thought entered my mind. How can a segment tree problem be listed B in a contest.
•  » » » » » 4 years ago, # ^ | ← Rev. 5 →   +9 Haha! I was thinking that, too...====My thoughts====Ahh, an easy functional segment tree or MO's algorithm problem.Wait a minute, is it a B?Is there an easier way to do it? It is just a B!O(n^2)? If so, then why not n=10^3 & m=10^3?There must be traps...====3 minutes later====Whatever... MO's algorithm for safety...====After an unsuccessful hack====WTF?????????????????????????????
•  » » » » 4 years ago, # ^ |   0 No, it's too simple even for c.
•  » » » » 4 years ago, # ^ |   0 Yes! Exactly my thoughts. Even I submitted the solution using merge sort tree around 90 mins into the contest and was wondering what is the easy approach which I am missing .
•  » » » 4 years ago, # ^ |   0 I think the intended solution was brute force O(n*m) but the solution with complexity O(n*m*log(n)) should fail cause it extends upto 10^9.Yes, i think actual solution should be either MO's or segmented trees. But in previous contest too many times solution with 10^8 complexity pass very smoothly.
•  » » » » 4 years ago, # ^ |   0 Alright... resonable... but still... unhappy :(
•  » » » » » 4 years ago, # ^ |   +1 I tried to hack a solution with O(n*m*log(n)) complexity and the person had used vectors instead. But it passed with in 0.8 despite the fact vectors are too slow than arrays.So felt terrible.
 » 4 years ago, # |   +4 Can we solve problem E using Mo's Algorithm?
•  » » 4 years ago, # ^ |   0 I like your idea, we can try dsu-on-buckets-sized-sqrt(n). It would be something like , which seems okay to me.
•  » » » 4 years ago, # ^ |   +5 Would you mind to further elobarate on your idea? I don't quite understand how could you break the DSU apart when you are "shrinking" the interval.
•  » » 4 years ago, # ^ |   0 I don't think so. But you can solve it with a segment tree.
 » 4 years ago, # |   +23 please start system test.
 » 4 years ago, # | ← Rev. 2 →   0 Solved 1 problem in last 2 rated contest, Then solved 2 problems in next contest, >>>>> unfortunately that was unrated.;( ;(Finally a rated one... Can't wait for the ratings to be updated,Please Finish the system test, for God's sake.... solved 2 problems.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 Codeforces Servers
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +16 Radioactive Chernobyl' potato and 0.0000001 nm microprocessors.
•  » » » 4 years ago, # ^ |   0 Same happened on CodeChef take a look https://discuss.codechef.com/questions/99237/slow-speed-of-submissions
•  » » 4 years ago, # ^ | ← Rev. 2 →   +2 Rating does not matters there when you are not a grandmaster and can't receive money from Botan Investment. Two problems div. 2 solved are not enough to become a grandmaster. So, you should not worry.
•  » » » 4 years ago, # ^ |   0 Well everyone start's from somewhere. This is my origin. No problem howmany penalties, lost rating, One day I'll be A Legendary Grandmaster.Any doubts mr. @Mahilewets.
•  » » » » 4 years ago, # ^ |   0 Hahaha! I can say you will never become legendary grandmaster then you might become angry and start work harder and become closer to your goal...
•  » » » » » 4 years ago, # ^ |   0 I am still learning, I have ambitions, not overconfidence, you might laugh. Actually, the rating is 1256 I'm not as dull as you might be thinking. Still getting familiar with Codeforces system it's kind of confusing though but I like the problems. My home is CodeChef.
•  » » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 So, I believe that genius are made, not born. And I really hate learning curve... And my previous comment was really intended to strengthen motivation.
•  » » » » » » » 4 years ago, # ^ |   0 Currently, my face is exactly as my avatar.Just joking. Thanks for the motivation.
 » 4 years ago, # |   +1 I tried hacking several O(n*m*log(n)) solutions using a full test case of just 1,2,3,...10000 (permutation in sequence).On my own PC this test case takes 30 seconds, but all my hacks failed. Other people hacked those solutions later with "random" large case instead of sequence 1,2,3,4...10000.Then I compiled my slow test case with "-O2" and it runs in 4 seconds on my PC instead of 30.So the question is, what all does C++ sort() in "-O2" flag optimize, besides "numbers already sorted"? Does it check for "reverse sorted" and "almost sorted"? Thanks.
•  » » 4 years ago, # ^ |   +6 Always use this: http://codeforces.com/problemset/customtest when you want to check execution time.
•  » » » 4 years ago, # ^ |   0 Wow I had no idea about that. Thanks!
 » 4 years ago, # |   +8 "I am also going to tell you about the Olympiad a bit later." When??
 » 4 years ago, # |   0 How to solve C?
•  » » 4 years ago, # ^ |   0 dynamic programming: d[i] -> maximum comfort of people numbered 1..i (or i..n)
•  » » 4 years ago, # ^ |   0 First we find the first and last occurrences of numbers in the array (not just a [i] <= 1000). Then, for each number, look for the beginning and end of the segment, which must enter if we take this number. Thus, we have an array of pairs of possible segments, which are sorted by their beginnings. Obviously, if the beginning of one segment is inside the other, then the entire segment will be in it, so we need to either take each segment completely or split into sub-sections (choose the largest from this). This can easily be done recursively, for example. one segment is inside the other, then u
 » 4 years ago, # |   +4 I was sure 10^8 cant fit in 2 seconds. I came up with O(n*m) idea very quickly but I didnt code it since I thought it wont pass...cri
 » 4 years ago, # |   0 Why did I got TLE 27376612 works in O(m * n * logn).Please hepl..
•  » » 4 years ago, # ^ |   +3 Shouldn't it?
•  » » 4 years ago, # ^ |   0 10^4*10^4*log(10^4) = 1,3 * 10^9 (it is average)
 » 4 years ago, # |   0 How to take in C take account of xor of unique elements in a range ???? I used set and it gave TLE :( So stupid of me
•  » » 4 years ago, # ^ |   +3 Just replace set with simple array.
•  » » » 4 years ago, # ^ |   0 And maintain a vector to remember which elements have been encountered ???
•  » » » » 4 years ago, # ^ |   0 Yes, it's called counting sort. https://en.wikipedia.org/wiki/Counting_sort
•  » » » » 4 years ago, # ^ |   0 since a xor a = 0, then ( a xor a) xor a = a. So if you have even number of same elements in range, just do one more xor on same element. Othervise, if there is odd number of same elements in range, xor all of them and answer will be correct.
•  » » » 4 years ago, # ^ |   0 I do not know but array did not work :( Unordered map did !!! Thanks for help :)
•  » » 4 years ago, # ^ |   +3 ai ≤  5000 you could use array
•  » » 4 years ago, # ^ | ← Rev. 2 →   -8 I used Map :( I got tle on main tests, FUCK Using Array it ran in 61ms :(
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 I dont like Nicki Minaj :(
•  » » » » 4 years ago, # ^ |   0 I like Taylor Swift
•  » » » » » 4 years ago, # ^ |   +9 I like guys
•  » » » » 4 years ago, # ^ |   0 Care to share the reason?
•  » » 4 years ago, # ^ |   0 I used map and it also passed. It also takes log n time. Here
•  » » » 4 years ago, # ^ |   0 I used unordered map then got AC but TLE in normal map :(
•  » » 16 months ago, # ^ |   0 Why does using set give TLE?????
 » 4 years ago, # |   0 How to solve problem B if constraints were 1 <= n,m <= 10^5 ?
•  » » 4 years ago, # ^ |   +3 You can use segment tree, approach was described earlier http://codeforces.com/blog/entry/52186?#comment-362512
•  » » » 4 years ago, # ^ |   0 Or even better — use a persistent one. This way you get an O(mlogn) solution instead of an O(mlog^2n) one, I would put my bets on this being the fastest solution. (I doubt someone can comeone with a linear time solution though — It's quite crazy)
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # |   0 Forgot to terminate the program in some cases, got idleness limit exceeded XD
•  » » 4 years ago, # ^ |   0 I think I remember to terminate, but still got this http://codeforces.com/contest/811/submission/27385612Can someone tell me why?
•  » » » 4 years ago, # ^ |   0 What I did, was to read the x y after printing the direction and if x or y equals -1 then stop the program.
•  » » » 4 years ago, # ^ |   0 It seems that you should still be reading the input when you output your solution after bfs (even though you it doesn't change your solution in any way). So in your last while loop you should be reading x and y in every cycle.
 » 4 years ago, # |   0 can anyone tell why this is giving TLE. I think coplexity is 5000*5000 .
 » 4 years ago, # |   0 Got RTE in D because I didn't remove asserts :'(
 » 4 years ago, # |   +1 anybody knows the reason for getting WA on Test-49 of C ?
•  » » 4 years ago, # ^ |   +6 I stress tested your code and it fails on this test: 7 2 5 1 2 2 4 1  Answer is 9.
•  » » » 4 years ago, # ^ |   +1 got it. Had made a silly mistake :( Thanks :)
•  » » » 4 years ago, # ^ |   +1 How to write a stress test?
•  » » » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ |   0 Would you be so kind to stress mine aswell? Can't figure out why my solution gives a slightly greater answer for #20 than expected.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   +3 I think you did the same mistake as I did. Here is the case:  5 4 4 5 4 5  Answer is 1. But your code prints 0.
•  » » » 4 years ago, # ^ |   0 how is it 9?
•  » » » » 4 years ago, # ^ |   0 take only segments with 4 and 5. They sum to 9.
 » 4 years ago, # |   +9 I solved 4 problems but it says 2 out of 5. Is anyone else facing the same issue?
•  » » 4 years ago, # ^ |   0 Same here.
•  » » 4 years ago, # ^ |   0 I faced it several times before. It will be OK after a while.
 » 4 years ago, # | ← Rev. 2 →   +16 That awkward moment when you spend half an hour explaining your O(msqrt(n)) solution for B to your friend, but their O(nm) solution also got AC.Edit: it should be O(msqrt(n)log(n))
•  » » 4 years ago, # ^ |   0 How to go about an O(msqrt(n)) solution?
•  » » » 4 years ago, # ^ |   0 I could only think of O(msqrt(n)log(n)) solution using Mo's Algorithm + BIT. While you are processing each query using Mo, maintain a BIT containing the occurrence of each number from L to R, and use it to answer each query.How to remove the log factor from BIT ?
•  » » » » 4 years ago, # ^ |   0 It can be solved in O(Q * log(N)) with offline algo.
•  » » » » » 4 years ago, # ^ |   0 Yes I'm aware of that. But I'm curious about maintaining the occurrence of numbers in Mo's query in constant time though.
•  » » » » » » 4 years ago, # ^ |   +6 Compress the numbers and use sqrt decomposition. Since update is O(1) complexity will become O(Q * sqrt(N)).
•  » » 4 years ago, # ^ |   0 How did u solve it? Mos algorithm? I thought maybe there is mos algorithm solution because constraints looked perfect for it.
 » 4 years ago, # |   0 Can anyone help me to find the error, in problem D? 27388425
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 You may step on a dangerous cell when you "check for left_right". Once you step on a dangerous cell, you will lose the game. So you might lose the game on the first step. Here is my code http://codeforces.com/contest/811/submission/27381946 (How can I paste my code like you?)
•  » » » 4 years ago, # ^ |   0 Thanks for reply. For share your code, there is a bar icon in comment box. Here you can select the submission and paste your submission id(like 27381946)
•  » » » » 4 years ago, # ^ |   0 Oh I get it.
 » 4 years ago, # |   0 It gave me TLE on case #87: 1 2 0 0 .F But I tested and it does in 3 moves, and the limit would be 2*1*2 = 4
 » 4 years ago, # |   -6 Was this contest rated or not????
•  » » 4 years ago, # ^ |   0 Yes, it was.
•  » » » 4 years ago, # ^ |   0 So why it's taking longer than usual for the change..!!
•  » » » » 4 years ago, # ^ |   +3 Because it is usual? o_O
 » 4 years ago, # | ← Rev. 2 →   +3 Can anyone explain what was wrong in the following approach for problem C. I tried to break the problem into a weighted job scheduling problem. The start and end times for jobs are the minimum starting and maximum ending index of each element . The profit is the xor of non individual elements taking each element only once in an interval. Then our goal is to maximize the sum of xor of non overlapping intervals which is the same as job scheduling . My solution was failing on testcase 12
•  » » 4 years ago, # ^ |   0 You're not ensuring that in that interval , all the elements in the interval have their first and last occurrence within the interval itself .
 » 4 years ago, # |   0 can we get tutorial for this round?
 » 4 years ago, # |   0 Problem D, Idleness limit test 70?
 » 4 years ago, # | ← Rev. 2 →   0 I had submitted this(http://codeforces.com/contest/811/submission/27386058) solution during the contest for problem D(811D - Vladik and Favorite Game). In the test case 6, there is no 'F' in the input given. In the problem, it is stated that there is exactly one 'F' to be given in the input. Am I missing something?
•  » » 4 years ago, # ^ |   0 It is present. The complete testcase isn't shown because of its big size..
•  » » » 4 years ago, # ^ |   0 Oh! Did not realize that. Thanks.
•  » » 4 years ago, # ^ |   0 there is 50x50, at the end ..., so F is below
 » 4 years ago, # |   0 How to solve D? I attempted below implement but WA(My English may not be that good to explain clearly):We start at a corner, there are 2 "edges", there must be a solution so at least one direction is '.', we can try that direction and get the result(wether moved or not).Implement a BFS and find the right path to 'F', there will be 2 situations:1.we keep on going "on an edge", then one direction would be enough2.we leave the edge at some moments, it means there will be a corner, we can apply the methods above again and get both directions right.Seems right, but WA. Am I having wrong idea or just buggy code?27384993
•  » » 4 years ago, # ^ |   +3 Probably due to buggy code.I used the same logic.
•  » » » 4 years ago, # ^ |   0 Thanks, and excuse me, what's the meaning of:Checker commentwrong output format Unexpected end of file — token expected"token expected"??? What token should I output?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 I'm guessing its because your program terminated before reaching end point.When checking if the direction is correct/wrong and if its wrong, your position will be the same so you will have to repeat the move with the opposite direction.If you havent done this, I guess it might be the cause of the error.
•  » » » » » 4 years ago, # ^ |   +3 Thank you. I found my bug! I forgot a "return" in my function and values of x and y were updated twice... Feeling worse... I didn't find it during the contest but till now.
•  » » » » » 4 years ago, # ^ |   0 Append: the correct one27390186
•  » » 4 years ago, # ^ |   0 We can find a path from (1, 1) to 'F' using bfs, and then we have to check whether left-right( call it swapl) or up-down (call swap swapu) are swapped or not, and then print the path according to new left-right and up-down.To find the swapping :- As there always exists a solution so you can find either swapl or swapu is true. Suppose we can go to (1, 2) then we will print 'L' and check if it moves to (1, 2) then swapl is true ( Similar is the case for swapu if we can move to (2, 1) )If we cannot go to (1, 2) then we will go down till we find place when we can move from (i, 1) to (i, 2) and check again similarly as described above. Same is the case with finding swapu.Refer this Most of the things are similar so it's just copy-paste with few changes.
•  » » 4 years ago, # ^ |   0 Can you explain how to handle case like .*.........F what happens if I press 'D' as first button pressed, but 'R' and 'D' have been interchanged.
•  » » » 4 years ago, # ^ |   0 The problem stated that only the LR and UD can be swapped with each other.
•  » » » » 4 years ago, # ^ |   0 In that case, it's quite easy to be div2 D, and < 500 accepted submissions. What am I missing?
•  » » » » » 4 years ago, # ^ |   0 The statement was overcompicated and Im sure a lot of participants didnt even get what they had to do in that task. :(
•  » » » » » » 4 years ago, # ^ |   0 Sorry but this problem isn't harder than div2B.
•  » » » » » » » 4 years ago, # ^ |   0 Well, my solution for Div2B is nearly 10 lines, and no thinking was required to code it. My solution for Div2D is nearly 250 lines with a lot of corner cases, and you're saying that it was easier than B...