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
In B you can also use 1 1 0 0 0 0 0 0 0 0 ... and cycle shift one unit every time
yes, you are right i did same
could you please explain a bit more. Thanks.
11000
10001
00011
00110
01100
it is cylcing, and you get all row and column having equal sum
I did this :
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
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.
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.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?
The sum of last columm ain't prime
sorry corrected now.
the sum of last column not prime? why so?
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
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
in column how answer is two?
Sorry, wrote it many months ago, it is wrong.
I also did this only:)
you can also use 4,1 and 8. 96557902
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
last column have only one "1". it's not a prime
Sorry for the little mistake. Fixed it. See again.
Problem B would have been slightly more interesting if instead of non-negative numbers, we were only allowed positive numbers.
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.
can anyone please tell why i am getting wrong answer in 6th test case DIV 2 -B here
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.
//okay but for n=25
/// no=9 satisfy condition
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.
ohhh shit,, thanks man now got it, should not bound the loop
So did I.
I used the number 9 instead.
lol
C(hasBig,cntBig)⋅cntBig! What does this C means in question 1436C?
nCr Combination
Why he didn't use A(n,r)
Combination nCr=C(n,r)
It is combination.
Also, notice that $$$nCr \times r! = nPr$$$
It's for Combination Number
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
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
i did the exact same way :)
yes same i did but it show wrong why?
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 :)
Sorry but can you explain E's solution a little more clearer
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$$$.
What these queries look like? What do we want to request for $$$[l, r]$$$?
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)$$$".
Thank you
Got it by Offline. if you have another way Please Make sure to share it :P
Can you tell your approach for D and the theoram mentioned in editoriol standard in cp??
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
Weak pretests for C. Huge number of people getting WA on test 10.
What actually is test 10?
Should probably be something like 6 3 3. Actual answer should give 36, people who failed system tests, their answer is 120.
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.
On the first iteration it will return 2 as mid (because its 0 indexed)
h = 6 and l = 0 so mid = 3
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.
Yes I understand. The image in the problem was not accurate that confused to take h = a.size()
But in the problem statement h=a.size()
In actual it should have been a.size()-1 in the problem but as it was given a,size()..it did with that.
Yeah they explicitly mention it to be h instead of h — 1
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.
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!
Yes we shoudn't have break the loop if mid==pos. That is why i also got failed in test 10.
Even if you break the loop, the if statement below will take care of that.
For input 3 3 1, answer should be 2.
yes, the two is {1,3,2} {2,3,1} but how they get answer 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 false
apply binary search according to algo given in question
Why?
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.
Can you please tell what is actually test case 10 in C?
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.
if we don't break then the value for test cases 1 & 2 also don't match as what it is given as answers
yes agreed answers dont match then get zero there
When the pretests are so weak, the round should be unrated.
I failed systest on C.
nonsense
It's clearly mentioned that your solution may pass the pretest but doesn't mean that it will pass system testing for sure.
what's the criteria between weak pretest or not?
What is av and maxi(sum(av)/leaf(si)) in problem D? Can someone elaborate?
Can someone give a more clear explanation of Editorial of D.
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.
Whiplash99 can you tell how this solution is correct? It did not use the DFS order for traversal.
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.
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.
Try this test:
Your code gives $$$1$$$ as the output, while the answer is $$$2$$$.
thanks for the great explanation
great explanation
Thanks for your amazing explanation!
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??
"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.
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 ?
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.
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
Thanks for the amazing explanation !
Here's my attempt at
rambling about my thoughtsexplaining 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.
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?
I think it is another name for pigeonhole principle.
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;
Man this contest problem were used in a official contest .. Such a shame having such pretest for C
Anyone else failed test case 51 of C? What was wrong?
Why doesn't C consider the permutations of the numbers not part of hasBig and hasLess?
Yes the correct answer is :-
Where :-
Bignum = (n - x)
Lessnum = (x - 1)
And
cntBig
,cntLess
is same as explained in the tutorial.Just a small correction, it should be $$$(n - cntBig - cntLess -1)$$$ factorial
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!
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.
weak pretest !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Weak Pretests, Long Queues, Unexpected Errors and Rated :(. Make it Unrated :P
in B it says there are no prime numbers in the square.
1 is not prime.
1 is not prime :) and its given in problem that sum should be prime
People be mourning to the rip case of C and random guy be like : 1 iS PrImE ..
Man come on revise your maths lessons
How to solve C??
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!
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.
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.
I think even if you break the loop, the if statement below will take care of that.
The if statement below is outside of the while loop. So it will check a[3-1] element. Which is definitely not 3.
but when left=2 after 1 iteration a[left-1]=3 and it will break after 1st iteration.
Exactly dude... I'm stuck thinking about it as well!
"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)
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.
We will count that in the binary search. For better understanding you can see my code. https://codeforces.com/contest/1436/submission/9658029
Thank you, well explained.
Thankyou so much <3 I finally understand how to solve C
First time i failed system test in codeforces . Problem C [Test 10] :(
what is exactly 'system test'?
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
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
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
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 ->
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
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:
and relevant diagram:
where the
100
can only move to the two leaves below it, meaning the answer should be50
.Thanks, Got it.
Oh My Goodness... Thank you so much for such a fast editorial.
can some one tell me about Dirichlet principle ?? any link for the study resources ??
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.
I'm confused too. Can someone clarify please?
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
Yea the first middle would be one right ? Can someone help what makes this test to have answer zero ?
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.
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
Yes I got it now. Thanks btw
Thanks man now i got it take me two days frustation ;_;
Exactly ! I also don't understand why the answer should be zero.
Edit:- Leave it I found where I was wrong.
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.
How? I implemented their binary search function and it succeeds in finding 3. Idk what's wrong
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.
Thanks, I am dumb!
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.
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
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 :
Yeah algorithm was not exactly same but I wrote exactly same algo as per pseudocode.It passed.
deleted
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
I'm also confused answer should be 0 only
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.
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
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!!!.
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
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.
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
Weak pretests for C and E,I get failed system test in my other account.
rank 9 -> rank 500+ :(
Hope for strong pretests.
"in my other account" you dont deserve to have better pretests, as you are ruining the contest for actual div2 contestants.
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.
The contest was extended for 10 minutes. So don't see a big problem there.
why am getting wrong answer on 6th test case of DIV2 B here
Help needed
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.
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
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.
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$$$
Editorial of E is just too short. Please elaborate a little. Thanks .
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
The answer will be 0 for those cases.
For Binary Search Problem, For Input-3 3 1, why the answer is 0 and not 2 ??
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 ?
This comment made me feel good and sad at the same time :(:)
In problem D, I used binary search. What is wrong with this logic? Submission
I think there is Long Long integer overflow
No, I am sure that all values are less than 2e14.
Your binary search works in the range
[1, 1e15]
, which implies that the req array might take values to the extent1e15 * 2e5
. Indeed it will overflow.Thanks, i got it now.
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
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.
Alas I wasted a lot of time on the Binary Search Solution for D, missed the obvious solution.
Can you please explain your binary search solution in detail?
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
Binary search soln for D 96602832
Can you please explain idea behind your binary search solution , i am bad at understanding from code.
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
could you pls elaborate a bit about function f()... I'm not getting the if conditions
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).
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(0,3) — 1
(2,3) — 2
(3,3)
Result will be false
Can you explain it? What do you mean by "first middle". (0 + 3)/2 = 1 isn't it
Fixed it
there are 3 elements
btw got the logic, they used different version of binary search in which you have to make log(n) iterations always for the result
Can you please explain idea behind your binary search solution , i am bad at understanding from code.
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.
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.
You should check the comments first. This issue has been discussed already in a ton of comments above.
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.
In my opinion, no one should fail system tests because of overflow and an overflow case should always be included in pretests.
Here are 0 fcks for your opinion.
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.
.
pseudocode was given in python ????
Come on!
Does Pseudocode have any programming language??
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.
Just another regular person BSing because he dropped rating OK.
Please, never implement Binary Search as same as in problem C.
I was solving C with my own implementation of BS lol, while(l <= r) { ... } then realized its different, still failed for system test. ;___;
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.
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.Well, there is an array
cnt
which holds what you said. $$$cnt_x$$$ holds the frequency of numberx
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 ofcnt
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 definetmp[i] = bool(cnt[i])
and declare Fenwick over thetmp
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$$$ intmp
.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$$$.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?)
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.
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?
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
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?
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...
Why there is no bracket for while loop?
identation exists for something. That is pseudocode.
This makes no sense, it would return false if it didn't find the element in the first step.
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.
Can someone explain me how to solve task E with segment tree?
range mex query offline algorithm submission
D has "binary search" in tags, have someone solved it in this way?
96602832
Could you please explain your solution?
https://codeforces.com/blog/entry/84024?#comment-714446
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).
You can cycle $$$1,1$$$ instead of $$$50,51$$$ as $$$2$$$ is prime as well :P
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
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?
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)
Since there are $$$O(n)$$$ solutions (including the official one), I believe that this time limit is quite reasonable ...
Someone, please provide the code for D.
96844907
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).
why binary search is not working in problem D??
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
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.
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.
Can anyone tell, In C problem, how answer of 9 4 4 is 7200.
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
problem E how to get the mex using segment tree ??
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.
great thanks :)
Can someone please explain binary search solution for D?
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
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.
could you explain your approach please??
I have explained it above, if you any doubts, you can ask me.
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?
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.
Oh yes I never thought that way. Got it accepted. Thanks a lot man.
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}.
Just pointing out an issue in the problem, what's about all these downvotes:)
Problem E can be done with Persistent Segment Tree and you don't have to bother with ordering the queries :)
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";
}
}
It is because of double. You should never compare double variable with any double/int variable. This is due to precision errors.
Ohh ho...thanks I will take care of it. then how to compare decimal numbers?
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) .
ㅤ
Can anyone Explain D?
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?
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.
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.
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.
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.
+++ this
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 :)
very fast announcement claimed 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
Found the problem, the solution 96682324 has the correction.
For E, how do we process the occurrences in order using segment tree?
C(hasBig,cntBig)⋅cntBig! ,is that equal to P(hasBig,cntBig) ?
I think so.
Need help. In D, I got WA on test 77 and I don't really get what's wrong with my code.
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.
Only the highlighted positions need to be calculated. This can be done by
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
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
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?
Can anyone tell me how to solve Problem B, if we are allowed to fill only positive numbers?
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
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!
Anybody please help me with C problem!
can someone tell the answer of testcase 3 3 1 in problem C?? is its answer is 0 or 2??
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
I solved B with a cool sequence
see my code
to get this sequence, you need to have a primality test function and do the following
for each input $$$n$$$ just slice the $$$seq[:n]$$$ and cycle shift one unit to get the matrix
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 :)
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.
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.
Not getting why this case 3 3 1 results in 0. I thought it should result in 2
exactly my doubt