ch_egor's blog

By ch_egor, 4 weeks ago, translation, In English,

Thanks for the participation!

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

1248B - Grow The Tree was authored by voidmax, _kun_ 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 V--gLaSsH0ldEr593--V 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 Nebuchadnezzar.

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

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

»
4 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

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

  • »
    »
    4 weeks 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

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

      got it, thanks

    • »
      »
      »
      4 weeks 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

      • »
        »
        »
        »
        4 weeks 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.

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

      Thank you so much got it!

  • »
    »
    4 weeks 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.

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

      thanks

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

      you made the question worthy.

    • »
      »
      »
      4 weeks 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?

      • »
        »
        »
        »
        4 weeks 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..

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can any one Explain div2 C problem more clearly.

»
4 weeks 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 Mahotsukai 's approach is more better and straight forward.

Hint1
Hint2
Hint3
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Great explanation.

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

    How to find F[m] or F[n] i.e total no of ways in which we can assign colors to the first row.

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

      F[m] represents the mth fibonacci no.We get the result from the strip problem explained by Mahotsukai above

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

    detailed analysis

»
4 weeks 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?

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

    Can you please elucidate a bit?

    • »
      »
      »
      4 weeks 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.
»
4 weeks 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
  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it -8 Vote: I do not like it

    Why do we need to pick SCCs?

    • »
      »
      »
      4 weeks 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.

»
4 weeks 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))
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    Time complexity of recursive Fibonacci is exponential.

  • »
    »
    4 weeks 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)
    
    • »
      »
      »
      2 weeks 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 :)

      • »
        »
        »
        »
        2 weeks 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

        • »
          »
          »
          »
          »
          2 weeks 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

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

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why in D1 the answer is minimum prefix balaneces count.

  • »
    »
    4 weeks 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)

    • »
      »
      »
      4 weeks 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.

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

      Can you please explain the polyline part?

»
4 weeks 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?

»
4 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

the worst editorial ever

  • »
    »
    4 weeks 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.

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

liked the second problem

»
4 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it
Another way to thing about div1D:
  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

»
4 weeks 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;
    }
»
4 weeks 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...

  • »
    »
    3 weeks 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$$$

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Brilliant explanation.

      • »
        »
        »
        »
        2 weeks 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.

»
4 weeks 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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

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

How to solve Div2B in O(n)

  • »
    »
    3 weeks 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)$$$.

»
4 weeks 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.

»
4 weeks 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.

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

      What cases are we talking about in editorial? What are the indices of the brackets that we are switching in the editorial, in 4th and 5th para?

»
3 weeks 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?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

64369202 Sorry, I want to know how this should be changed. What it shows is----Runtime error on test 4