By Vladik, 19 months ago, translation,

Author: aropan

author's solution: 96602393

Author: AleXman111

author's solution: 96598752

Author: AleXman111

author's solution: 96598711

Author: hloya_ygrt

author's solution: 96727317

Author: andrew

author's solution: 96601544

Author: hloya_ygrt

author's solution: 96727345

P.S. We will add our own solutions soon

• +118

 » 19 months ago, # | ← Rev. 3 →   +70 In B you can also use 1 1 0 0 0 0 0 0 0 0 ... and cycle shift one unit every time
•  » » 19 months ago, # ^ |   +8 yes, you are right i did same
•  » » 19 months ago, # ^ |   0 could you please explain a bit more. Thanks.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +3 11000 10001 00011 00110 01100 it is cylcing, and you get all row and column having equal sum
•  » » » » 19 months ago, # ^ | ← Rev. 3 →   +3 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 
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +19 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
•  » » » » 19 months ago, # ^ |   0 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.
•  » » » » » 19 months ago, # ^ |   0 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.
•  » » » » » » 19 months ago, # ^ |   0 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?
•  » » » » 19 months ago, # ^ |   0 The sum of last columm ain't prime
•  » » » » » 19 months ago, # ^ |   0 sorry corrected now.
•  » » » » » 19 months ago, # ^ |   0 the sum of last column not prime? why so?
•  » » » 19 months ago, # ^ |   -8 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
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 1 1 0 0 01 1 0 0 01 1 0 0 01 1 0 0 01 1 0 0 0in every row and column answer is 2
•  » » » » 14 months ago, # ^ |   +1 in column how answer is two?
•  » » » » 14 months ago, # ^ |   0 Sorry, wrote it many months ago, it is wrong.
•  » » 19 months ago, # ^ |   0 I also did this only:)
•  » » 19 months ago, # ^ |   0 you can also use 4,1 and 8. 96557902
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 19 months ago, # ^ |   0 last column have only one "1". it's not a prime
•  » » » » 19 months ago, # ^ |   0 Sorry for the little mistake. Fixed it. See again.
•  » » 19 months ago, # ^ |   0 Problem B would have been slightly more interesting if instead of non-negative numbers, we were only allowed positive numbers.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 19 months ago, # ^ |   0 can anyone please tell why i am getting wrong answer in 6th test case DIV 2 -B here
•  » » » » » 19 months ago, # ^ |   0 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.
•  » » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 //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
•  » » » » » » » 19 months ago, # ^ |   0 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.
•  » » » » » » » » 19 months ago, # ^ |   0 ohhh shit,, thanks man now got it, should not bound the loop
•  » » 19 months ago, # ^ |   0 So did I.
•  » » 19 months ago, # ^ |   0 I used the number 9 instead.
•  » » 19 months ago, # ^ |   0 lol
 » 19 months ago, # |   0 C(hasBig,cntBig)⋅cntBig! What does this C means in question 1436C?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +2 nCr Combination
•  » » » 19 months ago, # ^ |   +9 Why he didn't use A(n,r)
•  » » 19 months ago, # ^ |   +3 Combination nCr=C(n,r)
•  » » 19 months ago, # ^ |   0 It is combination.
•  » » 19 months ago, # ^ |   +16 Also, notice that $nCr \times r! = nPr$
•  » » 19 months ago, # ^ |   0 It's for Combination Number
 » 19 months ago, # | ← Rev. 2 →   0 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
 » 19 months ago, # |   0 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
•  » » 19 months ago, # ^ | ← Rev. 4 →   +3 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 
•  » » » 19 months ago, # ^ |   +3 i did the exact same way :)
•  » » » » 19 months ago, # ^ |   0 yes same i did but it show wrong why?
•  » » » » » 19 months ago, # ^ |   0 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 :)
 » 19 months ago, # |   +61 Sorry but can you explain E's solution a little more clearer
•  » » 19 months ago, # ^ |   +82 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$.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +6 What these queries look like? What do we want to request for $[l, r]$?
•  » » » » 19 months ago, # ^ |   +14 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)$".
•  » » » » » 19 months ago, # ^ |   0 Thank you
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 Got it by Offline. if you have another way Please Make sure to share it :P
•  » » » 19 months ago, # ^ |   0 Can you tell your approach for D and the theoram mentioned in editoriol standard in cp??
•  » » » 18 months ago, # ^ |   0 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
 » 19 months ago, # |   +39 Weak pretests for C. Huge number of people getting WA on test 10.
•  » » 19 months ago, # ^ |   +1 What actually is test 10?
•  » » » 19 months ago, # ^ |   +6 Should probably be something like 6 3 3. Actual answer should give 36, people who failed system tests, their answer is 120.
•  » » » » 19 months ago, # ^ |   0 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.
•  » » » » » 19 months ago, # ^ |   0 On the first iteration it will return 2 as mid (because its 0 indexed)
•  » » » » » » 19 months ago, # ^ |   +7 h = 6 and l = 0 so mid = 3
•  » » » » » » » 19 months ago, # ^ |   0 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.
•  » » » » » » » » 19 months ago, # ^ |   +6 Yes I understand. The image in the problem was not accurate that confused to take h = a.size()
•  » » » » » » » » 19 months ago, # ^ |   +4 But in the problem statement h=a.size()
•  » » » » » » » » 19 months ago, # ^ |   +4 In actual it should have been a.size()-1 in the problem but as it was given a,size()..it did with that.
•  » » » » » » » » » 19 months ago, # ^ |   0 Yeah they explicitly mention it to be h instead of h — 1
•  » » » » » 19 months ago, # ^ |   0 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.
•  » » » 19 months ago, # ^ |   0 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!
•  » » » » 19 months ago, # ^ |   +3 Yes we shoudn't have break the loop if mid==pos. That is why i also got failed in test 10.
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   +4 Even if you break the loop, the if statement below will take care of that.For input 3 3 1, answer should be 2.
•  » » » » » » 19 months ago, # ^ |   +4 yes, the two is {1,3,2} {2,3,1} but how they get answer 0
•  » » » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 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 falseapply binary search according to algo given in question
•  » » » » » 19 months ago, # ^ |   0 Why?
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 19 months ago, # ^ |   +1 Can you please tell what is actually test case 10 in C?
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 if we don't break then the value for test cases 1 & 2 also don't match as what it is given as answers
•  » » » » » 19 months ago, # ^ |   0 yes agreed answers dont match then get zero there
•  » » 19 months ago, # ^ |   -52 When the pretests are so weak, the round should be unrated. I failed systest on C.
•  » » » 19 months ago, # ^ |   +47 nonsense
•  » » » 19 months ago, # ^ |   +24 It's clearly mentioned that your solution may pass the pretest but doesn't mean that it will pass system testing for sure.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +30 what's the criteria between weak pretest or not?
 » 19 months ago, # |   +1 What is av and maxi(sum(av)/leaf(si)) in problem D? Can someone elaborate?
 » 19 months ago, # |   +12 Can someone give a more clear explanation of Editorial of D.
•  » » 19 months ago, # ^ | ← Rev. 3 →   +33 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.
•  » » » 19 months ago, # ^ |   0 Whiplash99 can you tell how this solution is correct? It did not use the DFS order for traversal.
•  » » » » 19 months ago, # ^ | ← Rev. 3 →   +13 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.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 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. submissionWhat I've done ispostorder 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.
•  » » » » 19 months ago, # ^ |   0 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$.
•  » » » 19 months ago, # ^ |   +6 thanks for the great explanation
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +3 great explanation
•  » » » 19 months ago, # ^ |   0 Thanks for your amazing explanation!
•  » » » 19 months ago, # ^ |   0 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??
•  » » » » 19 months ago, # ^ |   0 "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.
•  » » » 19 months ago, # ^ |   0 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 ?
•  » » » » 19 months ago, # ^ |   +1 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.
•  » » » 19 months ago, # ^ |   0 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
•  » » » 17 months ago, # ^ |   +3 Thanks for the amazing explanation !
•  » » 19 months ago, # ^ |   +12 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.
 » 19 months ago, # |   +2 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?
•  » » 19 months ago, # ^ |   +3 I think it is another name for pigeonhole principle.
•  » » 19 months ago, # ^ |   0 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;
 » 19 months ago, # |   0 Man this contest problem were used in a official contest .. Such a shame having such pretest for C
 » 19 months ago, # |   0 Anyone else failed test case 51 of C? What was wrong?
 » 19 months ago, # |   +7 Why doesn't C consider the permutations of the numbers not part of hasBig and hasLess?
•  » » 19 months ago, # ^ | ← Rev. 2 →   +11 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.
•  » » » 19 months ago, # ^ |   +3 Just a small correction, it should be $(n - cntBig - cntLess -1)$ factorial
 » 19 months ago, # |   0 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!
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 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.
 » 19 months ago, # |   -10 weak pretest !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 » 19 months ago, # |   -23 Weak Pretests, Long Queues, Unexpected Errors and Rated :(. Make it Unrated :P
 » 19 months ago, # | ← Rev. 4 →   0 in B it says there are no prime numbers in the square.
•  » » 19 months ago, # ^ |   +1 1 is not prime.
•  » » 19 months ago, # ^ |   0 1 is not prime :) and its given in problem that sum should be prime
•  » » 19 months ago, # ^ |   0 People be mourning to the rip case of C and random guy be like : 1 iS PrImE .. Man come on revise your maths lessons
 » 19 months ago, # |   -8 How to solve C??
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 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!
•  » » » 19 months ago, # ^ |   +1 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.
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +3 Notice that in the given code, they used, if(a[middle]<=x) then left=middle+1for the first iteration, middle = (0+3)/2 = 1 and left = middle+1 = 2for the second iteration, middle = (2+3)/2 = 2 and left = middle+1 = 3So, it will never find 3.
•  » » » » » 19 months ago, # ^ |   0 I think even if you break the loop, the if statement below will take care of that.
•  » » » » » » 19 months ago, # ^ |   0 The if statement below is outside of the while loop. So it will check a[3-1] element. Which is definitely not 3.
•  » » » » » 7 months ago, # ^ |   0 but when left=2 after 1 iteration a[left-1]=3 and it will break after 1st iteration.
•  » » » » 19 months ago, # ^ |   0 Exactly dude... I'm stuck thinking about it as well!
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 "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)
•  » » » » 19 months ago, # ^ |   0 Because if you place a smaller element there then, if(a[middle]<=x) condition will be true and you will go to right and you will never find the given element.
•  » » » » 19 months ago, # ^ |   0 We will count that in the binary search. For better understanding you can see my code. https://codeforces.com/contest/1436/submission/9658029
•  » » » 19 months ago, # ^ |   +1 Thank you, well explained.
•  » » » 19 months ago, # ^ |   0 Thankyou so much <3 I finally understand how to solve C
 » 19 months ago, # |   0 First time i failed system test in codeforces . Problem C [Test 10] :(
•  » » 19 months ago, # ^ |   0 what is exactly 'system test'?
•  » » » 19 months ago, # ^ |   0 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
 » 19 months ago, # |   0 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
 » 19 months ago, # |   +42 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
•  » » 19 months ago, # ^ |   0 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
•  » » » 19 months ago, # ^ |   +1 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.
•  » » » » 19 months ago, # ^ |   0 Thanks, Got it.
 » 19 months ago, # |   0 Oh My Goodness... Thank you so much for such a fast editorial.
 » 19 months ago, # |   0 can some one tell me about Dirichlet principle ?? any link for the study resources ??
 » 19 months ago, # |   +11 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.
•  » » 19 months ago, # ^ |   0 I'm confused too. Can someone clarify please?
•  » » » 19 months ago, # ^ |   +3 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
•  » » 19 months ago, # ^ |   0 Yea the first middle would be one right ? Can someone help what makes this test to have answer zero ?
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 19 months ago, # ^ |   0 no,according to image, 1 3 2 and 2 3 1 will make the BinarySearch function return false,for example 1 3 2left=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
•  » » » » » 19 months ago, # ^ |   0 Yes I got it now. Thanks btw
•  » » » » » 11 months ago, # ^ |   0 Thanks man now i got it take me two days frustation ;_;
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Exactly ! I also don't understand why the answer should be zero. Edit:- Leave it I found where I was wrong.
•  » » 19 months ago, # ^ |   +3 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.
•  » » » 19 months ago, # ^ |   0 How? I implemented their binary search function and it succeeds in finding 3. Idk what's wrong
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 Thanks, I am dumb!
•  » » 19 months ago, # ^ |   0 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.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 For 1 3 2 , No , Because mid=(3+0)/2=1 a[1]<=x left=2 now, mid=(2+3)/2=2; a[2]
•  » » 19 months ago, # ^ |   0 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//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i fact(maxn,0); ll bin(ll a, ll b) { a%=mod; ll res = 1; while (b > 0) { if (b & 1) res = res * a % mod; //mod a = a * a % mod; //mod b >>= 1; } return res; } void fac() { fact[0]=1; for(ll i=1;i> n >> x >> pos; ll l = 0; ll r = n; vector a(n,0); while(l=m){ a[m]=1; //x r=m; } } a[pos]=-1; ll low=0,high=0; for(i=0;i
•  » » » 19 months ago, # ^ |   0 Yeah algorithm was not exactly same but I wrote exactly same algo as per pseudocode.It passed. Code long less = (x-1); long more = (n-x); long moves = 1; if(n == 1){ System.out.println("1"); return; } while(left < right){ int middle = (left+right)/2; if(middle <= pos){ if(middle < pos){ // System.out.println(less); moves = (moves * less)%mod; less -= 1; } left = middle + 1; } else{ moves = (moves * more)%mod; more -= 1; right = middle; } } long num = (less+more); for(long i = num-1 ; i > 0 ; i--) num = ((num * i)%mod); long ans = (moves * num)%mod; System.out.println(ans); 
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   0 deleted
•  » » 19 months ago, # ^ |   +3 in case of 2 3 1 wouldfirst iteration mid = 1 and 3<=x thus left = 2 and right = 3second iteration mid = 2 and 1<=x thus left = 3 and right = 3here you can clearly see left becomes 3 and a[3-1] != x thus it returns false
•  » » 19 months ago, # ^ |   0 I'm also confused answer should be 0 only
•  » » 19 months ago, # ^ |   0 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.
•  » » 19 months ago, # ^ |   0 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
•  » » 19 months ago, # ^ |   0 lets execute step by step the code on first example "1 3 2":a[3]={1,3,2}l=0, r=3iteration 1:middle = (3+0)/2 = 1a[middle]=a[1]=3 is less than or equal than 3 then l=middle+1=2iteration 2:middle = (2+3)/2 = 2a[middle]=a[2]=2 is less than or equal than 3 then l=middle+1=3we end the iterationsl=3Then on line 11 of the code, left is greater than 0, but a[l]=a[3]=2 is not 3hence we return false.the same apply to the second case, good fortune!!!.
 » 19 months ago, # |   0 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
 » 19 months ago, # |   0 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.
 » 19 months ago, # |   +32 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
 » 19 months ago, # | ← Rev. 2 →   -34 Weak pretests for C and E,I get failed system test in my other account.rank 9 -> rank 500+ :(Hope for strong pretests.
•  » » 19 months ago, # ^ |   +41 "in my other account" you dont deserve to have better pretests, as you are ruining the contest for actual div2 contestants.
 » 19 months ago, # |   0 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.
•  » » 19 months ago, # ^ |   +5 The contest was extended for 10 minutes. So don't see a big problem there.
 » 19 months ago, # | ← Rev. 2 →   0 why am getting wrong answer on 6th test case of DIV2 B here
•  » » 19 months ago, # ^ |   0 Help needed
 » 19 months ago, # | ← Rev. 2 →   0 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.
 » 19 months ago, # |   0 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
•  » » 19 months ago, # ^ |   0 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.
•  » » » 19 months ago, # ^ |   0 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$
 » 19 months ago, # |   +26 Editorial of E is just too short. Please elaborate a little. Thanks .
 » 19 months ago, # |   0 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
•  » » 19 months ago, # ^ |   0 The answer will be 0 for those cases.
 » 19 months ago, # |   0 For Binary Search Problem, For Input-3 3 1, why the answer is 0 and not 2 ??
 » 19 months ago, # |   +18 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 ?
•  » » 19 months ago, # ^ |   0 This comment made me feel good and sad at the same time :(:)
 » 19 months ago, # |   0 In problem D, I used binary search. What is wrong with this logic? Submission
•  » » 19 months ago, # ^ |   +4 I think there is Long Long integer overflow
•  » » » 19 months ago, # ^ |   0 No, I am sure that all values are less than 2e14.
•  » » » » 19 months ago, # ^ |   +22 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.
•  » » » » » 19 months ago, # ^ |   0 Thanks, i got it now.
•  » » » » » » 19 months ago, # ^ |   0 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
•  » » » » » » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   +6 Alas I wasted a lot of time on the Binary Search Solution for D, missed the obvious solution.
•  » » 19 months ago, # ^ |   0 Can you please explain your binary search solution in detail?
•  » » » 19 months ago, # ^ | ← Rev. 4 →   +6 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
 » 19 months ago, # |   +3 Binary search soln for D 96602832
•  » » 19 months ago, # ^ |   0 Can you please explain idea behind your binary search solution , i am bad at understanding from code.
•  » » » 19 months ago, # ^ |   +3 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
•  » » » » 19 months ago, # ^ |   0 could you pls elaborate a bit about function f()... I'm not getting the if conditions
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   0 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).
 » 19 months ago, # |   0 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
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 (0,3) — 1(2,3) — 2(3,3)Result will be false
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 Can you explain it? What do you mean by "first middle". (0 + 3)/2 = 1 isn't it
•  » » » » 19 months ago, # ^ | ← Rev. 3 →   0 Fixed it
•  » » » » » 19 months ago, # ^ |   0 there are 3 elements
•  » » » » » » 19 months ago, # ^ |   -8 btw got the logic, they used different version of binary search in which you have to make log(n) iterations always for the result
•  » » » 19 months ago, # ^ |   0 Can you please explain idea behind your binary search solution , i am bad at understanding from code.
•  » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   0 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.
•  » » 19 months ago, # ^ |   +8 You should check the comments first. This issue has been discussed already in a ton of comments above.
•  » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   -9 In my opinion, no one should fail system tests because of overflow and an overflow case should always be included in pretests.
•  » » 19 months ago, # ^ |   +9 Here are 0 fcks for your opinion.
 » 19 months ago, # |   0 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.
 » 19 months ago, # | ← Rev. 3 →   -26 .
•  » » 19 months ago, # ^ |   +6 pseudocode was given in python ????
•  » » 19 months ago, # ^ |   0 Come on!
•  » » 19 months ago, # ^ |   0 Does Pseudocode have any programming language??
•  » » 19 months ago, # ^ |   -10 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.
•  » » 19 months ago, # ^ |   +2 Just another regular person BSing because he dropped rating OK.
 » 19 months ago, # |   +47 Please, never implement Binary Search as same as in problem C.
•  » » 19 months ago, # ^ |   +3 I was solving C with my own implementation of BS lol, while(l <= r) { ... } then realized its different, still failed for system test. ;___;
 » 19 months ago, # |   0 Such cute problems. =DJust 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.
•  » » 19 months ago, # ^ |   0 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.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +3 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. =DP.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$.
•  » » » » 19 months ago, # ^ |   0 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?)
 » 19 months ago, # |   0 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.
•  » » 19 months ago, # ^ | ← Rev. 2 →   +11 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?
•  » » » 19 months ago, # ^ |   0 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
•  » » 19 months ago, # ^ |   0 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?
 » 19 months ago, # |   0 I think most of us considered that if left>0 and a[left-1]==x then return trueelse 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...
•  » » 19 months ago, # ^ |   0 Why there is no bracket for while loop?
•  » » » 19 months ago, # ^ |   +3 identation exists for something. That is pseudocode.
•  » » 19 months ago, # ^ |   +3 This makes no sense, it would return false if it didn't find the element in the first step.
•  » » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   +22 Can someone explain me how to solve task E with segment tree?
•  » » 19 months ago, # ^ |   +3
 » 19 months ago, # |   +3 D has "binary search" in tags, have someone solved it in this way?
•  » » 19 months ago, # ^ |   +1
•  » » » 19 months ago, # ^ |   0 Could you please explain your solution?
•  » » » » 19 months ago, # ^ |   0
 » 19 months ago, # |   0 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).
•  » » 19 months ago, # ^ |   +6 You can cycle $1,1$ instead of $50,51$ as $2$ is prime as well :P
 » 19 months ago, # |   0 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
 » 19 months ago, # | ← Rev. 2 →   0 Solution for D failed system test, because of Tle in case-56, though it passed the testcase 5, for similar value of n. Solutioncan anyone explain why this happened?
 » 19 months ago, # |   0 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)
•  » » 19 months ago, # ^ |   +9 Since there are $O(n)$ solutions (including the official one), I believe that this time limit is quite reasonable ...
 » 19 months ago, # | ← Rev. 2 →   -11 Someone, please provide the code for D.
•  » » 19 months ago, # ^ |   0
 » 19 months ago, # |   +3 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 : 96604363The type of test cases where it will go for 2^n complexity :5930 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).
 » 19 months ago, # |   +3 why binary search is not working in problem D??
 » 19 months ago, # |   0 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
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 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 4In 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.
•  » » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   +1 Can anyone tell, In C problem, how answer of 9 4 4 is 7200.
•  » » 19 months ago, # ^ |   0 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
 » 19 months ago, # |   +27 problem E how to get the mex using segment tree ??
•  » » 19 months ago, # ^ |   +20 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.
•  » » » 19 months ago, # ^ |   0 great thanks :)
 » 19 months ago, # |   0 Can someone please explain binary search solution for D?
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 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
 » 19 months ago, # |   +3 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.
•  » » 19 months ago, # ^ |   0 could you explain your approach please??
•  » » » 19 months ago, # ^ |   0 I have explained it above, if you any doubts, you can ask me.
•  » » 19 months ago, # ^ |   0 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?
•  » » » 19 months ago, # ^ |   +5 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.
•  » » » » 19 months ago, # ^ |   0 Oh yes I never thought that way. Got it accepted. Thanks a lot man.
 » 19 months ago, # |   0 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}.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Just pointing out an issue in the problem, what's about all these downvotes:)
 » 19 months ago, # |   +14 Problem E can be done with Persistent Segment Tree and you don't have to bother with ordering the queries :)
»
19 months ago, # |
-34

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;


}

•  » » 19 months ago, # ^ |   +3 It is because of double. You should never compare double variable with any double/int variable. This is due to precision errors.
•  » » » 19 months ago, # ^ |   0 Ohh ho...thanks I will take care of it. then how to compare decimal numbers?
•  » » » » 19 months ago, # ^ |   0 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) .
 » 19 months ago, # | ← Rev. 3 →   0 ㅤ
 » 19 months ago, # |   0 Can anyone Explain D?
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » 19 months ago, # ^ |   0 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.
•  » » » 19 months ago, # ^ |   0 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.
•  » » 19 months ago, # ^ |   0 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.
 » 19 months ago, # |   +37 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.
•  » » 19 months ago, # ^ |   +14 +++ this
 » 19 months ago, # |   0 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 :)
•  » » 19 months ago, # ^ |   0 very fast announcement claimed it.
 » 19 months ago, # | ← Rev. 3 →   0 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
•  » » 19 months ago, # ^ |   0 Found the problem, the solution 96682324 has the correction.
 » 19 months ago, # |   0 For E, how do we process the occurrences in order using segment tree?
 » 19 months ago, # | ← Rev. 3 →   0 C(hasBig,cntBig)⋅cntBig! ,is that equal to P(hasBig,cntBig) ?
•  » » 19 months ago, # ^ |   0 I think so.
 » 19 months ago, # |   0 Need help. In D, I got WA on test 77 and I don't really get what's wrong with my code.
 » 19 months ago, # | ← Rev. 2 →   0 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
 » 19 months ago, # |   0 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 1For 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
 » 19 months ago, # | ← Rev. 3 →   0 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 2Here — the array looks like this 0 0 1 0So 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?
 » 19 months ago, # | ← Rev. 2 →   0 Can anyone tell me how to solve Problem B, if we are allowed to fill only positive numbers?
•  » » 19 months ago, # ^ |   0 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
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 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!
 » 19 months ago, # |   0 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 /nif 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
 » 19 months ago, # | ← Rev. 4 →   0 I solved B with a cool sequence 1, 4, 6, 8, 10, 12, 18, 20, ... see my codeto 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
 » 19 months ago, # | ← Rev. 2 →   0 Not getting why this case 3 3 1 results in 0. I thought it should result in 2 #include using namespace std; long long int util(long long int res, long long int p){ long long int mod= 1000000007; //cout<>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(leftmiddle){ l--; res=((res%mod)* (l+1))%mod; left= middle+1; }else{ res= util(res, g+l); break; } } cout<