Vladik's blog

By Vladik, 6 weeks 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

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

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

    yes, you are right i did same

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

    could you please explain a bit more. Thanks.

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

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

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

        yes thanks i got it but in editorial, they mentioned based on even odd. but there is no need of that right? how to come up solutions like this? i am always thinking brute like the way of same given in question. even i did brute for Question A today's contest initially.

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

          Brute forcing also requires some efforts, ( I suck at that tbh, couldn't even think of brute force way mostly) maybe it fits in time constraints in this one. Analysing the question helps in this case. Rather than jumping for implementation. A are mostly straightforward. and obv generating all possible numbers to fit your case in second is going to run in TLE.

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

            thanks. I couldn't even think brute most of the B problems as well. I heard that practicing only will become to understand the problems. how to identify which DS we have to for the questions?

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

        The sum of last columm ain't prime

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

      like if n=5 you can print 1 1 0 0 0 \n 0 1 1 0 0 \n 0 0 1 1 0 \n 0 0 0 1 1 \n 1 0 0 0 1 \n

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

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

    I also did this only:)

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

    you can also use 4,1 and 8. 96557902

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

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

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

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

        can anyone please tell why i am getting wrong answer in 6th test case DIV 2 -B here

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

          See The first mistake that you are making is 1 and 0 are not prime numbers. so isprime[0] = isprime[1] = false; But upto the six testcases there is no error because of this mistake. Then, where is the fault? The fault is where you are trying to find out the value of no. There you have bounded the loop to only run for n times which is not satisfied for n=25 because for n=25, no=35 as per your algorithm and no>n. So I think it is clear to you.

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

            //okay but for n=25


            no=0 loop 1 to n+1 if (isprime[n-1+i] and !isprime[i]) no=i

            /// no=9 satisfy condition

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

              How? see there are 24 1's in a row then the sum is 24 and when 9 is added to 24 it becomes 33 which is not a prime number.

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

                ohhh shit,, thanks man now got it, should not bound the loop

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

    So did I.

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

    I used the number 9 instead.

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

    lol

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

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

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

96560594 Solution B. You bulid a temp. array of [1,1]+[0]*(n-2). EX- [1,1,0,0,0] Print it right rotation by n-times This is for both n-odd or n-even

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

  • »
    »
    6 weeks 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
    
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      i did the exact same way :)

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

        yes same i did but it show wrong why?

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

          I first precalculated prime numbers using sieve upto 10000. Then the value of d as shown by you is chhosen in such a way that d is not prime and the( sum of 1's in the row + d) is prime... Thats all i did.. u may refer my solution for more clarity :)

»
6 weeks ago, # |
  Vote: I like it +61 Vote: I do not like it

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

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

    • »
      »
      »
      6 weeks 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]$$$?

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

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

      Can you tell your approach for D and the theoram mentioned in editoriol standard in cp??

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

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

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

    What actually is test 10?

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

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

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

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

            h = 6 and l = 0 so mid = 3

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

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

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

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

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

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

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

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

          The actual answer should be 72. The array (1, 4, 5, 3, 2, 6) has the number 3 at the 3rd position (0-based indexing as given in the sample cases), however, upon running the BinarySearch function for this array, the output is false. In the first iteration. left = 0, right = a.size() = 6 and middle = (left + right)/2 = 3. So, a[middle] will find the number(3) in the first iteration only, but then left will change to middle+1 which is 4. Hence, the number at position 4th must be greater than the number to be found which is 3. There are 3 such numbers, hence we have to choose one of the three at position 4 and we can arrange the remaining 4 in any way, hence the answer should bee 3*4! = 72.

    • »
      »
      »
      6 weeks 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!

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

        Yes we shoudn't have break the loop if mid==pos. That is why i also got failed in test 10.

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

          Even if you break the loop, the if statement below will take care of that.

          For input 3 3 1, answer should be 2.

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

            yes, the two is {1,3,2} {2,3,1} but how they get answer 0

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

              In these cases left value would be 3 and right value would be 3 and then the loop would break and a[left-1]!=x therefore its false

              apply binary search according to algo given in question

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

          Why?

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

      actually while considering they didn't observe that there can be cases where no permutation is possible, the no. of permutation will be zero. for example n=10 ,x=10,pos=0.

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

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

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

      Actually the thing is they changed the definiton of binary search it won't stop even if it finds the element. And the test case is 3 3 1 so if we break when mid==pos it shows wrong ans.

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

        if we don't break then the value for test cases 1 & 2 also don't match as what it is given as answers

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

          yes agreed answers dont match then get zero there

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

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

      nonsense

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

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

      what's the criteria between weak pretest or not?

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

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

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

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

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

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

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

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

      thanks for the great explanation

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

      great explanation

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

      Thanks for your amazing explanation!

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

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

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

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

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

      My code passed all test cases except testcase: 78 can u help me. I got an AC because i simply printed the correct ans for testcase 78. Here is my code ; https://codeforces.com/contest/1436/submission/96776940

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

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

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

    I think it is another name for pigeonhole principle.

  • »
    »
    6 weeks 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;

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

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

Anyone else failed test case 51 of C? What was wrong?

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

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

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

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

»
6 weeks 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!

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

»
6 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

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

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

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

    1 is not prime.

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

    1 is not prime :) and its given in problem that sum should be prime

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

»
6 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

How to solve C??

  • »
    »
    6 weeks 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!

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

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

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

          I think even if you break the loop, the if statement below will take care of that.

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

            The if statement below is outside of the while loop. So it will check a[3-1] element. Which is definitely not 3.

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

        Exactly dude... I'm stuck thinking about it as well!

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

      "then we need to place a element which is bigger than our given element otherwise we need to place a smaller element there"

      Why do you need to place an element which is bigger there? Why is this bad?

      "We will count how many places there are where we can place smaller element and bigger element. "

      How do I know where I can put them? How do I know how many spaces? (Unless this is the first question)

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

      Thank you, well explained.

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

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

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

First time i failed system test in codeforces . Problem C [Test 10] :(

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

    what is exactly 'system test'?

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

      During the contest, we are only given a few presests so that the queue during the contest is not long. After the contest, another test case will be given for participant submissions, this test case is called a system test

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

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

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

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

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

Oh My Goodness... Thank you so much for such a fast editorial.

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

can some one tell me about Dirichlet principle ?? any link for the study resources ??

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

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

    I'm confused too. Can someone clarify please?

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

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

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

      I think they have made some mistake. Since middle element can be found in a single step, "1 3 2" and "2 3 1" should be valid permutations.

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

        no,according to image, 1 3 2 and 2 3 1 will make the BinarySearch function return false,for example 1 3 2

        left=0,right=3,then middle=1,we check a[middle] is 3,then left=middle+1=2.Then middle=2,we check a[middle]=2 which 2<=3 then left=middle+1=3,then it will exit the while loop because left=right.After that we look at a[left],is a[left]=3?no because left=1,then BinarySearch function will return false as the result

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

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

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

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

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

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

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

    You could notice that their dumb algorithm goes on even after finding the mid element..(suggested by smax) Even my code failed on test 10. Just change your smaller condition to make it a wrong BS like they desire.... like so :

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

      Yeah algorithm was not exactly same but I wrote exactly same algo as per pseudocode.It passed.

      Code
  • »
    »
    6 weeks 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

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

    I'm also confused answer should be 0 only

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

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

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

    lets execute step by step the code on first example "1 3 2":
    a[3]={1,3,2}
    l=0, r=3
    iteration 1:
    middle = (3+0)/2 = 1
    a[middle]=a[1]=3 is less than or equal than 3 then l=middle+1=2
    iteration 2:
    middle = (2+3)/2 = 2
    a[middle]=a[2]=2 is less than or equal than 3 then l=middle+1=3
    we end the iterations
    l=3
    Then on line 11 of the code, left is greater than 0, but a[l]=a[3]=2 is not 3
    hence we return false.
    the same apply to the second case, good fortune!!!.

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

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

The problems were good...though queues, delays and FST's on C sucked. Also I become specialist for the first time after this round...so thanks but no thanks.

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

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

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

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

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

    The contest was extended for 10 minutes. So don't see a big problem there.

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

why am getting wrong answer on 6th test case of DIV2 B here

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

In problem A some have gotten Runtime error on test 4.They used sum ℅ m. But when m=0 it's impossible to do sum % m.

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

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

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

»
6 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

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

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

In problem C what about cases like n=5 x=5 and pos=0 is there any way binary search still can find x? where am i going wrong? as in this case all others are less than 5 so how do we position them such that binary search can find it

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

For Binary Search Problem, For Input-3 3 1, why the answer is 0 and not 2 ??

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

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

    This comment made me feel good and sad at the same time :(:)

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

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

    I think there is Long Long integer overflow

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

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

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

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

          Thanks, i got it now.

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

            I also used Binary Search. I use python so there is no overflow issue. But I'm getting TLE with my PyPy2 Submission. Can u please help me identify, why im getting TLE. Code (N*log(2*int(1e15))): https://codeforces.com/contest/1436/submission/96719990

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

              I guess the time limit of 1 sec is to prevent usage of binary search. This is my AC Submission. It takes ~900ms with C++.
              So, with PyPy, I guess it cannot pass.

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

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

    Can you please explain your binary search solution in detail?

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

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

Binary search soln for D 96602832

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

    pseudocode was given in python ????

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

    Come on!

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

    Does Pseudocode have any programming language??

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

    Though your logic is stupid but I still wish for this round to get unrated due to queues in the starting and weak pretests for problems.

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

    Just another regular person BSing because he dropped rating OK.

»
6 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

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

  • »
    »
    6 weeks 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. ;___;

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

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

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

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

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

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

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

      Yes, I think. When I solve a problem, I get some logic about maths, or implementation, or new algorithms or get heavy fun after solving. But in this problem I am not getting any logic why should I continue searching even if I find my desired value on the desired pos. It's like they said us to do, and we have to.. No fun at all

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

    That is a part of problem statement to make the problem slightly more harder to implement. As far as the relevance of that problem to real life goes, it is as equivalent to a problem where the statement goes like "Vasya would like to flip exactly k zeroes" do people actually flip zeroes in real life?

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

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

    Why there is no bracket for while loop?

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

      identation exists for something. That is pseudocode.

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

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

»
6 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

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

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

»
6 weeks 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).

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

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

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

Solution for D failed system test, because of Tle in case-56, though it passed the testcase 5, for similar value of n. Solution

can anyone explain why this happened?

»
6 weeks 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)

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

»
6 weeks ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

Someone, please provide the code for D.

»
6 weeks 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).

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

why binary search is not working in problem D??

»
6 weeks 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.com/contest/1436/submission/96608378

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

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

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

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

»
6 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

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

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

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

Can someone please explain binary search solution for D?

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

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

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

    could you explain your approach please??

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

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

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

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

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

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

»
6 weeks 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 :)

»
6 weeks 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;

}

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

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

      Ohh ho...thanks I will take care of it. then how to compare decimal numbers?

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

        In this case, if you observe carefully then only needed condition for YES is sum of all elements of array == m. In general, always try to avoid comparing decimals numbers. Usually problems don't require comparing decimal numbers. But if you want to compare them then you should consider their fractional forms (a/b form) .

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

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

Can anyone Explain D?

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

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

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

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

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

»
6 weeks 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 :)

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

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

»
6 weeks 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) ?

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

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

In B, I used a different approach. Setting 0 (zeros) in all but 2 rows and columns and then setting 1s in the remaining columns this fixes most of the position of the matrix. However, now you need to only fix 2 positions of the matrix.

Here's an example,
0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 1 1 
0 0 0 0 0 0 0 1 1 
1 1 1 1 1 1 1 1 _ 
1 1 1 1 1 1 1 _ 1 

Only the highlighted positions need to be calculated. This can be done by

Loop{          
      if (!isPrime(i) && isPrime(i + n - 1))
       {
           numAtPosition = i;
           break;
       }
}

where isPrime() checks if a number is prime or not and n is the number columns/rows of the matrix. So now I just need to find a number let's say 'i' is NOT prime and (n - 1) + (i) is a prime (final i), same is written in the if statement.

Link to contest submission

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

For B question my logic is here: For even n: 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

For odd n: 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1

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

Hello in Problem C my approach for the problem- 1.Here as one digit stays at a particular position and all other digits can interchange their positions — so using combinatrix I find the combinations of all numbers of left and to the right.

1st test case- 4 1 2

Here — the array looks like this 0 0 1 0

So I have left with three numbers (2 3 4) and two positions(left — 2 and right — 1).

So simply print the ncr(n-1,x) + ncr(n-1,n-x).

I don't get the cntBig hasBig terms here.

Anyone help me here what am I missing?

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

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

    If n is prime then we can print all 1. Else, print 1 for up to n-1 rows and columns. Then iterate from i=1-100 and check if prime(i)==false&&prime(n-1+i)==true. This value will be printed in the last row and column except i==n&&j==n. Again iterate from i=1-100 to find the last value, this will be if prime(i)==false&&prime((n-1)*previous_value+i)==true.

    For more clarification: https://codeforces.com/contest/1436/submission/96566675

  • »
    »
    6 weeks 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!

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

Anybody please help me with C problem!

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

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

In B you can solve by the following pattern :

if n is even then

1 0 0 0 0 1 /n 0 1 0 0 1 0 /n 0 0 1 1 0 1 /n 0 1 0 0 1 0 /n 1 0 0 0 0 1 /n

if n is odd

1 0 1 0 1 /n 0 1 0 1 0 /n 1 0 1 0 1 /n 0 1 0 1 0 /n 1 0 1 0 1 /n

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

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

Someone wrote C solution with python?

I figured it out pretty quickly but couldn’t get the exact solution! somehow I messed up the calculations.. Will be better next time :)

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

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

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

    exactly my doubt

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

»
6 weeks 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)

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

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

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

    Create a blog entry and ask the same question there. Also, if possible, add the submission link and an image of the problem's verdict in your blog entry. Most users do not check the replies in the editorial sections.

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

»
</