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
The sum of last columm ain't prime
sorry corrected now.
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?
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.
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
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 :)
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
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
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
Why?
Can you please tell what is actually test case 10 in C?
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
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.
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
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.
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.
Thank you, well explained.
Thankyou so much <3 I finally understand how to solve C
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
.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 ?
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
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
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
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 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.
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 .
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 ?
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.net/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??
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?
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.net/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
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 ...
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.net/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.
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.
Can anyone tell me how to solve Problem B, if we are allowed to fill only positive numbers?
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!
can someone tell the answer of testcase 3 3 1 in problem C?? is its answer is 0 or 2??
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
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
Notice that the index starts from zero. Following the code on the main text, we get 1. left=0, right=3, middle=1 -> a[1]<=3. 2. left=2, right=3, middle=2 -> a[2]>3(Impossible).
In C, why haven't they considered the permutation of the remaining numbers (those remaining after we find the given position after applying the given binary search)
Can someone please provide some similar problems like problem D ?? Thanks in advance.
I have got a verdict pretest passed on Problem B during contest time which has not changed till now, i.e., it has neither got a verdict W/A or AC rather the submission is still showing pretest passed. After the contest, I submitted the same solution again and get AC though the earlier is still showing pretest passed. What can be reason behind?
I have a code for problem E but its time limit exceeded on test 7. Is the question set in a way if we do not use a segment tree our time limit would exceed?
hey can anyone help me figure out what's wrong in my d's solution it's giving wrong ans on test case 87 96635681
In F how do you precalculate the multiplication of (sum of set with gcd i) into the answer?
I saw users such as neal using some mobius stuff but couldn't understand it. Can someone help me?
You can check out the definition of the mobius function on wikipedia. What it allows you to do, is apply the principle of inclusion-exclusion on the prime factors of natural numbers. If you aren't familiar with the principle of inclusion-exclusion you can check it out on wikipedia or cp-algorithms.com
Here we are able to separate out the target value over only the subsets whose gcd is 1 by applying the principle of inclusion-exclusion and eliminating the contribution from subsets whose gcd is greater than 1. We can do this by directly adding the contribution from all those subsets whose gcd have an even number of prime factors, and directly subtracting the contribution from all those subsets whose gcd have an odd number of prime factors. Note that we ignore the contribution from those subsets whose gcds are not square free. Where does the mobius function come in? It basically makes the choice for us (whether we need to add, subtract or ignore the contributions from the subsets having a certain gcd).
I've implemented the solution in the editorial here.
Hope this helps :)
nvm I got everything LOL
nvm i got this part.
A bit late, but here is the video editorial for E
Please, ¿can anyone explain more clear answer to problem C?, thank you very much.
In binary search we check only some special numbers, and you know exactly which positions are being checked during the algorithm, also we have two pointers left and right and you now each time you want left to become mid or right to become mid. So now all you need is it choose which of those bigger numbers are going to be set in the positions that we declared for big numbers, and we will also do this for smaller ones. after that we have some positions that don't have to be a certain number so you can put either bigger number or smaller one. here's my submission for this problem.
Why we not using binary search in solving D- Bandit in City? Consider x is answer and allow x citizen at leaf node , if no of citizen in all non leaf node is 0 then return 1 or return 0.
For those who are interested in problem B analysis here's our short video with some logic that could have lead to a common solution.
I am stuck on problem C, I think there is some mistake in my code regarding overflow. I tried but couldn't find the bug, can someone please look at my code and tell me the bug — https://codeforces.net/contest/1436/submission/96759365
It is giving WA on 52nd test case.
Hi! If I get your code right, then I guess you are misunderstanding how to calculate nCr. You can't just divide ans if you are taking modulo. Here's article for you.
tl;dr; you need to inverse the divisor
https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
In problem D I use dfs to calculate the answer from leaves to root. But it's wrong answer on test 7. Can someone give me a smaller example to debug?96761287
I also get error in this instance. The difference between my answer and the correct solution was only 6 units. Could you see my code? 96808517 Thanks.
I'm not sure but I think your variable tt should receive a ceil (a / step) in the following part.
if(point[now].a>=point[now].step){ LL tt=point[now].a/point[now].step; point[now].a-=tt*point[now].step; point[now].baseline+=tt; point[now].gap=0; }
It doesn't work. I have no idea. Maybe your variable slack (and my gap) will go wrong? Now I suspect that dfs is not suitable for this problem, because there are too many details to consider.
Hi, I have solved the problem with dfs. My code was wrong because I didn't test (k%s.t) before.
The following instance you can use to test your code. Your code answered 96 and correct solution is 92. I have tested with my code that was accepted.
8 1 1 2 2 3 3 3 68 5 44 83 46 92 32 51
Thank you so much.
same problem for me on same tc can u help me with my code? 96990704
F can be solved by using stirling。
In this way,now a set's contribution is S*(S-1),then contributions can be S^K。
Hi, Solution to problem 4 talks about Dirichlet principle, can anyone please explain what it is. I tried googling it but only found complex mathematical formulas.
You really don't have to know it completely just for solving this problem ... we are using this just to prove that we have minimum when we try to divide them into equal parts or not more than 1 difference(also no matter how you'll change some of minimums into maximum) because you are going to minimize the maximum. but if you're so curious about "Dirichlet principle" check out this
can someone point out my mistake in D the tc i am getting wrong is too big i cant figure it out
solution : 96990704
Thanks!!
In problem A:
anyone can help me out on question E(1436E — Complicated Computations)???
Here is an alternative solution to D, it might be somewhere in the comments but damn.... it's a very very long discussion.
So, if we have to distribute a value x among an array which is sorted such that all the values increase uniformly. For example, if we add 5 to [2,3,4,4,4,5,7] it would become [4,4,4,5,5,5,7]. The conversion is pretty easy to imagine.You can use a map for this, keeping a check of frequencies and then performing a sweep and converting the array.
Now, every value inside the tree which is not a leaf node has to sent down into the leaves.We have to do this and also keep the maximal element in the leaves as minimum. So every non zero element that we get in the tree is like a query to the problem described above. Every node will have a set of leaves in it's domain and it's value is to be divided into those leaves. If we keep a map for each node, we will be able to do this with a simple traversal. For every node's left and right subtree, you just add the smaller map into the larger one before resuming the process. Since we are performing a sweep while trying to find the minimal maximum after each "query", we won't be needing more than O(N+Q) which translates to O(Nlog(N)).
I hope my solution was understandable, if not , please do comment and let me know.
103544534 for Problem D binary search seems to save some trouble considering whether a number divides.
has anyone used small-to-large in D?
I did try to use small to large, but getting TLE on test case 80
Thanks bro! Your code helped me optimize my code and get an AC