Sereja's blog

By Sereja, 11 years ago, translation, In English

426A - Sereja and Mugs

Lets count the sum of all elements Sum and value of the maximal element M. If Sum - M ≤ S then answer is yes, otherwise — no.

426B - Sereja and Mirroring

Lets solve problem from another side. We will try to cut of matix as many times as we can. Cut means operation, reversed to operation described in statement. To check, can we cut matrix we need to check following conditions:
1). n mod 2 = 0
2). ai, j = an - i + 1, j for all 1 ≤ i ≤ n, 1 ≤ j ≤ m.

425A - Sereja and Swaps

Lets backtrack interval on which will contain maximal sum. To improve our sum we can swap not more then k minimal elements from the interval to k maximal elements that don't belong to interval. As n isn't big we can do it in any way. Author solution sort all elemets from interval in increasing order and all elements that don't belong to interval by descreasing order. We will swap elements one by one while we haven't done k swaps and we have some unswaped elements in first set and we have some unswaped elemets in second set and swap is optimal(we will optimize the answer after this swap). Author solution works in time O(n3·log(n)).

Is there some ideas how to solve this problem in time O(n) or O(n·log(n)) ?

425B - Sereja and Table

Note, that if we have two arrays x[1..n], 0 ≤ xi ≤ 1 and y[1..m], 0 ≤ yi ≤ 1, then described matrix can be showed as next one: ai, j = xi xor yj.
If n ≤ k, then we can backtrack array x and using greedy find best y. Otherwise there will be atleast one i, such that we will not change any cell in row number i. So we can simply bruteforce some row and use it like x. Then we use greedy and find y. From all possible rows we choose most optimal. Such row will be as number of mistakes is lower then number of rows, so it isn't possible to have atleast one mistake in each row.

Greedy means next algorithm: for every element of y we will look, will it be better to choose it like 0 or 1. To find better choise, we will count number of different bits in x and current(lets it be j) column. If number of different if lower then count of same cells we will set yj = 0, otherwise yj = 1.

425C - Sereja and Two Sequences

In thgis problem we will use dynamic programming: dpi, j — minimal pozition of deleted element in second array, such that we have made first operation j times and have deleted not more then i elements from first array.

Lets decided how to calculate transfers. Standing in pozition dpi, j we can change nothing and go to pozition dpi + 1, j, by other words make transfer dpi + 1, j:  = min(dpi + 1, j, dpi, j). What happens when we make first operation with fixed prefix(by i-th element) in first array? We should find element in second array with number greater dpi, j and value equal to ai, lets its pozition is t, so we need to make transfer dpi + 1, j + 1:  = min(dpi + 1, j + 1, t).

How to find required element quickly: lets just do vector of pozition in second array for all different elements that contains in second array. Then we can simply use binary search.

425D - Sereja and Squares

Lets line x = k contain not more then points. Then for each pair of points on this line (lets it be (k, y1) and (k, y2)) check: is there squere that contain them as vertexes. So we should check: is there(in input) pair of points (k - |y2 - y1|, y1) and (k - |y2 - y1|, y2), or pair (k + |y2 - y1|, y1) and (k + |y2 - y1|, y2).

Lets delete all watched points, and reverse points about line x = y. Then each line x = k will contain not more then points. Will solve problem in the same way.

Now we should learn: how to check is some pair of points(on one vertical line) in input. Lets write all of this pairs in vectors. Each vector(for every line) will contain pairs that we should check on it. Suppose, that we check it for line number k. Lets mark in some array u for all points with x-coordinate equal to k uy = k. Now to check is our pair with y-coordinates (y1, y2) on line we can simply check following condition: uy1 = uy2 = k.

425E - Sereja and Sets

First, lets look at F(S). First, we sort all intervals by second coordinte and then go by them in sorted order. And if current interval don't intersected with last taken to the optimal set, we get our current to the set.

Our solution will be based on this greedy. Solution of the problem is next dynamic:
1). number of position of second coordinte of interval
2). number of intervals in good set
3). second coordinate of last taken interval to the optimal set

How should we make transfers? Lets note that when we know dpi, count, last we can change last by i, or not change at all. Lets look what happens in every case. In first case last is changed by i, so we should take to optimal set atleast one of the inervals: [last + 1, i], [last + 2, i], ..., [i, i], number of such intervals i - last, number of ways to get at least one of them is 2i - last - 1. All other intervals: [1, i], [2, i], ..., [last, i] we could get as we wish, so we have 2last ways. So total number of transfers from dpi, count, last to dpi + 1, count + 1, i is (2i - last - 1)·(2last). If we count number of transfers from dpi, count, last to dpi + 1, count, last, we can simply use number 2last(as described early).

Also we shouldn't forget about trivial case dpi, 0, 0.

So now we have quite easy solution.

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
11 years ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

D can be solved without using sqrt(n) in a solution and dividing lines into large and small. This algorithm works: Fix upper right corner (x0, y0). We have to choose second corner of our square. We have two sets of candidates those of form (x, y0) where x < x0 and those of form (x0, y) where y < y0. Let's iterate over all candidates from smaller set, which will result in O(n^(3/2)) algorithm.

I think that many contestants implemented that solution using this optimization without any knowledge that this will in fact improve complexity and got accepted :P. Frankly saying I didn't know the proof too, but I knew that problem and solution earlier :P.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    If I get you clearly, to get your O(N3 / 2) you have to use some kind of hash_set. Or how do you want to check third and fourth square corners in O(1) time?

    Thanks to this comment I got such solution AC with unordered_set (C++ hash_set). But same code got TL with C++ set (binary search tree).

    So did you mean to use hash_set?

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      No, I did't use hash_set or structures like that. We had to answer queries like "Does there exist point (xi, yi)?" and I did it offline. When I have k points with constant coordinate x equal to a and I got l points which I want to check if they exist I can simply do this in complexity O(k + n). Coordinates are small, so I don't need even this lists of points to be sorted.

      If you want to see my code (which is in fact ugly, because of big quantities of copy-paste :( ), here it is: http://codeforces.net/contest/425/submission/6492350

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

      You can use vector instead of uset, for that you only use uset to store ordered elements. and the complexity is O(n*sqrt(n)*log(n)) I think. Here is my submission: http://codeforces.net/contest/425/submission/6573893

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry for mis-post. You can use vector instead of uset, for that you only use uset to store ordered elements. and the complexity is O(n*sqrt(n)*log(n)) I think. Here is my submission: http://codeforces.net/contest/425/submission/6573893

»
11 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

"Is there some ideas how to solve this problem in time O(N) or O(N * log(N)) ?" My solution for Div1 A (Div2 C) runs in O (N*(k^2)) http://codeforces.net/contest/425/submission/6494646

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

    Can you explaint what the state dp[i][j][k][l] means?thx.

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

      Sure

      At any given index ind (0<=ind<n), we have 3 states (st)

      0 means we have not started the targeted interval yet

      1 means we have started the targeted interval, but did not close it

      2 means we have started the targeted interval and closed it

      according to this values, we can decided whether to use the element at the current index or not.

      Skipping an element within the target interval increases the value (up)

      Considering an element outside of the target interval increases the value (dw)

      for a valid solution, st must be 1 or 2, and up = dw

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

        elegant algorithm. But I think you should not initialize the dp[][][][] with -1,since maybe some answer is actually -1.

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

          Yes, you are right, that must be a bug.

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

    My solution for Div1/C runs in O(N2K) using DP. 6490996

    But it seems that runs faster than you for the testcases 31 ms < 93 ms

    Do you have any description?

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

    Thanks for solution. I didnt get the greedy one on the tutorial and it is was a good practice for dp.

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is it possible to see any valid implementation of 425D - Sereja and Squares of author's way solution? Thanks

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C. Sereja and Two Sequences can the second action move empty sequences? can you explain the second sample?

»
11 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

C. Sereja and Two Sequences

TEST #2
3 4 3006 1000
1 2 3
1 2 4 3

ans = 2
TEST #4
4 3 100000 1290
75575 42837 79021 96022
42837 79021 96022

ans = 3

can anyone explain it for me ? I'm not very sure about the problem.

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

    You can use operation 1 only if last element of prefixes is the same.

    For test 2, you should do first operation 1 with prefixes (1) and (1), getting

    2 3
    2 4 3

    Then you do operation 1 again with prefixes (2) and (2)

    3
    4 3

    As you removed 4 elements from the sequences, you can now do operation 2 with a cost of 4 energy points, for a total of 1000+1000+4=2004 energy points. Note that you cannot remove (3) and (4 3) at the end, because you wouldn't have enough energy to perform operation 2 at the end (the cost would be 1000+1000+1000+7=3007). You NEED to do operation 2 as last operation.

    For test 4, you can remove all elements using operation 1 three times (the first is on (75575 42837), (42837)), and you have enough energy to do it.

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

      thanks. "The second action is worth the number of energy units equal to the number of elements Sereja removed from the sequences before performing this action." I misunderstood.

»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain this solution 6491956 to div1 E?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is it Giving WA on problem c Div2??

Please help!!

6500849

  • »
    »
    11 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Line 59:

                while(_in < in && _ot && k--){
                    int a = x[_in++],b=y[_ot--];
                    res+=(a > b)?a:b;
                }
    

    You won't iterate over last element of y, so you should check _ot >= 0, not _ot > 0.

    Submit with _ot >= 0: 6501201

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

So what is the final time complexity of problem B Div 1 (D Div 2) "Sereja and Table"?

»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can you translate the Russian language into English?

»
11 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

It was also possible to solve Problem 425B — Sereja and Table with backtracking. First of all, the required condition for the table holds if and only if for each 2x2 square inside the table it is true that either the number of 1s is 0, 2 or 4. So we start with finding all the bad squares and putting them into a set. Then try all possible changes of a single bad square (flipping a single number inside it). Since we flipped a single number, only four squares that intersect that number might have changed from bad to good or vice versa, so we should only check them. With a simple optimization this passes the time limit: 6507534

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

What does it mean by "Watched Points" int "425D — Sereja and Squares", http://codeforces.net/contest/425/submission/6573664 Here is my solution, and get WA #25. Can someone help me? Sincerely.

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

    I think by watched points, the author means the points which has already been processed.

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

Can someone re-explain the algorithm of 425B — Sereja and Table? I do not understand it at all.

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Could someone please explain why the solution to Div1B Sereja and Table works?