Aleph-0's blog

By Aleph-0, 12 days ago, In English,

1153A - Serval and Bus

Author: Serval, preparation: bzh

Editorial

1153B - Serval and Toy Bricks

Author: Serval, Preparation: bzh

Editorial

1153C - Serval and Parenthesis Sequence

Author & preparation: Serval

Editorial

1153D - Serval and Rooted Tree

Author & preparation: bzh

Editorial
Code
Another Solution
Code for Another Solution

1153E - Serval and Snake

Authors & preparation: Serval, bzh

Editorial
Bonus: How to save more queries?

1153F - Serval and Bonus Problem

Author: Serval, preparation: Serval, bzh

Editorial
Code

UPD: We fixed some mistakes and added another solution for D.

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

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

Aim of Q.C is just to make subset x = s[1...[s]-2] a perfect parenthesis sequence, with s[0] = '(' and s[|s|-1] = ')'. This is because if x is balanced, then all strict prefixes are gauranteed unbalanced, but still s[0]+x+s[n-1] will become balanced.

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

    I thought the same but got WA on Test Case 6. What about yours?

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

      See this comment. I too was closing brackets as soon as possible. But greedy approach should have been other way around (making brackets open first as much as possible). Refer this comment for better understanding : https://codeforces.com/blog/entry/66539?#comment-505352

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

      I use a greedy approach , Let the first '(' match the last ')' ,and we just remove the first char and the last char ,then if the remaining string can be a Legal sequence , then it works,and also use greedy approach to replace '?',first we shoule cale the numebr of '(' in '?' ,then we should replace '?' with '(' First ,and the rest we replace with ')', Be careful with the illegal solution.

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

    try this test case: 6 ??)?)) output: (()()) wa: :(

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

      why output: (()()) is WA ? I think it is correct

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

        It seems like my english is bad, I meaned that with this test, right answer would be (()()), and if your code gave :(, it would be considered as a wrong answer, sorry for my bad

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

          OK , I think my approach will output the correct answer

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

Thanks for the fast editorial!

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

Can someone explain D — Serval and Rooted Tree more clear, sorry for my stupidness

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    For each non leaf node, we either have a max node or a min node. If we are at a max node, then we can assume our answer will come from the child with the highest upper bound. But if we are at a min node, then we need to add up all the upper bound. The upper bound at the leaves are 1 (meaning we take the 1st highest node of its subtree which is itself). For a min node with 2 leaf child, the upper bound is 2 (meaning we need 2 high value K's to maximize that node)

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

      What do you mean, when you saying "upper bound". Is this a maximal number, what can be written in non leaf node? Can you explain idea in more detail, why we need upper bound for all nodes?

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

        The upper bound on a node is the maximum value that can be achieved with optimal arrangement of it's subtree.

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

    for each vertex, try to minimize the number of numbers which the number on this vertex must be less than (I mean '<'). Try to find this answer for all the vertices and the answer for the no.1 vertex will be used to make the final answer for this task, final answer is (number of leaves)-(answer for question I mentioned above for no.1 vertex). Hope you get it. how to get this idea: by seeing that the number on each vertex must be less than some numbers on other vertices, it depends on what type of restriction (min or max), try to minimize this number for all vertices to get better answer (bigger number for vertex no.1)

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

In pronlem E , we can check all rows and columns in a random order . In worst case , the expect number of queries is about 1020.

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

Thanks for the editorial. I was trying to solve C by trying to maintain difference of 1 between number of open and closed brackets and greedily marking a '?' as '(' or ')'. Kept failing on pretest 6 and could see on Discord after contest that a few more were failing on that pretest.

I guess another intuition of why we can make as many '?' = '(' in the beginning is that there is no way it will make the sequence unbalanced as we can always have ')' at the later half of the sequence to balance it out. My solution, in contrast would have failed for case like "((?)))" as it would have changed the first '?' to ')'.

BTW Then I think there can't be an online solution to the problem ? Am I right ?

Thanks again !

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

    I was facing the same problem but I still do not understand how closing brackets as soon as possible leads to failure in Testcase 6. Could you please explain your insights?

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

      (??)

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

        I used this approach by excluding first and last characters. In the middle part, I tried to close the brackets as soon as possible and in the end ensured that if middle part is legal then check if first character is ( and last character is ).

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

      ( ( ? ) )

      Your code I guess will be assigning ? as ).

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

        There are two sweeps. It first tries to close the brackets while sweeping right to left and if it does not generate a legal sequence, it tries a left to right sweep. If both fail then, :( is printed. Nonetheless, your example does not seem to have any valid answer. Does it?

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

    try this: ??)?))

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

      Gives this output (()()). Please take a look at my solution.

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

        a condition to maintain a valid sequence is make sure num of '(' >= num of ')' so )()( is fail for the first character when num of ')' is 1 and none of '(' character

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

Problem D and E are really nice! We need more div2 contests like this ;)

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

In the editorial for 1153E — Serval and Snake,

"If the head and tail are in different columns, we can find two columns with odd answer and get them. Then we can do binary search for each of those two columns separately and get the answer in no more than 998+10+10=1018 queries totally."

Where does the 998 comes from? Isn't it that in the worst case you will have to go through 999 columns?

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

    Oh, you are right. It is 999. We've changed constraints several times and made a mistake in changing that number in the tutorial. Sorry for my mistake and thanks for your correction. Fixed now.

»
12 days ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

I hardly understand anything from D's editorial :// ,

Can anyone explain : ,

1, What dp[i] means ? ,

2, What does "the number on i is one" mean when we dont know the specific 'x' ? ,

3, Why the answer is k + 1 — dp[1] ?

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

    dp[i] means that the maximum number on node i is the dp[i]-th greatest number of leaves within subtree of i. Updated in the tutorial now and thanks for your questioning.

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

      But can you please explain why this solution works ??

      What is the proof behind the dp solution??

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

        If you meet a max operation, then it is the minimum number of all dp values of its direct children. And if you meet a min operation, then it is the sum of dp values of its direct children.

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

      dp[i] means that the maximum number on node i is the dp[i]-th smallest number of leaves within subtree of i.

      according to ur comment, if dp[root] = 1, the maximum number on root node is the first smallest number of leaves which is 1. But the k+1-dp[root] gives k. We get a contradiction.

      I think 'smallest' should be 'greatest', which makes sense

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

        yes, you are right. Fixed and thanks.

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

    I have added another solution so you can try to understand another one. :)

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

      But how do you know where to place the values < x and the values >= x ?

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

      Can you explain the min case of the second solution given in editorial of Problem D?

      For all sons or children v of u, we number the first $$$f_{v}−1$$$ leaves in the subtree of v first according to the optimal arrangement of the node v. And then no matter how we arrange the remaining numbers, the number written in u is $$$1+\sum_{v\ is\ a\ son\ of\ u}f_v$$$. This is the optimal arrangement.

      What is the intuition behind the first $$$f_{v}−1$$$ leaves?

      What is the proof that this leads to optimal arrangement?

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

        According to the optimal arrangement in the subtree of $$$v$$$ ($$$v$$$ represents all children of $$$u$$$), we know that the largest possible number written in node $$$v$$$ is $$$f_v$$$. And in a possible arrangement, the number written in node $$$u$$$ is the minimum of what the $$$f_v$$$-th leaf numbered in subtree of $$$v$$$. So our goal is to find an arrangement to make the number written in the $$$f_v$$$-th leaf as large as possible in each subtree of $$$v$$$. And bacause of the optimal arrangement in the subtree of $$$v$$$, we have to make sure that, for any two leaves $$$a$$$ and $$$b$$$, if $$$a$$$ numbered less than $$$b$$$ in $$$v$$$'s arrangement, $$$a$$$ should be numbered less than $$$b$$$ in $$$u$$$'s subtree, too. Let's consider how many numbers less than $$$f_v$$$ we can arrange first to make all $$$f_v$$$ as large as possible, so the answer is $$$\sum_{v\text{ is a son of }u} (f_v-1)$$$. And no matter how we arrange the next number, there will always be a $$$v$$$ that the $$$f_v$$$-th leaf in $$$v$$$'s subtree is numbered, and it becomes the minimum of what the $$$f_v$$$-th leaf numbered in subtree of $$$v$$$. So this is an optimal way to arrange the numbers.

        And sorry for the mistake I written in the editorial, it is $$$\sum (f_v-1)$$$ instead of $$$\sum f_v$$$, I will fix it. :)

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

    The question still remains intact.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I got accepted and I'll share how I understood it,

    dp[i] = the minimum value you need to maximize node i, for ex : if dp[i] = 3, you'll need {k-2,k-1,k} to maximize node i,

    if the operator is max, the child which uses the fewest value will be the optimal, so dp[i] = min(dp[child[i]]),

    if the operator is min, dp[i] = sum(dp[child[i]), because no value can concide,

    so the answer is numbers of leaf — dp[1] + 1

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

      But how will you give the values to leaves in this case ??

      This will seriously help me understand the problem

      Any help will be appreciated

      11

      1 1 1 0 0 1 1 1 1 1 1

      1 1 2 2 3 4 4 5 5 5

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

      Why exactly do we need the +1?

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

    You can refer link
    this solution is easy to understand.

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

In Q C test case : 14 ((?)))(((??))) in this example we need to replace 2 ?'s with '(' and 1? with ')' with reference to the editorial, we should first add 2'(' to the string and then 1')' so ans =((()))(((()))) but in this case sequence s1...s6 is correct parenthesis.? Can anybody explain the editorial more clearly

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

    We should check it whether a correct answer or not after we construct the possible answer.

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

      So R u telling me to go for backtracking if the answer found is wrong. I am not getting how you are deciding that we should put ')' or '(' such that the complete sequence is correct but none of the prefixes.

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

        The way they place the braces is the greedy way that should give the correct answer. If this greedy way doesn't give the correct answer, there is no way you can place the braces right.

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

Can someone tell me how to find the bus route in O(1)? (for Problem A)

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

    time = s + ( ( (t-s+d-1)/d ) * d );

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

      Yeah, I saw it in some sources but I don't understand how it works.

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

        t-s is the duration between arrival time and initial time. But the bus need not come at the arrival time exactly. So, we add d to this time in order to get any time after arrival. Now we need to find the number of trips within the duration t-s+d.

        In order to find it, we subtract 1 form t-s+d because we don't need any trips in the last minute. So, we get number of trips=(t-s+d-1)/d. Each trip takes d time. Finally, time will be = s + ( ( (t-s+d-1)/d ) * d )

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

          For problem A, can someone explain , how to come up with this? time = s + ( ( (t-s+d-1)/d ) * d );

          Also, is it not possible to come up to this using aritmetic progression??
          Because I tried to do this:

          =>   s-(n-1)d >= t
          =>   (n-1)d >= t-s
          =>   (n-1)  >= (t-s)/d
          

          but this gives wrong ans..

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

            My approach which TLE'd has been

            if s > t:
              first_bus = s
            else:
              first_bus = s
              while (first_bus<t): first_bus += d
            

            This will give you the first bus for any (s,d) pair but its no efficient enough to pass within the time limit

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
            Rev. 6   Vote: I like it 0 Vote: I do not like it

            Let $$$time$$$ be the minimal time you need to wait for a bus.

            If $$$s\geqslant t$$$, then $$$time=s$$$. Else, you need to wait $$$x$$$ more seconds until the next bus comes. So basically, you have $$$time=s+x$$$.

            Of course $$$time\geqslant t$$$ so $$$s+x\geqslant t$$$. Moreover, you get on the bus right when the bus comes, so $$$x$$$ is divided by $$$d$$$. The problem become: Find the smallest $$$x$$$ satisfies that $$$s+x\geqslant t$$$ and $$$x$$$ is divided by $$$d$$$.

            Now we can write $$$x$$$ as $$$y\times d$$$ where $$$y$$$ is an integer. Condition $$$s+x\geqslant t$$$ can be written as $$$s+y\times d\geqslant t$$$, or $$$y\geqslant \dfrac{t-s}{d}$$$. We need to find the minimum $$$y$$$ that satisfies that condition. Here, $$$|\dfrac{t-s+d-1}{d}|$$$ is the answer (let $$$a$$$ be a real number, $$$|a|$$$ is the maximum integer that smaller than $$$a$$$), and when you save the result of the operation (t-s+d-1)/d to an integer variable, it gets the same result.

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

Got my mistake.

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

    The string (()(())()) is different from the one given in the test case, and can't be formed from (???(???(? as the second last element (s[n-2]) is different in your solution and we can only change "?" and not the "(" and ")".

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

Can someone explain with example the approach for D ?

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

    Let us assume x is the answer k=#leaves nodes are 1,2,3,....,x,x+1,....,k

    If All nodes >=x are 1 and all nodes < x are 0 Then no of ones for nodes >=x are k-x+1 because of x,x+1,x+2,....,k

    Let dp[i] be the minimum no of ones needed in all nodes of subtree of i so that subtree of i is one (which means nodes>=x)

    So dp[root] means minimum no of ones need in all nodes of the tree so that the root gives one(an answer >=x)

    so k-x+1 >= dp[root]

    which means x<=k-dp[root]+1

    therefore largest value of x is k-dp[root]+1

    to calculate dp use following guidelines

    If the vertex is max type then it's enough for one of the children to be 1 for the vertex to give a 1 too (remember that 1 means that the value is >= x)

    And for min nodes you need all the children to be 1

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

Is ques D is related to some standard problem which I should solve first? because I feel many people did solve this ques in very less time and almost all have applied same approach.

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

    I feel the same way.

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

    I solved it in contest and don't remember seeing any similar problem. I started brainstorming and analyzing random trees I drew on paper and eventually saw the pattern.

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

      Could you help me? how you come to the recognize the pattern? Like not the solution I am asking, but how did you able to connect the dots in order to get the pattern?

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Okay, I will try to explain my thought process. The maximum query looked like it would be pretty straightforward, so I only thought about the minimum query. Idea one (Wrong): If I want the minimum of 2 children, then the max should be in one and max-1 should be in another. I drew a sample where this failed. Idea two (Failed): Make some sort of dp to find out which of the children is the one I keep. I couldn't think of anything with this approach. Idea three (Success): Look carefully at sample 3, and try drawing a few similar ones, but with more levels. Say N is the number of leaves. I saw that when a node keeps the minimum value of its children, it looses the values of all other children. Say you have 3 children, the value on this node can not be N or N-1, but it can be N-2. This led to the idea: If a node keeps the minimum, it looses all the values of its children, except the smallest one (loosing K values means the answer can't be higher than N-K). So you keep track of which values the children lose, and keep the smallest one (Number of lost numbers — 1). Now for the max query: You want to lose the minimum possible (to get the highest possible result), so you keep the child which loses the minimum. Link to my submission: https://codeforces.com/contest/1153/submission/52704203

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

What is the intuition behind problem D?

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

Am I the only one who thinks that the editorial needs more explanation?

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

    For which problem? :)

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

      Problem B.

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

        For any $$$h_{i,j}$$$, it is limited by three views — the top view, the left view and the front view. We just set $$$h_{i,j}$$$ as the minimum among these three limitations.

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

      Problem D

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

        You can refer link
        this solution is easy to understand.

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

      Can you explain the min case of the second solution given in editorial of Problem D?

      For all sons or children v of u, we number the first $$$f_{v}−1$$$ leaves in the subtree of v first according to the optimal arrangement of the node v. And then no matter how we arrange the remaining numbers, the number written in u is $$$1+\sum_{v\ is\ a\ son\ of\ u}f_v$$$. This is the optimal arrangement.

      What is the proof of this?

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

How do i add an image to my blog ?

»
12 days ago, # |
Rev. 5   Vote: I like it +14 Vote: I do not like it

**Problem D : Serval and Rooted Tree **.
Can also be done in this way . for each node X keep a pair (maximum possible order of X,no of leaves subtree rooted at X has).
Order of X means if we sort values at leaves in the subtree rooted at X then let that sorted sequnce be it be L1,L2 ..,Li ...Lk then Order of x is maximum possible index .
Lets call this tuple (maximum possible order of X,no of leaves subtree rooted at X has) as (ff,ss).
if node X is of **max ** type maximum then X.ss is total leaves in subtree rooted at X i.e. X.ss=($$$\sum\limits_{}^{all child} C.ss$$$ ) where C represent child.
Ans X.ff is maximum possible order that will be X.ff=max(X.ss-(C.ss-C.ff)) i.e. X.ff=X.ss+max(C.ff-C.ss)) for all C that are child of X.

if node X is of **min ** type maximum then X.ss is total leaves in subtree rooted at X i.e. X.ss=($$$\sum\limits_{}^{all child} C.ss$$$ ) where C represent child.
Ans X.ff is maximum possible order that will be X.ff=($$$\sum\limits_{}^{all child} (C.ff -1)$$$ ) + 1.

code :
code_link

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

There is a place in question C that I don't want to understand. According to the meaning of the problem, first fill in the required'(', then fill in the required')'. In this case, there is only one filling method. I don't know how to prove that only this filling method is available.I hope someone can help me.

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

    There are many solutions. We just use this method to construct one possible answer. :)

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

      Thank you for your reply. Since there are many solutions, why can one of them be used to judge the feasibility?

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

        The method I given is the optimal way to find an answer. If the answer it found is invalid, there will be no solution exists. :)

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

What is test case 5 in problem D ?

»
12 days ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

silly bugs T^T

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

Just when you thought asking EXACTLY 2019 queries for E was fuckin' genius...

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

    How did you manage to do that?

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

      First 1000 queries to check each column. If head and tail are at the same column, I check 999 rows (if there are only one odd answer (for head), it means that the tail is at the 1000'th column). And next I use binary search (2x10) to find exact positions. In total it's 1000+999+10+10=2019 queries

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

For div 2 c the second example test case given- 10 (???(???(?

is ()()()()()->(1)+(1)+(1)+(1)+(1) not a solution? why?

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

    As the problem states, all prefixes of the final string, except the final string itself, should not be valid. Since () is a valid parenthesis sequence, ()()()()(), is not a valid solution.

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

    Please read the statement. () is a strict prefix of ()()()()(), and according to the problem, it should not be a correct parenthesis sequence.

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

How to solve C. I am not able to get the solution described by the author ...Please help me

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

I have seen problems similar to C before with parentheses checking. I would like to practice more of those .. can anyone link me to similar problems please ?

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

Problem C :

-at the end you need to have n/2 of '(' and n/2 of ')'.

-what is the best way to arrange the n/2 of ')' so that the string is still strict prefix as long as it's less than n ? by putting them as far as possible so that the(number of '(' is greater as possible so that we won't allow any type to correct sequence before the end of the string)

-the best way to put the ')' is to go from n-1 .... 0 and in each step you check if s[i] = '?' and the number of ')' is less than n/2 if it's you put the ')' otherwise in every '?' you put '('.

-after you finish the previous operation you go from 0 .... n-1 and count the number of '(' and ')' on every step and check that '(' is always greater than the number of ')' and i < n-1 otherwise you print :(.

-after you finish the loop you check that the number of '(' and ')' is equal if so you print the string otherwise you print :(.

here is my submission : https://codeforces.com/contest/1153/submission/52723028 , happy solving!.

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

In problem D 1. why are we taking sum of dp values in case of min operation. 2. why are we taking min values in case of max operation.

»
12 days ago, # |
Rev. 5   Vote: I like it +70 Vote: I do not like it

I think Problem F can be solved directly by calculus in $$$O(n\log n)$$$.

Let

$$$ p(x) = {x(l - x) \over ({l^2 \over 2})} $$$

(Which means the probability that a random segment cross point x.)

Then

$$$ f(x) = \sum\limits_{i = k}^n {n \choose i}p(x)^i (1 - p(x))^{n - i} $$$

(Which means the probability that a at least k random segment in n cross point x)

We just need to calculate:

$$$ \int_0^l f(x)dx $$$

We can solve it in $$$O(n\log n)$$$.

I implement it in $$$O(n^2)$$$ though...

UPD: I can't solve it in $$$O(n\log n)$$$ but $$$O(n\log^2 n)$$$. It's about polynomial interpolation so very brute.

UPD2: It can be solved in $$$O(n\log n)$$$ now. See at here.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Oh, by FFT. For it's 998244353.

  • »
    »
    10 days ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    how to cal f(x) in O(n^2) ?

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

      That's quite easy. We first reform $$$f(x)$$$ to $$$\sum\limits_{i = 0}^n a_i p(x)^i$$$.

      It's $$$O(n^2)$$$.

      Then we replace $$$p(x)$$$ with $$${2x(l - x) \over l^2}$$$.

      It's $$$O(n^2)$$$.

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

    Can you explain more about how to solve $$$\int_0^l f(x)dx$$$ in $$$O(n\log n)$$$?

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

      Sorry about that. My mistake. Now I can only solve it in $$$O(n\log^2n)$$$

      • »
        »
        »
        »
        9 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        By polynomial interpolation. It's very brute.

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

      I can solve it in $$$O(n\log n)$$$ now.

      Let $$$l = 1$$$, it doesn't matter.

      We reform $$$f(x)$$$ to $$$f(x)=\sum\limits_{i = 0}^n a_ip(x)^i$$$.

      We now only need to calculate $$$\int_0^1 p(x)^i dx$$$. $$$p(x) = 2x(1-x)$$$.

      So it will be $$$\int_0^1 x^i(1-x)^i dx = {i!^2 \over (1+2i)!}$$$.

      I don't know why but now it can be solved in $$$O(n\log n)$$$. (I get this by wolfram...)

      So anyone knows why: $$$\int_0^1 x^i(1-x)^i dx = {i!^2 \over (1+2i)!}$$$?

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

        Aw, It's Beta function!

        And it seems like:

        $$$\int_0^1 x^i(1-x)^i dx = B(i+1,i+1) = {i!^2 \over (1+2i)!}$$$

        Thank you so much!

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you share some problems of this kind?

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

Can someone explain the problem C, I have tried understanding it, but didnt worked out.

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

    So the problem is the same as asking to recover (if possible) a sequence of parentheses that is balance but any proper prefix is not balanced. The sequence of parenthesis is balanced if and only if: there's equal ( as ), and for any prefix there's no more ( than ). Saying that the sequence of parentheses is balanced but any proper prefix it's not actually implies that the number of ( is more than the number of ) for any proper prefix... that's the main idea :)

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

      okay, here is my understanding. let me know whether is correct or not

      P(1,L), 1<=L<=N, is balance if it contains equal number of ('s and )'

      and we have to balance the P, such that there should be only one solution for L, that is L=N.

      and we have to replace ? with )'s or ('s to satisfy the above contraint. right ?

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

Problem B has another cute solution (at least I had it accepted, break me if you dare!) -- if t[i][j] = 1 (we don't care about the 0 case obviously), then the number of bricks we put is min(b[i], a[j]) (basically, the minimum of the front and left view corresponding to the brick).

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

    That's what I submitted, too. You don't even need to store the t_ij, you can output this min as you read a 1, or 0 when you read a 0.

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

      Ditto. If there were impossible arrangements, this might fail, but since it's guaranteed the given heights will be possible, this minimum approach should always work.

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

[please ignore earlier posted message, I confused node id and value filled in]

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

    Read the statement carefully please. :) The numbers written in the middle of the nodes are their indices, and the numbers written on the top are the numbers written in the nodes.

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

I have looked at all of the solutions of D but all of them are too cryptic. I can't understand none of them at all. All these subindicies and sums are very, very confusing and I can't understand why do they pop up. Can someone please instead of saying "Do x to solve" try to explain why do x to solve? What is the intuition behind those indicies? Why this and not that?

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

Can someone explain how to do a binary search in problem E ,for example, after finding a row how to choose the two points ?

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

Can you please explain what is wrong with this submission: https://codeforces.com/contest/1153/submission/52760960 When I run it locally I get the correct answer for the second test case.

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

    There are $$$n-1$$$ edges in a tree but you tried to read an $$$n$$$-th edge.

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

Why in problem F we add both f[i-1][j][1] and f[i-1][j][0] to f[i][j][1] (the first case in solution placing P at the ith position)

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

Can I get Some upvotes ;)

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

Can the problem D be solved using breadth first traversal?

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

Are there any problems similar to problem D for practice ?

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

Can anyone explain how this solution of D by Max.D. works ?

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

can we solve problem C using stack ,someone please explain the approach.

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

It would be nice if the problem statement explicitly says if the interacter is adaptive, just saying.

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

Can anyone explain to me what's wrong with my submission for the interactive problem E. The checker seems to be giving me an invalid answer given the mentioned input. Can anyone take a look if there's some issue? https://codeforces.com/contest/1153/submission/53116004 (check the diagnostic message for Test Case #3)