Nerevar's blog

Codeforces Round #154 (Div. 2) — tutorial
By Nerevar, 12 years ago, translation, In English

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.

  • Vote: I like it
  • +40
  • Vote: I do not like it

Comments Comments (44)
| Write comment?
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Fast editorial :) Thanks!

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    yes, you are right. I got AC with this idea.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please explain using an example?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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://mirror.codeforces.com/contest/253/submission/2728058

        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry, You are saying problem_B?

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 SUBMISSION

    Thnx

    → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    agree.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please be more meticulous?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thx. That is exactly how I was struggling... But your approach is different from ForeverBell's one, which sounds more attractive xD.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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')).

          → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder how to use BFS for problem C without getting MLE, I used BFS but got MLE :(

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes, I made this mistake during the contest. thx

      → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Hello . Can anyone tell me what is wrong with my source ? I can't find it and I know the solution is ok .
2728928

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Basically your queue is not long enough. make it ~~~~~ cp q[10000000]; ~~~~~

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! This was the error which ruined my rating ..

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    use std::queue in future.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I learned that push_back and this kind of function are a bit laggy and I was afraid of TLE

      → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please suggest an improvement for my code for Problem D? I'm getting TLE after implementing the approach mentioned in the tutorial.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

binary search! didn't think of that! very good editorial!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hey can anyone help me with problem D ? if i consider every subtable it will be 400*400*400*400 and i TLE

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why is it right?! O((n^2) * m) = 400 * 400 * 400 = 64 000 000! I have got TL.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The worse complexity of computer is 10^9 a second , so it won't be TLE...

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          are you sure?! 10^9 per second! I don't think so =/ Where i can see this information?

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            sorry ,I'm wrong...

            → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think your code's worst complexity is O((nm)^2).

        → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi, I want to know when the O(NlogN) solution of problem E available? Or is there any code written in that complexity?

Thanks!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do I improve my solution (2820048) to D — Table with Letters — 2? It's getting TLE on test 23.

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Everyone should keep it in mind who use "w+"/"r+" in c++ for opening file. http://mirror.codeforces.com/blog/entry/11335

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me as to why am I getting a run time error in 253 B ( physics practical ) http://mirror.codeforces.com/contest/253/submission/9244115

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My code if running fast enough on my system,still its showing TLE on testcase #1.Plz help. http://mirror.codeforces.com/contest/253/submission/11731622

→ Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In question C, can someone please tell me why the BFS approach in submission 60272417 is giving TLE verdict on testcase 10?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't find file K:\ramdisk\codeforces62\e7ff8bb91dedde9a6d865f706e191786\check-2a7006f85105f62668272971b6545418\run\output.txt invokerId=6f6b8c9223c03ef07c62571aa9bbddf5, location=2032792129

Does that mean tests are removed ?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem also has O(NlogN) solution, which will be described later.

Ten years passed. And it still was not described? I solved the problem in $$$O(NlogN)$$$ but don't sure if it is correct.

→ Reply