ch_egor's blog

By ch_egor, 5 years ago, translation, In English

Thanks for the participation!

1248A - Integer Points was authored by voidmax and prepared by vintage_Vlad_Makeev.

1248B - Grow The Tree was authored by voidmax, cdkrot and prepared by wrg0ababd.

1239A - Ivan the Fool and the Probability Theory was authored and prepared by voidmax.

1239B - The World Is Just a Programming Task (Hard Version) was authored by vintage_Vlad_Makeev and prepared by DebNatkh.

1239C - Queue in the Train was authored by meshanya and prepared by Sehnsucht.

1239D - Catowice City was authored by platypus179 and prepared by budalnik.

1239E - Turtle was authored by voidmax and prepared by cdkrot.

1239F - Swiper, no swiping! was authored and prepared by voidmax.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +52
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +38 Vote: I do not like it

can someone prove that answer for div2c is 2(Fn+Fm−1)?

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

    This was my logic during the contest. Consider each of the cells as a point and we connect cell A and B with an edge if

    1. they're adjacent, and
    2. they have the same color.

    Note that no edges can share their endpoints ( otherwise, a cell should share its color with two or more neighboring cells ).

    Also note that if a cell at coordinate (x, y) is connected with (x, y + 1), then (x + N, y) and (x + N, y + 1) are also connected for all valid integer N ( This can easily be seen by assuming each of their color ). The same holds for the case where (x, y) is connected with (x + 1, y).

    Now we see that there are no cases where there are both horizontal and vertical edges. So our answer is (The number of shapes where there are no horizontal edges) + (The number of shapes where there are no vertical edges) — (The number of shapes where there are no edges).

    Now the number of shapes where there are no horizontal edges are completely determined by the state of the first column by our previous observation. And this number is eactly the N-th fibonacci number times two (The number of the positionings of the edges are F_n, and you can alternate color for each cases).

    The second term is M-th fibonacci number times two similarly.

    The last term is obviously 2.

    Therefore, the answer is (F_n + F_m — 1) * 2

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

      got it, thanks

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

      As per the editorial "this problem equal to the same problem about strip. Answer for the strip is 2Fn." Can any one say which problem is he talking about?can anyonne give the link of this problem

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +55 Vote: I do not like it

        This is a pretty well-known problem.

        "What is the number of sequences of 1 and 2 such that they sum up to an non-negative integer N?"

        The answer is N-th fibonacci number F_N and it's easy to show it inductively.

        First, when N = 0, there is one empty sequence so the answer is 1 which is equal to F_0. Similarly, when N = 1, there is one sequence with exactly one 1 so the answer is 1 = F_1.

        Now suppose N >= 2 and suppose you have proved that the answer is F_k for all k < N. Then, when you consider a sequence summing up to N, the last element is either 1 or 2. Since there are F_(N-1) of them of the first type and F_(N-2) of the second type, the answer for N is F_(N-1) + F_(N-2) = F_N.

        And sorry I don't know any link to this kind of problem.

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

          Thanks,bro for such a beautiful explanation!

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

      The no. of shapes where there are no horizontal edges will be Fn:

      Proof: let cnt[n] will be the answer for n vertices. Assuming we know the answer for k < n; Then,

      Adding a new vertex at the end of the given set of n-1 vertices, there are only 2 new ways for this new vertex — either connect to n-1th vertex or not connect at all.

      cnt[n] = 0, initialized.

      Case 1: make en edge with (n — 1)th vertex, then cnt[n] += cnt[n-2], since for no. of ways with (n — 2) vertices, we can add in all of those ways 1 edge from n-1 to n, without any overlap/shared edge gauranteed (since (n — 1)th and (n-2)th are not connected in counting ans for n-2 vertices only).

      Case 2: make no edge for nth vertex with (n-1)th vertex, then cnt[n] += cnt[n-1]. Since, for all the positions/arrangements of edges with (n-1) vertices, we can add the answer for nth vertex, again ensuring no adjacenet edges since we are not connecing nth and (n-1)th vertex.

      Thus cnt[n] = cnt[n-1] + cnt[n-2]. Hence cnt[n] = Fn.

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

    Some observations:

    • if you repeat some color horizontally, you cannot repeat any color vertically, and vice versat
    • if you repeat some color horizontally, the colors of all cells in the whole 4-columns slice is defined uniquely

    Let's count the number of "horizontal colorings".

    Define $$$d_{k}$$$ the number of horizontal colorings of the first $$$k$$$ rows (no matter how many columns there is).

    There are two options to fill $$$k$$$-th row:

    1. Fill each cell with the opposite color of the upper cell: $$$a_{ij} = \bar{a}_{i-1 j}$$$
    2. Fill each cell with the same color of the upper cell: $$$a_{ij} = a_{i-1 j}$$$

    In addition, you cannot apply the $$$2^{nd}$$$ option more then twice in a row. It's easy to see that other "mixed" variants break the rules.

    Let's assume that the first row is filled in some correct way. Therefore, the number of horizontal colorings $$$d_{k} = d_{k-1} + d_{k-2} = f_{k}$$$ The same formulae stands for vertical colorings.

    The only coloring that presents in both of vertical and horizontal colorings is pure chess coloring.

    And you need to multiply the result by 2 because you defined the first row in some fixed way and colors can be the opposite.

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

      thanks

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

      you made the question worthy.

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

      If color is repeated horizontally, then the whole 3-columns slice would be filled right? so if you repeat white we can fix 3 columns wwb , the fourth column can be b or white. May I know how it is 4 columns?

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

        If you have ...ww... then you must place the black both before and after the repeat: ..bwwb..

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

      Nice explanation

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

      I am finally got this problem solution idea thanks a lot :)

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

    Here's a late reply but maybe people who will see this editorial in the future will find it helpful.

    Consider that you have a valid coloring for the first row, you will notice that the coloring of this row enforces the coloring of the entire grid. Similarly for the first column. We have (-1) since the case where white and black alternates in each row and in each column is counted twice (with F(n) and with F(m)). **** Answer = T(n,m) = 2 * (F(n) + F(m) — 1)

    Where F(x) is the number of ways we can fill a (1 by x) grid using blocks of size 1x1 and blocks of size 1x2. If x >= 2, we can choose to put a 1x1 block at the beginning (we're left with F(n-1) choices) or put a 1x2 block at the beginning (we're left with F(n-2) choices) -> F(n) = F(n-1) + F(n-2) -> Fibonacci!!

    (Note: Equivalent to the problem where you're asked to the find the number of ways to climb n stairs if you can at each step go to the next level or to the one next to the next level).

    We multiply the factor (F(n) + F(m) — 1) by 2 since flipping black and white will keep the grid coloring valid.

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

Can any one Explain div2 C problem more clearly.

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

Div2 C I thought of it this way during the contest but Savior-of-Cross 's approach is more better and straight forward.

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

$$$O(n)$$$ solution to Div2B: Since the range is only $$$10^4$$$, use element counting to sort or find the median?

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

    Can you please elucidate a bit?

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it

      Look up "counting sort". Basically:

      1. Make a $$$cnt$$$ array with maximum index $$$\geq \max(a)$$$
      2. Iterate through array $$$a$$$, incrementing $$$cnt[a_i]$$$ each time
      3. You can now sort $$$a$$$ by iterating through the counts in $$$cnt$$$, or directly find the sums of the two sets desired.
»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Here is my approach for D.

  • All indices from 1 to $$$n$$$ have to appear in our solution. This might sound obvious but it's probably the most important observation.
Spoiler
  • Try to convert the bipartite graph of residents and cats to a graph of only residents. Cats are useless. (I'm a dog person)
Spoiler
  • If we pick a resident, who else must we pick?
Spoiler
  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it -8 Vote: I do not like it

    Why do we need to pick SCCs?

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

      If you pick a node $$$x$$$, you'll have to pick all the nodes that can be visited from $$$x$$$. Our goal is to pick a set of nodes such that starting from any node in this set, we can't visit a node that is not in this set. Think about the easy case where the graph has no cycle, we can simply pick a node without outgoing edge. If the graph has cycles, we can compress it into a new one without cycle by finding SCCs.

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

Can someone tell me why I keep getting Runtime Errors on test 10 of 1239A? I thought I fixed REs by changing the recursion limit but maybe not. Test 10 is (1, 100000).

import sys
sys.setrecursionlimit(999999999)
def f(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return f(n-1) + f(n-2)
a, b = tuple(map(int, input().split()))
print(((f(a)+f(b)-1)*2)%(10**9+7))
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    your recursive tree goes exponentially, and that probably causes memory overflow

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

    Time complexity of recursive Fibonacci is exponential.

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

    I demand you to stop RIGHT THERE NO STOP You're calculating nth fibonacci number explicitly NO STOP

    MOD IT EVERY TIME YOU CALCULATE PLEASE

    Also you did not use memoization try this

    M = 10 ** 9 + 7 # MODULO
    array = [0] * 100010 # Extra because im bad
    array[0] = 1
    array[1] = 1
    # array[2] = 2
    def f(n):
        if array[n] == 0:
            array[n] = (f(n &mdash; 1) + f(n &mdash; 2)) % M
        return array[n]
    
    # To initialize, don't use sys.setrecursionlimit(99999). It's bad.
    for i in range(1, 100010):
        f(i) # Calculates the value but doesn't do anything with it
    # Now you can do
    # a, b = tuple(map(int, input().split()))
    a, b = map(int, input().split()) # No need tuple, python is smart :)
    print (( (f(a)+f(b)-1)*2 ) % M)
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thank you so much for helping me! Now I can solve recursion problems without getting TLEs or REs :)

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

        No problem lol seems like my ranting explanation didn't get any upvotes :P

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

          I think it would've got more than a dozen upvotes if the ranting part didn't exist lol

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

In D1 ,How can we arrive at that formula for cyclic Shifts?

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

Why in D1 the answer is minimum prefix balaneces count.

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

    We reduce $$$cnt$$$ if we see "(" and increase $$$cnt$$$ if we see ")".

    Let's calculate it on example: "))()(())(("

    Cnt: [-1, -2, -1, -2, -1, 0, -1, -2, -1, 0]

    The minimum of all $$$cnt$$$ (-2 here) is when we close all levels of brackets. Then we increase it again (opening new levels) and closing them, checking if we again closed all levels (when $$$cnt$$$ = minimum).

    Also we should check if last $$$cnt = 0$$$ (it means that we find opposite brackets for starting).

    Hope you understand it better)

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

      You are supposed to swap reduce(decrease is better) and increase in the first line of your reply.

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

Is there any resource where I can learn about brackets and their corresponding properties?

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

the worst editorial ever

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

    It is written on higher level than most of div2 participiants could understand.

    C editorial should be extended as for me.

»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it
Another way to thing about div1D:
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Awesome! Didn't know about the problem you refer to, It turns that giving problems for contests is very useful sometimes.

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

      Didn't know about the problem you refer to

      The theory of SAT and specifically 2-SAT problems is well-known. It's not "the problem" any more than BFS.

      This isn't some kind of special case of 2-SAT. It's direct textbook 2-SAT, you don't even need to know that for each condition/edge "if x then y", you need a condition "if !y then !x" in the graph too, since they correspond to different endpoints of an edge, so the symmetry is clear. The only thing you need to know is that it behaves "nicely" when you compress SCCs — either there's no solution or any greedy assignment works.

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

div2-Queue in the Train

Why is my method wrong?

wa in fourth test point

//Sort by time in ascending order
    sort(a,a+n,cmp);
//now means now's time
    ll now=0,i=0;
//que is a heap sort by person's position
    while(i<n||!que.empty()){
//if someone in now's time needed water, push him.
        while(i<n&&a[i].val<=now)que.push(a[i++]);

//in now's time, no one need water, so the time jump to earliest time sush that have some one in que. 
        if(i<n&&que.empty())now=a[i].val;
        while(i<n&&a[i].val<=now)que.push(a[i++]);
        PP x=que.top();que.pop();
        now+=p;//p equals to the problem' p.
        ans[x.pos]=now;
    }
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the meaning of line This problem is same problem about strip...

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

    Let's fill the first row in some correct way. Then, the way you fill all the other rows is forced (this is the key observation for the problem). So, to get the answer to the problem you actually just need to find the number of ways to fill the first row (the first "strip").

    There are some technicalities. Let's assume that the top left cell is always white. We will need to multiply the eventual answer by 2 to account for symmetry (when the top left cell is black).

    Let $$$f(k)$$$ be the number of ways to fill a "strip" of length $$$k$$$.

    1) We fill the first row. The number of ways for this is $$$f(n)$$$. All other rows depend on the first row.

    2) We fill the first column. The number of ways for this is $$$f(m)$$$. All other columns depend on the first column.

    3) Notice that both in 1) and 2) we count the "chess board" case, where the color of every cell is different to all its neighbors'. This is why we subtract 1, because we want to count each board state exactly once.

    We now have a total of $$$f(n) + f(m) - 1$$$ ways. We multiply by 2 to account for the case where the top left cell is black (and thus flip the colors of all cells). So the answer is $$$2*(f(n) + f(m) - 1)$$$.

    The only thing left to do is to find out how to calculate $$$f(i)$$$ for some $$$i$$$. I think this is literally one of the simplest ways to use dynamic programming.

    $$$f(0) = 1$$$

    $$$f(1) = 1$$$

    $$$f(i) = f(i-2) + f(i-1)$$$ for $$$i \geq 2$$$

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

      Brilliant explanation.

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

        Amazing explanation. But the number of ways for filling the first row should be f(m) since the length of strip is m , not n.

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

      the thing i was confused about is that how do you make sure that f(n) and f(m) don't coincide on the first cell (1,1)? for example, if you fill the first row, then that cuts off like half of the options for the first column (because (1,1) is now forced white or black). and i understand parity comes into play so multiply by 2, but still, won't it still cut off half of the options despite parity?

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

"So now we need to split our set into two of equal size, so that the maximum sum is smallest possible."

This statement is misleading, the first time I read it I thought you might mean that the optimal solution is to split the 2n items into to groups, each consisting n items, one of which is the first line and the other is the second line of the answer.

However, this is untrue.

Consider the test case

4
0 3 4 4
4 4 3 2

This is the optimal solution while the way to split these into two set of equal sum would lead to

4
0 4 4 4
4 3 3 2

Which answer is 14, larger than 13 in the former case.

Please look into it ch_egor

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

    You should split 2n-2 items. Two smallest will be start and finish.

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

      Yeah, you are right. It's just the solution said nothing about that.

      I figured it out myself today though, you could see my submissions.

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

How to solve Div2B in O(n)

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

    It's overkill because you can just sort the elements in $$$O(n log n)$$$. But since $$$a_i \leq 10000$$$ you can use counting sort and solve it in $$$O(n + maxa)$$$.

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

The editorial for E is wrong!

So now we need to split our set into two of equal size, so that the maximum sum is smallest possible.

No, because our path doesn't have $$$N$$$ elements. It has $$$N+1$$$, the top left and bottom right element are always included, and there are just $$$N-1$$$ differences $$$x_{i+1}-y_i$$$, which is obvious from the shifted first index! Alternatively, we want two sets with equal size $$$N+1$$$, but they're not disjoint!

We can do knapsack DP e.g. if the states contain the difference (cost of our path) — (cost of the rest) without the top left and bottom right element, and if their values are (cost of our path) — (cost of the rest). However, we can do better and add bitsets.

The problem with bitsets is that we need the values of states to be 0/1, so it's not straightforward. Let's sort all the elements in decreasing order. The top left and bottom right elements can be the smallest two of elements chosen for our path, since that maximises the chance of our path being taken. That means we'll have some state where we've chosen $$$N-1$$$ elements for our path out of the first $$$i$$$, their sum is $$$s$$$, then we want to choose the $$$i+1$$$-th element for our path too, and the last element we'd want to choose is $$$j > i+1$$$. Our path has sum $$$a_j + a_{i+1} + s$$$, the other path has sum $$$\sum a - s$$$ and we want their difference to be non-negative: $$$2s \ge \sum a - a_j - a_{i+1}$$$. Obviously, we need just the smallest such $$$s$$$.

Now we can do knapsack DP with bitsets; the states are obviously ($$$i$$$, $$$s$$$, number of elements that summed up to $$$s$$$) and their values are just if it's possible to reach them. For each $$$i \ge N-1$$$, we then try all $$$j$$$, try to find the smallest $$$s$$$ that satisfies the above condition and if it gives the best answer so far, construct a solution. The time complexity is the same, except with a much better constant.

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

Can someone please explain Div 2 D(Hard)? I could not understand the polyline thing in the editorial. It would be really helpful if someone could elucidate it a bit with an example.

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

For div1F,what if a way between nodes-1 on nodes-2 have more than one edge between one node-1 and nodes-2?

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

Can someone tell if my understanding of Div2C/Div1A is correct?

If there exist two adjecent cells with same color then one of two cases can happen: 1. Adjacent cells with same color are vertically adjacent. 2. Adjacent cells with same color are horizontally adjacent.

Both cases cannot happen for the same board — if there is a strip such that case 1 holds true for it, then the rest of the board can either follow chessboard coloring, or case 1 coloring — but not case 2 coloring. Likewise for a strip colored according to case 2.

No. of ways for case 1 is $$$F_n$$$, and for case 2 is $$$F_m$$$. Since only one of these two cases can happen for a particular board, total ways = $$$F_n + F_m$$$.

But the 1 case where full board is colored according to chessboard coloring in counted in both $$$F_n$$$ and $$$F_m$$$, so we subtract it from either one, to get $$$F_n + F_m - 1$$$.

For each of the $$$F_n + F_m - 1$$$, we can flip colors across entire board, so final answer = $$$2(F_n + F_m - 1)$$$.

Is this correct?

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

In div2D1, It's written/hinted in the tutorial that O(n^3) works but system testing giving TLE for such solution like I have implemented here

Personally, I also believe that n^3 (125000000) is too large and should get TLE but then why is it written in editorial as such?

Thanks in advance!

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

    My solution O(n^3)

    As you can see it passed with 732 ms. I dont see much (or any) difference in our solution. So i guess, please submit the solution again with

    #pragma GCC optimize("Ofast")
    

    at first just as i used and also change endl to \n (it also saves time)

    if u still get tle, try chaning cin and cout to scanf and printf respectevly. (Although i dont think TLE will come)

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

In div1 Problem A, at 2*(F(n) + F(m) — 1) formula we are subtracting 1 because by adding F(n) , we have already covered one row ... is that so ??

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

    no...i think its beacuse chessboard case is included in both (no two same colored adjacent cells)

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

Thank you. It was excellent information.

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

I found this video on YouTube for div2C.