### Nerevar's blog

By Nerevar, 6 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.

•
• +40
•

 » 6 years ago, # |   +2 Fast editorial :) Thanks!
•  » » 6 years ago, # ^ |   0 The editorial isn't fast, moreover they cannot be fast.
 » 6 years ago, # |   +2 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
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 yes, you are right. I got AC with this idea.
•  » » » 6 years ago, # ^ |   0 can you please explain using an example?
•  » » » » 6 years ago, # ^ |   0 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
•  » » 6 years ago, # ^ |   0 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)
•  » » » 6 years ago, # ^ |   0 sorry, You are saying problem_B?
•  » » 15 months ago, # ^ |   0 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
 » 6 years ago, # |   +8 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.
•  » » 6 years ago, # ^ |   0 agree.
•  » » 6 years ago, # ^ |   0 Could you please be more meticulous?
•  » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 years ago, # ^ |   0 Thx. That is exactly how I was struggling... But your approach is different from ForeverBell's one, which sounds more attractive xD.
•  » » » » » 6 years ago, # ^ |   0 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')).
 » 6 years ago, # |   0 I wonder how to use BFS for problem C without getting MLE, I used BFS but got MLE :(
•  » » 6 years ago, # ^ |   +8 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.
•  » » » 6 years ago, # ^ |   0 yes, I made this mistake during the contest. thx
 » 6 years ago, # | ← Rev. 3 →   0 Hello . Can anyone tell me what is wrong with my source ? I can't find it and I know the solution is ok .2728928
•  » » 6 years ago, # ^ |   +6 Basically your queue is not long enough. make it ~~~~~ cp q[10000000]; ~~~~~
•  » » » 6 years ago, # ^ |   0 Thanks! This was the error which ruined my rating ..
•  » » 6 years ago, # ^ |   +3 use std::queue in future.
•  » » » 6 years ago, # ^ |   0 I learned that push_back and this kind of function are a bit laggy and I was afraid of TLE
 » 6 years ago, # | ← Rev. 2 →   0 Can someone please suggest an improvement for my code for Problem D? I'm getting TLE after implementing the approach mentioned in the tutorial.
 » 6 years ago, # |   0 binary search! didn't think of that! very good editorial!
 » 6 years ago, # |   0 hey can anyone help me with problem D ? if i consider every subtable it will be 400*400*400*400 and i TLE
•  » » 6 years ago, # ^ | ← Rev. 2 →   +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.
•  » » » 6 years ago, # ^ |   0 Why is it right?! O((n^2) * m) = 400 * 400 * 400 = 64 000 000! I have got TL.
•  » » » » 6 years ago, # ^ |   0 The worse complexity of computer is 10^9 a second , so it won't be TLE...
•  » » » » » 6 years ago, # ^ |   0 are you sure?! 10^9 per second! I don't think so =/ Where i can see this information?
•  » » » » » » 6 years ago, # ^ |   0 sorry ,I'm wrong...
•  » » » » 6 years ago, # ^ |   0 I think your code's worst complexity is O((nm)^2).
 » 5 years ago, # |   +3 Hi, I want to know when the O(NlogN) solution of problem E available? Or is there any code written in that complexity?Thanks!
 » 5 years ago, # |   0 How do I improve my solution (2820048) to D — Table with Letters — 2? It's getting TLE on test 23.
 » 4 years ago, # |   0 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"
 » 4 years ago, # |   +6 Everyone should keep it in mind who use "w+"/"r+" in c++ for opening file. http://codeforces.com/blog/entry/11335
 » 4 years ago, # |   0 can someone send me the code of the printer please :(( pls
 » 3 years ago, # |   0 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
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   0 It seems like the problem with Binary-Search.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); 
 » 15 months ago, # | ← Rev. 5 →   0 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.
 » 13 months ago, # |   0 unable to solve 253B — Physics Practical can any one explain?