Vladik's blog

By Vladik, 4 years ago, translation, In English
Tutorial is loading...

Author: aropan

author's solution: 96602393

Tutorial is loading...

Author: AleXman111

author's solution: 96598752

Tutorial is loading...

Author: AleXman111

author's solution: 96598711

Tutorial is loading...

Author: hloya_ygrt

author's solution: 96727317

Tutorial is loading...

Author: andrew

author's solution: 96601544

Tutorial is loading...

Author: hloya_ygrt

author's solution: 96727345

P.S. We will add our own solutions soon

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

| Write comment?
»
4 years ago, # |
Rev. 3   Vote: I like it +70 Vote: I do not like it

In B you can also use 1 1 0 0 0 0 0 0 0 0 ... and cycle shift one unit every time

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

    yes, you are right i did same

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

    could you please explain a bit more. Thanks.

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

      11000
      10001
      00011
      00110
      01100
      it is cylcing, and you get all row and column having equal sum

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

        I did this :

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

      Probably this :-
      1 1 0 0 0
      0 1 1 0 0
      0 0 1 1 0
      0 0 0 1 1
      1 0 0 0 1

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

      1 1 0 0 0

      1 1 0 0 0

      1 1 0 0 0

      1 1 0 0 0

      1 1 0 0 0

      in every row and column answer is 2

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

    I also did this only:)

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

    you can also use 4,1 and 8. 96557902

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

    This was my answer:
    fill only one diagonal with 1.
    then fill every up and down cell with 1 of this diagonal.
    fill every other thing with 0.

    for n = 5
    11000
    11100
    01110
    00111
    00011

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

    Problem B would have been slightly more interesting if instead of non-negative numbers, we were only allowed positive numbers.

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

      I don't think so.

      Actually you can still put 1 for everything except main diagonal.

      For main diagonal, brute force for !isprime(r) && isprime(r+n-1) and fill in r.

      Maybe the AC amount would just be decreased by like 500.

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

C(hasBig,cntBig)⋅cntBig! What does this C means in question 1436C?

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

In Problem B you can go like For 4 1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 For 3 1 1 0 0 1 1 1 0 1 For 2 1 1 1 1

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it +3 Vote: I do not like it
    d = not prime number.
    sum_row_col = d + n - 1 = prime number.
    ex. n = 4
    d 1 1 1     4 1 1 1
    1 d 1 1     1 4 1 1
    1 1 d 1 ->  1 1 4 1
    1 1 1 d     1 1 1 4
    
»
4 years ago, # |
  Vote: I like it +61 Vote: I do not like it

Sorry but can you explain E's solution a little more clearer

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

    A simple way to think of it is lets say we want a MEX of $$$x$$$.

    Our array is something like $$$ .... x .... x .... x .... x .... x .....$$$ Notice that, for any array, adding a new number cannot make it not $$$x$$$, unless you add $$$x$$$. So if there exists a subarray with MEX of $$$x$$$, there must also be a subarray between the occurences of $$$x$$$, that has a MEX of $$$x$$$.

    Now to query these subarrays, we will use a segment tree $$$S$$$. Lets sort the queries by $$$r$$$. Let $$$S_i$$$ be the last position of $$$i$$$. Now to check if subarray has a MEX of at least x, you can query, the minimum last index of the values from $$$(0,x-1)$$$. If that is greater than your $$$l$$$, then the subarray has a MEX of at least $$$x$$$. Since the subarray doesn't contain any $$$x$$$, the MEX cannot be larger, so querying it is equivalent to checking if MEX is $$$x$$$.

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

      What these queries look like? What do we want to request for $$$[l, r]$$$?

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

        The answer to $$$query(1,x-1)$$$ is "how far back do I have to go in the array to find all values in the range $$$(1,x-1)$$$".

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

      Yes i did it by mo's algo and my time complexity is O(N*sqrt(N)*log(N)) which is giving me TLE . CAN ANYONE SUGGEST IT TO REMOVE TLE. THANKS,IN ADVANCE

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

Weak pretests for C. Huge number of people getting WA on test 10.

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

    What actually is test 10?

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

      Should probably be something like 6 3 3. Actual answer should give 36, people who failed system tests, their answer is 120.

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

        The actual answer is 120. On the first iteration itself you are supposed to find 3, so the other 5 elements can be in any order. Basically 5! = 120.

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

          On the first iteration it will return 2 as mid (because its 0 indexed)

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

            h = 6 and l = 0 so mid = 3

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

              no he is right change your high and you will get the right answer. I am ashamed of myself. But considering they had such weak pretests, it is a shame for them too.

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

                Yes I understand. The image in the problem was not accurate that confused to take h = a.size()

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

                But in the problem statement h=a.size()

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

                In actual it should have been a.size()-1 in the problem but as it was given a,size()..it did with that.

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

                  Yeah they explicitly mention it to be h instead of h — 1

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

      I guess its because we shouldn't break when (l == pos) instead do : mid = l+1; PS : If that's the mistake I'm getting WA on test 10 too!

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

    Can you please tell what is actually test case 10 in C?

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

    When the pretests are so weak, the round should be unrated.
    I failed systest on C.

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

      nonsense

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

      It's clearly mentioned that your solution may pass the pretest but doesn't mean that it will pass system testing for sure.

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

      what's the criteria between weak pretest or not?

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

What is av and maxi(sum(av)/leaf(si)) in problem D? Can someone elaborate?

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

Can someone give a more clear explanation of Editorial of D.

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

    You can refer to my solution.

    At the end, every citizen will be at one of the leaf nodes. So, they should follow this strategy: first, distribute all the citizens from the immediate parents of the leaves, to the leaves. Then distribute the citizens from the parent of the parent to the leaves in its subtree, then parent of parent of the parent of leaves, and so on, in a bottom to top manner.

    How to distribute this? Let's see the first step: From immediate parent of leaves to the leaves. We'll try to minimise the maximum number of citizens that are at any leaf. To do this, we'll first try to make the number of citizens in every leaf equal the maximum number of citizens present in any other leaf which has the same immediate parent as this leaf. Once, all leaves under the same immediate parent have an equal number of citizens, we can can start distributing the remaining citizens from the parent to the leaves equally.

    So, if a parent of leaves has $$$L$$$ leaves in its subtree, the total number of citizens in its leaves is $$$c1$$$, and there are $$$c2$$$ citizens initially in the parent, then the maximum number of citizens in any leaf after distribution is at least $$$\lceil \frac{c1+c2}{L} \rceil$$$. This is simply a result of the Pigeonhole Principle.

    We'll store three values at each node: $$$max$$$, $$$sum$$$, and $$$count$$$. $$$max$$$ is the maximum number of citizens present in any leaf of our current node's subtree, $$$sum$$$ is the total number of citizens present in our subtree, and $$$count$$$ is the total number of leaves in the subtree. For a leaf $$$u$$$, $$$max[u]$$$ $$$=$$$ $$$sum[u]$$$ $$$=$$$ $$$a[u]$$$, $$$count[u]=1$$$.

    For other nodes $$$u$$$, $$$sum[u]$$$ equals $$$a[u]+$$$ sum of all $$$sum[v]$$$ for children $$$v$$$ of $$$u$$$, $$$count[u]$$$ too is simply the sum of all the counts of the children. Now, $$$max[u]=maximum(\lceil \frac{sum[u]}{count[u]} \rceil, maximum(max[v]))$$$ over all children $$$v$$$ of $$$u$$$. $$$maximum(max[v])$$$ is the maximum number of citizens present in any leaf before distributing citizens from this node, and $$$\lceil \frac{sum[u]}{count[u]} \rceil$$$ is the minimum number of citizens that at least one leaf will have after distributing. The answer for a node $$$u$$$ will be stores at $$$max[u]$$$. So, we can implement using DFS.

    The main idea is find the answer for every node as if that node were the root of the tree and the actual tree was only formed of the subtree of that node. For each node, we distribute all the citizens from it greedily, keeping the maximum number of citizens present in any leaf minimum possible. We solve it bottom to top: first for the highest level, then previous level, then previous, and so on.

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

      Whiplash99 can you tell how this solution is correct? It did not use the DFS order for traversal.

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

        It's doing the same thing. Just not using DFS directly. This was possible because the problem had the constraint $$$1 \le p_i \lt i$$$, meaning, for any node, its parents will have a lower node number. Thus, a node numbered $$$8$$$ (say) can't be the parent of a node numbered $$$5$$$. So, we can just start solving from node $$$N$$$,and go backward, because its parent will have a lower node number. So, it's doing the same thing, solving it in a bottom to top manner.

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

      I got stuck for long while with WA at 5. I don't exactly know what I did wrong. BUt I did it like this only. Can you please see this if possible and tell me. submission

      What I've done is

      postorder DFS, resolving children first, and storing {maximum value from their children at any node, and total diff of max from all the other children nodes)

      for leaf nodes it's going to be {citizens[leafnode],0} since total max is the number of citizens at that node only and diff is going to be 0;

      then recursively, find maximum in all children, total diff, and citizens[node];

      if citizens[node] < diff, then store the {maximum of children, diff}

      else if citizens[node]>diff then store {maximum + ceil((citizens[node]-diff)/count),{some simple formula to calculate new diff}}

      then answer is at answer[0](main square) Thanks.

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

        Try this test:

        5
        1 1 1 4
        4 0 0 0 0
        

        Your code gives $$$1$$$ as the output, while the answer is $$$2$$$.

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

      thanks for the great explanation

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

      great explanation

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

      I have question that the game s going on sequential way like if citizen go to level 2and then in next step bandid go to level 2 then it will not catch them ?? or it will only catch when it only at leaves??

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

        "The process is repeated until the bandit is located on a square with no outgoing roads. The bandit catches all the citizens on that square."

        Leaves are the only nodes here which have no outgoing nodes. Thus, the bandit will only catch them in the leaves.

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

      Thanks for this great explanation. For solving in top to bottom, is there any specific rule for dividing the citizens at a particular node to its children ?

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

        No, there is no rule. It depends on the problem. Here, we followed a greedy strategy, and what was locally optimal turned out to be globally optimal too.

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

      Thanks for the amazing explanation !

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

    Here's my attempt at rambling about my thoughts explaining the way I thought about it in a more formal way.

    It's a little harder to think about adjusting the strategy for every time the people/bandit moves, so let's start by thinking about the final state and what each side can guarantee.

    First, if there are $$$P$$$ people in total they will end up distributed in the $$$L$$$ leaves, regardless of the strategies there will always be one leaf with $$$\ge \frac{P}{L}$$$ people at the end. It is not unnatural to think the bandit can always walk towards the subtree with the highest ratio of people to leaves and get $$$\ge \frac{P}{L}$$$.

    Let $$$P[u],L[u]$$$ be the total number of people,leaves at the subtree rooted at $$$u$$$. At the beginning we have a leaf will end up with $$$\ge \frac{P[0]}{L[0]} = r$$$ people. Next the bandit has to choose between some vertices $$$a_1,a_2,\dots, a_k$$$, notice the people already moved to one of this cities, so their subtrees have all the people $$$P[v_1]+\dots +P[v_k] = P[0]$$$ and clearly $$$L[0] = L[v_1]+\dots +L[v_k]$$$ as well. Intuitively, it makes perfect sense that one of the new ratios $$$\frac{\text{people}}{\text{leaves}}$$$ of a subtree has to be just as large as $$$r$$$, we distributed the people and leaves into several subtrees.

    Formally, suppose that all ratios $$$\frac{P[v_i]}{L[v_i]} < r$$$. That is $$$P[v_i] < L[v_i] r$$$ and adding this inequalities we get $$$P[0] = P[v_1]+P[v_2]+ \dots P[v_k] \le r (L[v_1]+\dots +L[v_k]) = rL[0]$$$ but this is impossible as it gives $$$\frac{P[0]}{L[0]} < r $$$ and we defined $$$r$$$ exactly like that. That means we always have some ratio $$$\ge r$$$ in the subtree of one of his adjacent vertices. As we go down the tree following this procedure we'll eventually reach a leaf with ratio $$$\ge r$$$ and so he will get at least $$$r$$$ people in there.

    So we have some progress, we just proved the bandit can always get $$$\ge \frac{P}{L}$$$ where $$$P$$$ is the total number of people and $$$L$$$ is the total number of leaves.

    If you look carefully we did much more, there is nothing special about the starting vertex. The same argument shows that if we have a subtree with some ratio $$$\frac{P}{L}$$$ the bandit can get at least that many people at the end. Therefore, the bandit can always get $$$\ge \frac{P[v]}{L[v]}$$$ for any vertex $$$v$$$. In particular he can get $$$\ge r$$$ where $$$r$$$ is the maximum ratio $$$\frac{P[v]}{L[v]}$$$ among all vertices $$$v$$$.

    At this point one thing is clear, the absolute minimum the bandit can get is closely related to the ratios between people in a subtree and the number of leaves. In particular we can always get $$$\ge r$$$ where $$$r$$$ is the greatest ratio people/leaves among all subtrees. However, for any of this to be actually useful we need to make sure the people can organize themselves in a way that doesn't allow the bandit to get more than this. We shouldn't be too scared as it again makes intuitive sense that the people can distribute themselves somewhat evenly among all the leaves.

    What prevents the people from distributing themselves perfectly even among the leaves and leaving the bandit with only $$$\left\lceil \frac{P}{L} \right\rceil$$$ captures? If all the people in the city start in a leaf, we can't move any of them and the bandit gets all. Generalizing a little, if a subtree is charged with a lot of people its leaves will have a much higher average.

    This motivates us to prove that the people can always distribute themselves in a way that at the end each leaf has $$$< \frac{P[v]}{L[v]}+1$$$ for the maximum such ratio $$$r = \frac{P[v]}{L[v]}$$$ among all vertices $$$v$$$, as we already showed the bandit can always get $$$ \ge r$$$. That will prove the answer is $$$\lceil r \rceil$$$ for the largest ratio.

    Suppose we're at $$$v_i$$$, there are $$$a[i]$$$ people on it. We know there are $$$P[v_i]$$$ people on its subtree and $$$P[v_i] \le rL[v_i]$$$ as $$$r$$$ is the largest ratio.

    We would like to distribute them as $$$p_1+\dots + p_j = a[i]$$$ among his child $$$r_1,r_2,\dots , r_k$$$. Our objective is once again preserving $$$\frac{P[r_i]+p_i}{L[r_i]} < r+1$$$ so we want $$$P[r_i]+p_i \le (r+1)L[r_i]$$$ or $$$p_i \le (r+1)L[r_i]-P[r_i]$$$. In other words, we can add up to $$$\lfloor (r+1)L[r_i]-P[r_i] \rfloor$$$ to the subtree rooted at $$$r_i$$$ while preserving the ratio condition. We now have to show this gives us enough margin to distribute all the $$$a[v_i]$$$ people standing on $$$v_i$$$. That is, we just have to prove: $$$\lfloor (r+1)L[r_1]-P[r_1] \rfloor+\dots + \lfloor (r+1)L[r_k]-P[r_k] \rfloor \ge a[i]$$$.

    Notice that $$$L[r_i] \ge 1$$$ as each subtree has at least one leaf. Therefore $$$\lfloor (r+1)L[r_i]-P[r_i] \rfloor \ge \lfloor rL[r_i]+1-P[r_i] \rfloor > rL[r_i]-P[r_i]$$$ for each term in the sum as $$$\lfloor x \rfloor > x-1$$$ for all $$$x$$$.

    Adding them all up we get the left side is at least $$$r(L[r_1]+\dots + L[r_k]) - (P[r_1]+\dots + P[r_k]) = r(L[v_i]) - (P[v_i]-a[i]) = rL[v_i]-P[v_i]+a_i \ge a[i]$$$ because $$$rL[v_i] - P[v_i] \ge 0$$$ is equivalent to $$$r \ge \frac{P[v_i]}{L[v_i]}.$$$

    This finishes the proof that the answer is $$$\left\lceil \frac{P[v]}{L[v]} \right\rceil$$$ for the largest sch ratio. Hopefully this makes it a bit easier to understand. We just explicitly wrote out the details that formally prove our intuitions:

    • The bandit can chase the largest ratio, locate the subtree that has it and start going down in its direction, once we reach it, every time we go down we just pick the subtree with the largest new ratio. No matter what the people do he will always end up in a subtree with a ratio just as big, and capture at that many people at the end.

    • People can distribute themselves 'evenly' among the leaves, ending up with less than $$$r+1$$$ on each at the end. Whenever we are on a vertex we give as many people as possible to each subtree without messing up its ratio (making it larger than $$$r$$$) and as we proved that is enough to fit all the people.

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

In the tutorial for question D it is written that the proof that answer is [a1/leaves] if all people are at the root of the tree is provable using dirichlet principle. Could someone please elaborate on that?

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

    I think it is another name for pigeonhole principle.

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

    If everyone is at root we can uniformly distribute each person to each leave. [] it is actually ceiling. Let us assume a1=13 and leaves 4 We can send 4 to the first and 3 to the remaining. So ans is [13/4]=4;

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

Man this contest problem were used in a official contest .. Such a shame having such pretest for C

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

Why doesn't C consider the permutations of the numbers not part of hasBig and hasLess?

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

    Yes the correct answer is :-

    C(Bignum, cntBig)*(cntBig!)*C(Lessnum, cntLess)*(cntLess!)*(n - cntBig - cntLess -1)!
    

    Where :- Bignum = (n - x) Lessnum = (x - 1)

    And cntBig, cntLess is same as explained in the tutorial.

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

      Just a small correction, it should be $$$(n - cntBig - cntLess -1)$$$ factorial

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

Here is the weird part.... this submission was accepted. And yet for 6 3 2 it actually shows 36 when the answer is 120. The testing for this problem seems extremely poor. Better luck next time!

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

    The correct answer is 36.

    for input 6, 3, 2. The permutation pattern is:

    "* a 3 B * *"

    where B in {4, 5, 6}, a in {1, 2}

    3 * 2 * (3!) = 36.

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

weak pretest !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

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

Weak Pretests, Long Queues, Unexpected Errors and Rated :(. Make it Unrated :P

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

in B it says there are no prime numbers in the square.

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

    1 is not prime.

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

    People be mourning to the rip case of C and random guy be like : 1 iS PrImE ..

    Man come on revise your maths lessons

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

How to solve C??

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

    First of all simulate the given binary search.

    For every mid position we know that whether our given element lies left or right of that mid position. If it lies in the left of the mid position then we need to place a element which is bigger than our given element otherwise we need to place a smaller element there.

    We will count how many places there are where we can place smaller element and bigger element. Let's say we can place smaller element in S positions and bigger element is B positions and we have X smaller elements and Y bigger elements. So, how many ways can we arrange X elements in S positions and Y elements in B positions?

    It is P(X,S) = C(X,S) * S! and P(Y,B) = C(Y,B) * B!

    After placing all those elements let's say we have R elements remaining. Then R can be arranged in R! ways. So, the final answer is ans = P(X,S) * P(Y,B) * R!

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

      Can you tell me the answer for input "3 3 1", the output shown is 0 but "1 3 2" and "2 3 1" are valid permutations.

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

        Notice that in the given code, they used, if(a[middle]<=x) then left=middle+1

        for the first iteration, middle = (0+3)/2 = 1 and left = middle+1 = 2

        for the second iteration, middle = (2+3)/2 = 2 and left = middle+1 = 3

        So, it will never find 3.

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

      Thank you, well explained.

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

      Thankyou so much <3 I finally understand how to solve C

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

A request , From the next time please provide the solution with an AC code in Tutorial, atleast for questions like D which need good implementation skills

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

Here's a solution video/screencast in which I predict that I would FST C three separate times, but am still not careful for some reason

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

    In problem D- I first calculated the maximum population amongst all the leaf cities lets call it $$$maxele$$$ and then I filled up all the non-leaf cities' population in all the leaf city and made population of all leaf cities equal to 'maxele'

    if after all this I've still population of non-leaf cities left then I'll distribute it equally amongst all leaf cities and my answer would be ->

    $$$ answer = maxele + populationleft/noofleafcities$$$

    but I'm getting wrong answer on test-5 now test-5 is quite big so I can't decode it, Can you please help?

    Here's my Submission

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

      This doesn't work because the rest of the edges are also directed — you can't move any non-leaf value to any of the leaves.

      Example case would be:

      5
      1 1 3 3
      0 0 100 0 0
      

      and relevant diagram:

      where the 100 can only move to the two leaves below it, meaning the answer should be 50.

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

So I failed test 10 in C, but I'm not sure why.

The test is "3 3 1" and the correct output is 0. But shouldn't the correct output be 2?

Since both the permutation "1 3 2" and "2 3 1" would work because the binary search would just look for the middle element, which is 3, thus finding 3 in both cases.

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

    I'm confused too. Can someone clarify please?

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

      In image, it is given that when pos<=mid left+=1 so it's that we don't have to return the result when pos==mid we have to move further which ultimately will show the result 0

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

    Yea the first middle would be one right ? Can someone help what makes this test to have answer zero ?

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

    Exactly ! I also don't understand why the answer should be zero.

    Edit:- Leave it I found where I was wrong.

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

    I also got that wrong. But I guess the output for that test case is indeed 0 because they ask for the number of permutations for the given implementation of binary search, which indeed fails to find 3 for both permutations.

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

      How? I implemented their binary search function and it succeeds in finding 3. Idk what's wrong

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

        First case: 1 3 2 Second case: 2 3 1 After first iteration mid=1, a[mid] <= x, L = mid+1=2
        so our range(L,R) is (2,3)
        After second iteration mid=2 and this is the important part. In both case the
        value of index=2 is either 2 or 1 is still less than 3, so L=mid+1=3.
        Finally both case end up with break condition L=R=3
        and a[L-1]=a[2] which is not equal to 3.

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

    After asking for position 1, you're left with range [2,3]. Nevermind what number is on position 2 it is smaller than 3, thus left will be equal to 3 at the end if the process, not 2 as it should.

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

    For 1 3 2 , No , Because mid=(3+0)/2=1 a[1]<=x left=2 now, mid=(2+3)/2=2; a[2]<x so left=mid+1=3 , so pos is found out to be left-1=2 , where as in question it should be 1 , notice that there is no break statement even if the element is found

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

    in case of 2 3 1 would

    first iteration mid = 1 and 3<=x thus left = 2 and right = 3

    second iteration mid = 2 and 1<=x thus left = 3 and right = 3

    here you can clearly see left becomes 3 and a[3-1] != x thus it returns false

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

    Write the binary search program given in the question and try searching for element 3 at position 1 for the permutations (1,3,2) and (2,3,1). Both permutations give false as the answer. Then try looking why it happened, you'll get your answer.

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

    For 3 3 1, for the function to return true. A[2] > x i.e A[2] > 3, which is not possible.

    There are two steps in the dry run, 1) s = 0, e = 3 i.e a[1] <= x 2) s = 2, e = 3 i.e a[2] > x

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

I think In E 5 4 3 2 1 1 1 1 1 1 1 1 1 1 1

you cant have this example .

my friend Segment O(nlog^2n) wrong result can pass

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

The system testing has already finished and my solution for problem A still shows pretests passed which greatly affected my rank. Someone, please look into this .MikeMirzayanov bug.png

»
4 years ago, # |
Rev. 2   Vote: I like it -34 Vote: I do not like it

Weak pretests for C and E,I get failed system test in my other account.

rank 9 -> rank 500+ :(

Hope for strong pretests.

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

    "in my other account" you dont deserve to have better pretests, as you are ruining the contest for actual div2 contestants.

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

I was shocked when I saw this contest will be rated though my A's solution got passed after 10 minutes of submission and waiting 5-6 minutes for B's solution to get passed the pretests.

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

I was so excited that I could solve the 3rd div2 problem this time that I didn't look at the notes I made and missed a corner case ;-; Yayy

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

    You answer is failing on the 10th test case i.e for "3 3 1" your answer is 2 which I believe is correct as "1 3 2" and "2 3 1" are valid permutation. I don't know why they are showing 0 as output.

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

      Nope, for a solution to exist, the number at index $$$2$$$ of the array must be greater than 3, however this isn't possible, as there is no $$$p_i > 3$$$ for $$$1 \leqslant p_i \leqslant 3$$$

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

Editorial of E is just too short. Please elaborate a little. Thanks .

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

I highly suggest Andrey(character in problem C) to learn Binary Search from our EDU section because we have a much much better content than he is referring as of now. Who the hell still looks in the array if the position is found ?

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

In problem D, I used binary search. What is wrong with this logic? Submission

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

    I think there is Long Long integer overflow

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

      No, I am sure that all values are less than 2e14.

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

        Your binary search works in the range [1, 1e15], which implies that the req array might take values to the extent 1e15 * 2e5. Indeed it will overflow.

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

Alas I wasted a lot of time on the Binary Search Solution for D, missed the obvious solution.

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

    Can you please explain your binary search solution in detail?

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

      Basically binary search on the the maximum capacity(number of people) of all the leaf nodes. Then just traverse the tree and check whether the capacity of each node. Capacity of any node is the sum of capacities of children - the number of people on this node. The capacities of leaf node is the current fixed value - the number of people on this leaf node. If any node's capacity is less than 0, then the Binary search check fails and we check for the greater half, and vice-versa.

      Solution link for reference

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

Binary search soln for D 96602832

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

    Can you please explain idea behind your binary search solution , i am bad at understanding from code.

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

      F(s,x,p) -> If it is possible to distribute everything in this subtree to it's leaves,such that no leaf has more than x. We check the space left after solving children of x (it is optimal to first distribute children, as they will have lesser leaf nodes to support them), if the space left is >= a[x] fine, else false

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

        could you pls elaborate a bit about function f()... I'm not getting the if conditions

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

          as i understand, what we want to do in this problem is to distribute citizens among leaves such that the maximum number of citizens (let's call it as max) in some leaf is minimum, we will call this minimum as best_max. Obviously, we can find this best_max using binary search because if we can find a way to distribute citizens with max = best_max, then it's always possible to find another way such that max is worse than best_max (i.e max > best_max). Here, binary search starts by considering some value x for best_max, we will check if it is possible to distribute all the citizens to leaves so that no leaves have more than x citizens, we can do this greedily, which means that we will fill these leaves with as much citizens as we can i.e x. If, at some subtree, there exists some leaves that have less than x citizens, then this space left will be preserved for citizens from upper squares in the tree (which the f function above returns). If at some points we find a subtree whose leaves all have x citizens but still has some citizens left then we return false and find other x else we continue. The overall complexity of this is O(nlog(sum_of_citizens)) though with the solution in the editorial it just run dfs once and the time complexity is O(n).

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

In test case 10 for problem C 3 3 1 the answer should be 2. as (1,3,2) and (2,3,1) are valid permutations

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

    (0,3) — 1

    (2,3) — 2

    (3,3)

    Result will be false

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

      Can you explain it? What do you mean by "first middle". (0 + 3)/2 = 1 isn't it

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

      Can you please explain idea behind your binary search solution , i am bad at understanding from code.

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

    Write the binary search program given in the question and try searching for element 3 at position 1 for the permutations (1,3,2) and (2,3,1). Both permutations give false as the answer. Then try looking why it happened, you'll get your answer.

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

In problem C, 10th test case is 3 3 1 and actual answer is given 0 but there exist two permutation 1,3,2 and 2,3,1 which return true when binary search is performed on these permutation. So actual answer should be 2 right?? Anyone explain? Thanks in advance.

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

    You should check the comments first. This issue has been discussed already in a ton of comments above.

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

    Write the binary search program given in the question and try searching for element 3 at position 1 for the permutations (1,3,2) and (2,3,1). Both permutations give false as the answer. Then try looking why it happened, you'll get your answer.

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

In my opinion, no one should fail system tests because of overflow and an overflow case should always be included in pretests.

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

Here is an alternative approach to B solution. There are 2 cases, either n is even or odd. Take a 2D grid of size n*n initialized with 0. In case1: n is even, populate both the diagonals with 1 and print this 2D grid.

In case2: n is odd, consider the grid[n-1][n-1] and populate both it's diagonals with 1. Then put grid[0][n-1]=grid[n-1][0]=grid[n-1][n-1]=0 and print it.

This grid will always have the sum of rows and columns as 2 or 3.

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

.

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

Please, never implement Binary Search as same as in problem C.

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

    I was solving C with my own implementation of BS lol, while(l <= r) { ... } then realized its different, still failed for system test. ;___;

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

Such cute problems. =D

Just to note that it's possible(not showing off honestly! :D) here I could get AC from problem E with Mo's algorithm + BIT in O(n.sqrt(n).log(n)) time complexity.

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

    Can you explain what you are storing in the Fenwick tree exactly? It seems that it stores the frequency of each number, $$$X$$$. I don't understand what the mex() function does. It would be great if you can explain the idea behind that.

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

      Well, there is an array cnt which holds what you said. $$$cnt_x$$$ holds the frequency of number x in the $$$[l, r)$$$ range of the array as $$$l$$$ and $$$r$$$ move.

      But Fenwick is not built over the $$$cnt$$$ array itself. Actually, in the mex function I want to find the first element of cnt which is equal to zero(as it would be the mex of $$$a[l, r)$$$). So it just matters to my Fenwick tree whether $$$cnt_x = 0$$$ or not; so if we define tmp[i] = bool(cnt[i]) and declare Fenwick over the tmp array, we can use a binary search trick as we do in LCA(find bits of the answer one by one from MSB to LSB) to find the first appearance of $$$0$$$ in tmp.

      I tried to explain shortly, in case you need more details send me a message. =D

      P.S. as $$$fen[x] = \sum tmp[x - i]$$$ for each $$$0 \le i < x\ \text{&} -x$$$ we can make sure that all of the tmp elements in this range are equal to 1 iff $$$fen[x] = x\ \text{&} -x$$$.

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

        That is an amazing implementation of binary search in one line. Do you know where you got the idea from (any website that links the original LCA binary search?)

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

Just for curiosity, Is there any need of this type of problem (Problem C) in real life? Is there any need to continue finding even if I got the desired value on the desired position.

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

    Out of curiosity, do you think there is any need for the other problems we solve here in "real life" other than boosting problem solving skills?

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

I think most of us considered that

if left>0 and a[left-1]==x then

return true

else return false

was a part of the while.This was the confusing part for the most of us in problem C and in this case our algorithm works...

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

    Why there is no bracket for while loop?

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

      identation exists for something. That is pseudocode.

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

    This makes no sense, it would return false if it didn't find the element in the first step.

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

      Oh ,sorry.I didn't notice, I just took the test 10 and ran the binary search and it returned true.Thanks for the clarification.

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

Can someone explain me how to solve task E with segment tree?

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

D has "binary search" in tags, have someone solved it in this way?

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

For B you could just note that 101 is prime and 101=51+50 and cyclic shift 51,50,0... (with repeating 0s at the end).

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

    You can cycle $$$1,1$$$ instead of $$$50,51$$$ as $$$2$$$ is prime as well :P

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

I think mine is the most complicated B soln, Find the first prime number from n that is divisible by n-1 and greater than 3

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

I think that time limit for problem d is quite less. I think it would be better if the time limit for this problem was 2 seconds. ( I use dfs function log(1e15) times and get time limit)

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

    Since there are $$$O(n)$$$ solutions (including the official one), I believe that this time limit is quite reasonable ...

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

I think the test cases of 5th problem is weak. My O(2^n) solution for 5th problem, passed all test-case in 62ms.
Link to submission : 96604363
The type of test cases where it will go for 2^n complexity :
59

30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

This test-case gave TLE on my code, as I said my worst case time complexity is O(2^n).

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

why binary search is not working in problem D??

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

I used the same logic as in the tutorial for C. Can someone help me where I went wrong? https://codeforces.net/contest/1436/submission/96608378

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

    In your code, as soon as you visit middle == pos you are breaking the loop and not considering that even after that left and middle values can change.

    For eg. 9 4 4

    In 1st iteration middle == pos so you breaking the loop

    But in reality in the next loop when middle = 6, left can change if the value at 6 is less than 4 so in such cases your code is giving wrong answers.

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

      Oh ok, yeah I get it now where I went wrong. I just did not read the algorithm properly given in the question. Thanks for the help.

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

Can anyone tell, In C problem, how answer of 9 4 4 is 7200.

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

    We know, pos(4) = 4, after 1st BS left = 4, right = 9, now middle will be 6 so now for our BS to return trye we need a bigger value than 4 at pos = middle, as we have 5 values bigger than 4 so ans = 4, Now left = 4, right = 6, middle = 5, same condition as before so ans = ans*4(coz now only 4 values are left bigger than 4. again same step, ans = 5*4*3, now after this left==right so BS stops now we have fixed 4 positions and 5 positions are left and we can fill them in any order

    So final ans = 5*4*3*5! = 7200

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

problem E how to get the mex using segment tree ??

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

    First store all the segments for which you want to calculate the mex value and then sort them according to their r value. We will build a segment tree which answers minimum in any range. Initially all the nodes in the segment tree is assigned with infinity. Now proceed by by taking segments one by one. Lets say its right value is r so for every index <= r you should update its value in the segment tree and then query for minimum in the range 1 to x-1 where x is the value for which you have got this interval. If the minimum value is greater than l it implies that all the elements in the range 1 to x-1 have their last occurrence in the range l to r , so mex value x is possible.

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

Can someone please explain binary search solution for D?

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

    You can directly do binary search on the answer. After choosing a value=mid, starting from the leaves, you can store how many maximum citizens that can arrive from above to that node. We will use take[] to store those values. For leaves that number is mid-arr[x], if arr[x]>mid, then its obvious that there are already more than mid number of citizens there so our mid is small. So, for leaves take[x] = mid-arr[x], and for other nodes take[x] = (sum of take[v] for all children v of x) — arr[x]. You have to subtract arr[x], because we will be sending all citizens to the children of that node. In the end we just check if take[x]>=0 for all x, since otherwise we weren't able to send all citizens from x to below, as it can be seen from the above equation. It requires a bit of optimization, and also look out for overflow, keep take[x] in bound of sum(arr). You can look at my soln if you want. Soln

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

I don't know whether it was intended to not let binary search in D to pass easily, but for me atleast, it took quite a lot of small optimizations to finally get rid of the TLE. Or you could use bfs to pass the TL a bit more comfortably. Still have to take care of overflows though.

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

    could you explain your approach please??

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

      I have explained it above, if you any doubts, you can ask me.

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

    My logic is exactly same. This is my submission. It is saying signed integer overflow. But that seems impossible to me as I am using long. Can you have a look?

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

      One case where this type of logic can overflow is this: N = 2e5, arr[i] = 1e9 for all i, and each node is directly connected to 1. So here the value of fill for node 1, in your code, will have value (2e14 — 1e9) * (2e5 — 1) which is around 4e19, hence the overflow. You can avoid this by just restricting fill to min( fill , sum(arr)), at each step.

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

        Oh yes I never thought that way. Got it accepted. Thanks a lot man.

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

For 1436F, Sum Over Subsets, the problem assumes that there are multiple different subsets with cardinality 4 of {1,1,1,1,1}. This seems to be mathematically incorrect, as there is really only 1 subset with cardinality 4: {1,1,1,1}.

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

    Just pointing out an issue in the problem, what's about all these downvotes:)

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

Problem E can be done with Persistent Segment Tree and you don't have to bother with ordering the queries :)

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

in prob A , every other compiler shows the correct output but on codeforces it shows wrong. plscheck if anyone of u found any mistake.

include<bits/stdc++.h>

using namespace std; typedef long long int lln;

define all(x) x.begin(),x.end()

int main() {

ios_base::sync_with_stdio(false);cin.tie(NULL); int t; cin>>t; while(t--) { int n; double sum=0,m; cin>>n;cin>>m; int a[n+1];a[0]=0; for(int i=1;i<=n;i++)cin>>a[i];

sort(a,a+n+1); for(int i=1;i<=n;i++) { for(int j=i;j<=n;j++) { sum=sum+(double)a[j]/(double)j; } }

if(sum==m){cout<<"YES\n";} else cout<<"NO\n";

}

return 0;

}

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

    It is because of double. You should never compare double variable with any double/int variable. This is due to precision errors.

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

Can anyone Explain D?

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

    D's solution is so hard to understand. Im not sure even sure why its a tree in the first place. How do I know the structure/layout of the tree?

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

      In D, it's quite clear that its a tree, just consider this: each edge is pi -> i, that basically means that pi is the parent of i. The condition pi < i ensures that the tree is connected. Also I have explained my binary search soln above, you can have a look at that if you want.

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

      It was mentioned in the problem, initially you have n nodes and n-1 edges and you could reach each node from the root node. So that's a tree. Later it was converted to a directed graph,
      1) just adding directions to the edges
      2) still you could reach each node from the root.
      You can never satisfy these conditions without the discussed tree like form of the graph.

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

    Take an node , say $$$p$$$ , take "sum" of values of all nodes in the subtree of node $$$p$$$ (including $$$p$$$ itself) . Also suppose number of leaves in subtree of $$$p$$$ in "L" . Final answer will be maximum of ceil(sum/L) over all nodes in the tree . Why this works ? See the two examples in the problem and do the above for every node.If you don't get you can ask me.

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

Problem statement of F was confusing. As far as I know two elements in a mutiset with same value are considered equal and in that case number of subsets of a multiset is $$$\Pi_i (1+f_i)$$$. But from the solution, it doesn't seem like that's the case in this problem. It would have been nice if the terms used were properly defined.

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

Problem B got me... I didn't notice that you can use zero, assumed all numbers must be positive, figured it must be some variation of the magic squares construction algorithms and got lost in there :)

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

On 1436D - Bandit in a City i tried to keep track of the already visited node with max citziens and then use the sum of the difference between the max and the number of citziens on the other nodes, i can't find a counter example, but my code is failing test case 78, if anyone can give me a help this is the submission
96620681

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

For E, how do we process the occurrences in order using segment tree?

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

C(hasBig,cntBig)⋅cntBig! ,is that equal to P(hasBig,cntBig) ?

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

Need help. In D, I got WA on test 77 and I don't really get what's wrong with my code.

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

Can anyone tell me how to solve Problem B, if we are allowed to fill only positive numbers?

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

    fill a (n — 1) * (n — 1) table with 1, after that check the numbers that can be placed in other positions... I've done something similar during the contest although I wasn't that mush sure if there exist such a number always or not .. but now that I'm thinking about it.. I guess it can be proved easily!

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

can someone tell the answer of testcase 3 3 1 in problem C?? is its answer is 0 or 2??

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

I solved B with a cool sequence

1, 4, 6, 8, 10, 12, 18, 20, ...

see my code

to get this sequence, you need to have a primality test function and do the following

seq = [1]
sum = 1
for i in range(2, 600):
    if not is_prime(i) and is_prime(sum + i):
        seq.append(i)
        sum += i

for each input $$$n$$$ just slice the $$$seq[:n]$$$ and cycle shift one unit to get the matrix

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

sorry if my question is very standard but i stuck on this, In problem D given a connected graph having n node and n-1 edges so my question is how to prove that it will never contains a cycle??? Even i know that it is true but i need proof.

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

    I think you can do by induction on the number of vertices.

    First n = 2(and thus 1 edge) obviously has no cycle.

    Now suppose any graph with k vertices and k-1 edges imply no cycle. We want to prove the case of k+1 vertices and k edges.

    Make use of summation(degree of vertex) over all vertices is 2*number of edges. Now since number of edges is vertices-1, obviously you can't have deg>=2 for every vertex. So now you have at least one vertex with degree 1(not 0 since connected). Also this vertex wouldn't participate in any cycle, otherwise it should have degree >=2. So you can remove this vertex and the only edge connecting it, and wouldn't decrease the number of cycles. Now you decreased number of vertices from k+1 to k, and by induction the graph with k vertices and k-1 edges do not have cycles. The proof is completed.

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

Not getting why this case 3 3 1 results in 0. I thought it should result in 2


#include <iostream> using namespace std; long long int util(long long int res, long long int p){ long long int mod= 1000000007; //cout<<res<<" "<<p<<endl; for(int i=2;i<=p;i++){ res= ((res%mod)* (i%mod))%mod; } return res; } int main() { int n,x,p; cin>>n>>x>>p; int mod= 1000000007; long long int res=1; int left=0,right=n-1; int g=n-x,l=x-1; while(left<right){ int middle= (right+left)/2; if(p<middle){ g--; res= ((res%mod)* (g+1))%mod; right= middle; }else if(p>middle){ l--; res=((res%mod)* (l+1))%mod; left= middle+1; }else{ res= util(res, g+l); break; } } cout<<res<<endl; }
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    exactly my doubt

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

      Notice that the index starts from zero. Following the code on the main text, we get 1. left=0, right=3, middle=1 -> a[1]<=3. 2. left=2, right=3, middle=2 -> a[2]>3(Impossible).

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

In C, why haven't they considered the permutation of the remaining numbers (those remaining after we find the given position after applying the given binary search)

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

Can someone please provide some similar problems like problem D ?? Thanks in advance.

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

I have got a verdict pretest passed on Problem B during contest time which has not changed till now, i.e., it has neither got a verdict W/A or AC rather the submission is still showing pretest passed. After the contest, I submitted the same solution again and get AC though the earlier is still showing pretest passed. What can be reason behind?

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

I have a code for problem E but its time limit exceeded on test 7. Is the question set in a way if we do not use a segment tree our time limit would exceed?

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

hey can anyone help me figure out what's wrong in my d's solution it's giving wrong ans on test case 87 96635681

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

In F how do you precalculate the multiplication of (sum of set with gcd i) into the answer?

I saw users such as neal using some mobius stuff but couldn't understand it. Can someone help me?

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

    You can check out the definition of the mobius function on wikipedia. What it allows you to do, is apply the principle of inclusion-exclusion on the prime factors of natural numbers. If you aren't familiar with the principle of inclusion-exclusion you can check it out on wikipedia or cp-algorithms.com

    Here we are able to separate out the target value over only the subsets whose gcd is 1 by applying the principle of inclusion-exclusion and eliminating the contribution from subsets whose gcd is greater than 1. We can do this by directly adding the contribution from all those subsets whose gcd have an even number of prime factors, and directly subtracting the contribution from all those subsets whose gcd have an odd number of prime factors. Note that we ignore the contribution from those subsets whose gcds are not square free. Where does the mobius function come in? It basically makes the choice for us (whether we need to add, subtract or ignore the contributions from the subsets having a certain gcd).

    I've implemented the solution in the editorial here.

    Hope this helps :)

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

A bit late, but here is the video editorial for E

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

Please, ¿can anyone explain more clear answer to problem C?, thank you very much.

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

    In binary search we check only some special numbers, and you know exactly which positions are being checked during the algorithm, also we have two pointers left and right and you now each time you want left to become mid or right to become mid. So now all you need is it choose which of those bigger numbers are going to be set in the positions that we declared for big numbers, and we will also do this for smaller ones. after that we have some positions that don't have to be a certain number so you can put either bigger number or smaller one. here's my submission for this problem.

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

Why we not using binary search in solving D- Bandit in City? Consider x is answer and allow x citizen at leaf node , if no of citizen in all non leaf node is 0 then return 1 or return 0.

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

For those who are interested in problem B analysis here's our short video with some logic that could have lead to a common solution.

Video link

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

I am stuck on problem C, I think there is some mistake in my code regarding overflow. I tried but couldn't find the bug, can someone please look at my code and tell me the bug — https://codeforces.net/contest/1436/submission/96759365

It is giving WA on 52nd test case.

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

In problem D I use dfs to calculate the answer from leaves to root. But it's wrong answer on test 7. Can someone give me a smaller example to debug?96761287

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

    I also get error in this instance. The difference between my answer and the correct solution was only 6 units. Could you see my code? 96808517 Thanks.

    I'm not sure but I think your variable tt should receive a ceil (a / step) in the following part.

    if(point[now].a>=point[now].step){ LL tt=point[now].a/point[now].step; point[now].a-=tt*point[now].step; point[now].baseline+=tt; point[now].gap=0; }

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

      It doesn't work. I have no idea. Maybe your variable slack (and my gap) will go wrong? Now I suspect that dfs is not suitable for this problem, because there are too many details to consider.

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

        Hi, I have solved the problem with dfs. My code was wrong because I didn't test (k%s.t) before.

        The following instance you can use to test your code. Your code answered 96 and correct solution is 92. I have tested with my code that was accepted.

        8 1 1 2 2 3 3 3 68 5 44 83 46 92 32 51

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

    same problem for me on same tc can u help me with my code? 96990704

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

F can be solved by using stirling。

In this way,now a set's contribution is S*(S-1),then contributions can be S^K。

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

Hi, Solution to problem 4 talks about Dirichlet principle, can anyone please explain what it is. I tried googling it but only found complex mathematical formulas.

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

    You really don't have to know it completely just for solving this problem ... we are using this just to prove that we have minimum when we try to divide them into equal parts or not more than 1 difference(also no matter how you'll change some of minimums into maximum) because you are going to minimize the maximum. but if you're so curious about "Dirichlet principle" check out this

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

can someone point out my mistake in D the tc i am getting wrong is too big i cant figure it out

solution : 96990704

Thanks!!

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

In problem A:

$$$\sum_{i=1}^{n} \sum_{j=i}^{n} \frac{a_j}{j} = \sum_{j=1}^{n} \sum_{i=1}^{j} \frac{a_j}{j} = \sum_{j=1}^{n} j \frac{a_j}{j} = \sum_{j=1}^{n} a_j$$$
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone can help me out on question E(1436E — Complicated Computations)???

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

Here is an alternative solution to D, it might be somewhere in the comments but damn.... it's a very very long discussion.

So, if we have to distribute a value x among an array which is sorted such that all the values increase uniformly. For example, if we add 5 to [2,3,4,4,4,5,7] it would become [4,4,4,5,5,5,7]. The conversion is pretty easy to imagine.You can use a map for this, keeping a check of frequencies and then performing a sweep and converting the array.

Now, every value inside the tree which is not a leaf node has to sent down into the leaves.We have to do this and also keep the maximal element in the leaves as minimum. So every non zero element that we get in the tree is like a query to the problem described above. Every node will have a set of leaves in it's domain and it's value is to be divided into those leaves. If we keep a map for each node, we will be able to do this with a simple traversal. For every node's left and right subtree, you just add the smaller map into the larger one before resuming the process. Since we are performing a sweep while trying to find the minimal maximum after each "query", we won't be needing more than O(N+Q) which translates to O(Nlog(N)).

I hope my solution was understandable, if not , please do comment and let me know.

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

103544534 for Problem D binary search seems to save some trouble considering whether a number divides.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

has anyone used small-to-large in D?

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

    I did try to use small to large, but getting TLE on test case 80

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

    Thanks bro! Your code helped me optimize my code and get an AC