### Nerevar's blog

By Nerevar, 7 years ago, translation, , Sorry for the short tutorial: we are too busy preparing and conducting school competition.

253A - Boys and Girls

Lets assume that we have more boys than girls (the other case is solved similarly). Then we can construct one of the optimal solutions in the following way: we add pairs consisting of a boy and a girl (BG, in that order) to the end of the line until we don't have girls any more. Then add remaining boys to the end of the line. For instance, with 7 boys and 4 girls we will come to the solution BGBGBGBGBBB.

253B - Physics Practical

For each x from 1 to 5000 calculate count(x) — the number of measurements equal to x. The iterate over all possible minimal values m (from 1 to 5000). For a fixed m we can easily figure out which numbers we have to erase: we should erase every number k that k < m or k > 2·m. To find out the number of such values in the given sequence, we should sum up values count(k) for all such k.

253C - Text Editor

One of the solutions to the problem is breadth-first-search (BFS). Vertices of the graph correspond to all possible pairs (r, c), denoting the row and the position of the cursor. Each vertex has at most four arcs leaving it (these arcs correspond to pressing the buttons). So we need to find the shortest path from one vertex to the other. There are at most 107 vertices and at most 4·107 arcs. This problem can also be solved with some greedy observations.

253D - Table with Letters - 2

Lets iterate over all pairs of rows i, j (i < j), that bounds the sub-table from the top and from the bottom. Then for each character ch make a list of such column numbers k that T[i, k] = T[j, k] = ch. Consider such list for some fixed character ch. All we need to count is the number of pairs l, r (l < r) in this list such that the sub-table with corners at (i, l) and (j, r) contains not more than k characters "a". This can be done using two standard techniques: two-pointer method and calculating partial sums.

253E - Printer

First lets learn how to simulate the process with all priorities known. We will keep the priority queue of tasks. The task enters the queue when the printer receives this task, and leaves the queue when the printer finishes it. Then every change in the queue happens when one of the two possible events occurs: the printer receives some task or finishes printing some task. Between the consecutive events printer just prints pages from the tasks with the highest priority. So, if we maintain a set of events, the simulation can be done in O(NlogN).

To solve the problem, make an obvious observation: the higher priority the task has, the sooner the printer finishes it. Then the required missing priority can be found using binary search. Also we can search the missing priority among O(N) values. The overall complexity is O(Nlog2(N)).

This problem also has O(NlogN) solution, which will be described later. Tutorial of Codeforces Round #154 (Div. 2) Tutorial of Codeforces Round #154 (Div. 2)  Comments (45)
 » Fast editorial :) Thanks!
•  » » The editorial isn't fast, moreover they cannot be fast.
 » the second problem can be also solved by sorting the sequence and performing a binary search for every 1<=i<=N in O(nlogn) time
•  » » 7 years ago, # ^ | ← Rev. 2 →   yes, you are right. I got AC with this idea.
•  » » » can you please explain using an example?
•  » » » » well basically, the main observation is: after i sort my results, i can find a contiguous part of the results which satisfy my conditions.How can i find that? You can even check every single candidate subarray, or perform a binary search for every i<=N and find the upper bound that satisfy your conditions: http://codeforces.com/contest/253/submission/2728058
•  » » I think this problem can also be solved in O(n), which is asymptotically optimal. Considering the rows. The best you can do is to go an arbitrary position(maybe the same as you are) and than to the destinantion row. The column position is now the minimum of all lines considered(-> can be determined vial O(n) preprocessing + O(1) query time). and the current position. There are n rows to check in O(1) time. So the overall complexity is O(n)
•  » » » sorry, You are saying problem_B?
•  » » I tried to do it using two pointer . Following is my solution. Can you explain why my solution is getting TLE in very first test case when I submit???? It runs correctly through Custom Invocation. Please, need help.MY SUBMISSIONThnx
 » About the C problem: the greedy observation is simple: a best solution must have the following structure, just simply move the cursor only up or down to some row i, then move to the destination row and directly to the destination column.
•  » » agree.
•  » » Could you please be more meticulous?
•  » » » suppose you are in location (r1,c1), you wanna go down to (r2,c2). find the line with minimum length l between them(include start and end line), the fastest way you can reach (r2,c2) is r2-r1+abs(l-c2). now suppose you can go up, then go down, so track an non-increase length which is less than l, and go to that line fist then go down to line r2. you need to do the same thing to lines lines below r2 too. hope it helps.
•  » » » » Thx. That is exactly how I was struggling... But your approach is different from ForeverBell's one, which sounds more attractive xD.
•  » » » » » after think about it, i think you could combine the up, middle, down step, find form r1 to other rows, where the c will ends up with, say it's (r',c') then, go from that row to r2. min(abs(r1-r')+abs(r2-r'),abs(c1-c')+abs(c2-c')).
 » I wonder how to use BFS for problem C without getting MLE, I used BFS but got MLE :(
•  » » there is no need to keep a large amount to vector. there are only 4 possible ways to go for each step, i.e. up, down ,left, right.
•  » » » yes, I made this mistake during the contest. thx
 » 7 years ago, # | ← Rev. 3 →   Hello . Can anyone tell me what is wrong with my source ? I can't find it and I know the solution is ok .2728928
•  » » Basically your queue is not long enough. make it ~~~~~ cp q; ~~~~~
•  » » » Thanks! This was the error which ruined my rating ..
•  » » use std::queue in future.
•  » » » I learned that push_back and this kind of function are a bit laggy and I was afraid of TLE
 » 7 years ago, # | ← Rev. 2 →   Can someone please suggest an improvement for my code for Problem D? I'm getting TLE after implementing the approach mentioned in the tutorial.
 » binary search! didn't think of that! very good editorial!
 » hey can anyone help me with problem D ? if i consider every subtable it will be 400*400*400*400 and i TLE
•  » » 7 years ago, # ^ | ← Rev. 2 →   You do not need to consider every subtable. You fix two rows (or columns, no matter) and then go through columns (or rows), check if letters in cross are same and if it is so you add this column (or row) to list associated with that letter. Then for each letter you go through it's list and count how much subtables are "good" (number of 'a' we preculc by dp). So, we fix two rows (O(n^2)), go through columns (O(m)) and check this columns (O(m)). Asymptote is O( (n^2) * m) or O( (m^2) * n ), depend on your choice.
•  » » » Why is it right?! O((n^2) * m) = 400 * 400 * 400 = 64 000 000! I have got TL.
•  » » » » The worse complexity of computer is 10^9 a second , so it won't be TLE...
•  » » » » » are you sure?! 10^9 per second! I don't think so =/ Where i can see this information?
•  » » » » » » sorry ,I'm wrong...
•  » » » » I think your code's worst complexity is O((nm)^2).
 » Hi, I want to know when the O(NlogN) solution of problem E available? Or is there any code written in that complexity?Thanks!
 » How do I improve my solution (2820048) to D — Table with Letters — 2? It's getting TLE on test 23.
 » I always get runtime error on problem 1. (#253A) I can't find the reason for this message.The code: import sysn,m=map(int, raw_input().split()) i=min(n,m) print (n-i)*"B"+i*"GB" +(m-i)*"G"
 » Everyone should keep it in mind who use "w+"/"r+" in c++ for opening file. http://codeforces.com/blog/entry/11335
 » can someone send me the code of the printer please :(( pls
 » Can anyone help me as to why am I getting a run time error in 253 B ( physics practical ) http://codeforces.com/contest/253/submission/9244115
 » My code if running fast enough on my system,still its showing TLE on testcase #1.Plz help. http://codeforces.com/contest/253/submission/11731622
•  » » It seems like the problem with Binary-Search.
•  » » 4 years ago, # ^ | ← Rev. 2 →   freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); 
 » 3 years ago, # | ← Rev. 5 →   A greedy (or maybe brute force) solution for C — Code. For each row k: - start from r1, go till k, then go to r2 - move till c2 Choose the k for which the button presses are minimum.
 » unable to solve 253B — Physics Practical can any one explain?
 » 11 months ago, # | ← Rev. 2 →   Code for A giving wrong answer after submission, but it is running perfectly in my compiler. Please look. https://codeforces.com/contest/253/submission/47244948
 » In question C, can someone please tell me why the BFS approach in submission 60272417 is giving TLE verdict on testcase 10?