### desert97's blog

By desert97, history, 3 years ago, Preliminary, changes to come possibly.   Comments (167)
 » No solutions?
• »
»

# include <stdio.h>

int main() { int amount; int note100, note20, note10, note5,note1;

note100 = note20 = note10 = note5 = note1 = 0;

scanf("%d", &amount);

if(amount >= 100)
{
note100 = amount/100;
amount -= note100 * 100;
}

if(amount >= 20)
{
note20 = amount/20;
amount -= note20 * 20;
}
if(amount >= 10)
{
note10 = amount/10;
amount -= note10 * 10;
}
if(amount >= 5)
{
note5 = amount/5;
amount -= note5 * 5;
}

if(amount >= 1)
{
note1 = amount;
}

printf(" %d\n",note100+note20+note10+note5+note1);

return 0;

}

•  » » #include using namespace std; #define ll long long int int main() { ios::sync_with_stdio(0); cin.tie(0); #ifndef ONLINE_JUDGE // freopen("input1.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif ll n, sum=0 ; int v[]={100,20,10,5,1}; cin >> n; int i=0; while(n!=0){ sum+=n/v[i]; n%=v[i]; i++; } cout<
•  » » » can you guys write your code in spoiler tags please?
 » Explain to someone how the solution working for O (n ^ 2) has been tested in task B
 » I see some of the participants passed Div.1 C by random shuffling and greedy approach. Could anyone explain the rationale behind this solution?
•  » » My solution shouldn't have worked but it did. Basically i was taking vectors greedily but because i knew there were countertests, i did so starting from the last vector and going back to the first.
•  » » I think creating test cases to break a greedy algorithm is pretty tricky — each vector needs to be roughly orthogonal to the greedy sum of the previous ones, and as soon as one adds some randomisation it's basically impossible to break.
•  » » » To avoid the use of randomization, the authors may put some constraints like the found solution should be lexicographically smallest by defining -1 < 1 or vice versa.But at the same time, this would mean that the problem is looking for the unique solution which can be obtained only if the solution is similar to intended solution.
 » For Div1 F, what is the O(n) interpolation you had in mind? I used Lagrange interpolation in O(n^2), and while I can see how one could optimise that to O(n) by incrementally computing each term from the previous one, it would add a lot of complexity.
•  » » 3 years ago, # ^ | ← Rev. 4 →   Though I don't have the formula on hand, if you write out what Lagrange interpolation gives and then substitute x = D into the formula, it becomes a sum of the dp values times some binomial coefficients. We can do this in O(n) with some preprocessing.Here is the code: http://codeforces.com/contest/995/submission/39639811You should post it here if you figure out what it is :P
•  » » » That's more-or-less what I had in mind, although that code is still O(n^2). It would be pretty easy to make O(n) though by first computing and then using that to get for each j.
 » In problem C-tesla, in the first sample, why am I getting WA cause I put car No 5 in (4, 1) as temp place? I will put it in right place after that.
•  » » The problem statement says that a car can only be moved into row 1 or 4 if that is its designated parking spot.
•  » » You can't do that. "Furthermore, Allen can only move one of his cars into a space on the first or fourth rows if it is the car's designated parking space."
 » Rating drop for sure now :/ this was a bad day.
•  » » Just now, I wrote something very similar to your solution with E except I used random_shuffle and it passed, you should give it a go.
•  » » » How did your solution work? We can't choose vectors randomly right?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   We choose them greedilylet's say the vector pointing to current position is pwe calculatep — a[i] and p + a[i]and choose which one has the smallest distance from (0,0)Now this is definitely incorrect greedy and there is probably a counter-case, but it is sort of hard to break.But now, seeing that the process is O(n), I thought if I scrambled it it is unlikely the solution would fail the constraints over a thousand times so I continued to run this process until it passed.Also note I used "sqnorm" which is just the magnitude squared, becauseI wanted to avoid floating-points and sqrt() function, but I don't think it's necessary.UPD: Good job on solving :D
•  » » » » » Oh , okay . Thank you!
 » Problem E says "We can show that the answer always exists."While statistically I'd be very surprised if it didn't, does anyone have an actual proof?
•  » » I wanted to ask the same question. Even though I pretty quickly thought of "random" solution which I was sure will pass, I though that authors should have an actual proof to state something like this which would probably be a constructive provable solution.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Well, this graph is called the "Margulis expander". An expander graph is a graph that kind of "expands" optimally in a BFS. There are explicit lower bounds on the expansion using deep number theory.In other words, yeah I can "prove" the solution works, but not in a way that works in contest. To be honest, I just was feeling experimental with this problem.
•  » » » » LOL. I had exam in university like two weeks ago and large part of that course was about expanders. We had 'Margulis expander' in the course but I found the proof so big and ugly so I didn't even tried to learn it and even forget the what it is about :) Could save me some time on trying to come up with actual solution.
•  » » do you have proof for GAME , please tell me how to prove and please share photo of your proof
 » for B.would any one explain how the following two codes differ in logic... one is accepted while other is giving TLE.. http://codeforces.com/contest/996/submission/39630623 http://codeforces.com/contest/996/submission/39631431
•  » » try using int instead of long long.
•  » » » why??
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Int operation are faster. And I don't know why you are all downvoting preda2or, he's probably right.
•  » » 3 years ago, # ^ | ← Rev. 2 →   This brute force approach is almost on the limit, so by making it long long you're adding extra computations that will give you TLE.
•  » » » Is there any better approach besides brute force?The problem has a tag of binary search but I can not figure out how will we choose the mid-value after testing with 1st value of the round. I was able to figure out the maximum value and the minimum is obviously zero.
•  » » You have declared size of array as n ! And you are taking input from 1 to n ? Why kingosak
•  » » » That's not my code
 » For Div2-E, I don't know what is the difference but in the solution I submitted during contest, I processed each vector in the order given and kept changing the position vector through my algorithm which got WA on TC 79. However,after contest I did a slight change and stored all the vectors and then iterated in reverse manner, from n-1 to 0 using the same algo and I got an AC. Can anyone explain to me what is the difference?
•  » » It is hard to make good data. Probably the latter solution just gets lucky.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Can you please share the model solution ? Most solutions I’m finding use randomisation.
•  » » Even I got WA on TC 79. Did you use the fact that whenever we add a vector we just try to be greedy and hence take that sign which reduces the distances and nothing more? Is there any problem with this approach?
•  » » » I did the same and I dont know what is wrong with the approach.
•  » » Sir, I want to know why that claim is right. If I have two vector, one of them is (5,6) and its length is max, the other is (5,5). But their sum is better than the length of (5,6). So, why that chaim is right?
•  » » » Sorry, I can understand it now! Thanks!
•  » » 16 months ago, # ^ | ← Rev. 2 →   Applying your algo on a=ri, b=rj, and c=r/√2(i-j), in a,b,c order. a and b will combine to give x=a+b=r√2(i+j), And x will combine with c to give y , where |y|=r√3. But if x=-a+b, then you can see -a+b+c is less than r√2. Which is output of your algo in reverse order
 » 3 years ago, # | ← Rev. 3 →   Problem E. Here is BFS, that finds the answer of length  ≤ shortest_path_length + 3. http://codeforces.com/contest/995/submission/39632072(It's simple bidirectional bfs with used array for buckets of size 4 on bitset),
 » desert97, the complexity of making an entire circle is actually 2*n, not k.
•  » » There are only k cars in the cycle. So advancing k cars by one is O(k).
•  » » » But at each move, you move into neighbouring empty space which means you move one by one. It's not clearly described though.
•  » » » » The time complexity of it is O(2n) (unless you do it in a clever way), but the number of moves is O(k).
 » 3 years ago, # | ← Rev. 2 →   Can anybody give me the source code of Div.2 B no problem with the same approach which has been provided in the editorial?
•  » »
 » Does anyone have solution for div1 C as described in editorial (the binary tree and vectors as leaves)
 » nice Python solution for DIV2 problem B n, a, m, res = int(input()), [*(map(int,input().split()))], 10e9,-1 k = [ math.ceil((ai-i)/n) for i,ai in enumerate(a) ] print(k.index(min(k))+1) you can find more like this here: https://codeforces.com/blog/entry/60059
 » If anyone solved Problem C using dynamic approach please share it. Thank You
 »
 » Finding a linear time solution to “suit and tie” is equivalent to counting inversions in and array. As far as I know there is no known exact algorithm for calculating inversions in O(n).
•  » » Okay, you're right. So is probably the best we can do.
•  » » How do you reduce counting inversions to suit and tie?
•  » » » 3 years ago, # ^ | ← Rev. 3 →   Look at your solution.i got idea of counting inversion from your solution :Pbut what is idea behind f[a[i]]
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   This is not what I asked. What I am asking is: Given a problem of counting invesions, can we reduce it to an instance of the problem "suit and tie", which is necessary for equivalence.
•  » » » » » Consider a permutation of 1 through n, and place 1 2 3 ... n to the left of this array. Then the answer for suit and tie is the same as the number of inversions of the permutation plus n(n-1)/2.
•  » » » » » » Then the answer for suit and tie is the same as the number of inversions of the permutation plus n(n-1)/2.I'm sorry but this fact is not obvious to me. Can you please elaborate ?
•  » » » » » » » As in the editorial, we only need to consider for each pair, the relative ordering and add up the number of swaps needde. If a < b, the possible orderings in our sequence is a ... b ... b ... a or a ... b ... a ... b.In case a b b a there is one inversion in original array and two swaps needed.In case a b a b there is no inversion in original array and one swap needed.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   If you know where everything should go, you can relabel the people to numbers 1..2N. Now, you are asking the question “given a permuation of 2N values, how many adjacent swaps are needed to sort it”.The general idea is that your array will become sorted when there are 0 inversions left, and that each adjacent pair swap will eliminate (or add, but we don’t want that) 1 inversion. So therefore the number of adjacent swaps needed is equal to the number of inversions.https://stackoverflow.com/questions/20990127/sorting-a-sequence-by-swapping-adjacent-elements-using-minimum-swapsEdit: ksun has commented how to turn inversion counting back into the suit and tie problem.
•  » » » » So is the problem equivalent to - Relabel the integers from 1 to 2n Count the number of inversions I believe the number of inversions of a permutation can be found in O(n) time. So, is this an O(n) solution ?
•  » » » » »
•  » » » » » » Wait ... What about when you decompose into cycles ? int no_of_swaps = 0; vector visited(n + 1, false); for(int i = 1; i <= n; i++) { if(!visited[i]) { int cycle_size = 0; for(int current = i; !visited[current]; current = permutation[current]) { visited[current] = true; cycle_size++; } no_of_swaps += cycle_size - 1; } } Am I wrong ?
•  » » » » » » » 4 3 2 1The cycles are 1 → 4 → 1, 3 → 2 → 3. Your algorithm will return 2, while the answer is 6.
•  » » » » » » » » I understood the mistake. Cycle decomposition counts the parity of the permutation in O(n) time, not the exact number of inversions !Thanks !
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   I have a doubt about how to do the relabelling. Can you help me understand how exactly to relabel the integers ? I was thinking every pair but that’s not optimal. Do you need to know the optimal arrangement apriori before reducing it to inversion counting ?
•  » » » » » You can do the relabelling in increasing order. Let the original array be 3 1 2 3 1 2. Relabel 3 as 1 , 1 as 2 and 2 as 3. The transformed array is 1 2 3 1 2 3. Then find the number of inversions in the transformed array.Code
•  » » » » » 3 years ago, # ^ | ← Rev. 4 →   I did the relabeling in the following manner: a: original array. b: relabeled array. num=1000; outer: for(i=0;i=0;j--) { if(a[i]==a[j]) { b[i]=b[j]; continue outer; } } b[i]=num++; } 
 » Great contest ! It met my expectations and the editorial is very well written compared to most CodeForces tutorials. In Div 2 E, I didn’t understand why two vectors in the same 60 degree segment have sum less than r. Can someone please explain ?
•  » » Geometry: If AB < 1, AC < 1 in a triangle, and , then BC < 1. This is because the angle opposite an angle less than 60 cannot be the longest side of the triangle.
•  » » » Wow ! Great proof. Should have been included in the editorial !
 » 3 years ago, # | ← Rev. 3 →   Can anyone please tell me whats wrong with this code for problem 996B.39614833 . Somebody plz help me
•  » » Wrong logic.
•  » » » I am sorry! that code is for problem 996B. Please tell me why its not working for following testcase :-2 1000000000 1000000000
•  » » » Generic comment.
•  » » You forgot that he can go many laps around the queues, so after your for loop, if it didn't find any empty queue you can't just output the last queue you must instead let him walk around the queues again and again until he finds an empty queue.
 » someone plz explain how greedy approach will work for div2 DIf the leftmost person is in pair a, swap the other person in pair a left, to the second position. Now the first two people are both in pair a, and we repeat the process on the remaining n−1 pairs of people recursively.i am not getting this line :|
•  » » 3 years ago, # ^ | ← Rev. 2 →   Notice that by switching the other person to the left, we will switch everyone between them to the right. We don't want to switch the leftmost pair because there's a chance that some person inbetween the pair will be farther than beforeFor example this tc: 1 2 3 2 4 1 3 4 -> 1 2 3 2 1 4 3 4 -> 1 2 3 1 2 4 3 4 -> 1 2 1 3 2 4 3 4 -> 1 1 2 3 2 4 3 4 -> 1 1 2 2 3 4 3 4 ....If we switch the right 1, all other pair won't be farther than before (2 pair distance will be the same, 3 and 4 pair will be closer). But by switching the left 1, the 3 pair and the 4 pair will be farther.
•  » » » okay got it!!can u explain me logic behind this solutionhttp://codeforces.com/contest/995/submission/39620454
•  » » » » For each number(i), we will eventually need a swap with j (j < i) if a[i] leftmost number < a[j] leftmost number1 2 3 2 4 1 3 4 -> 6th number and 7th number will eventually swap with 5th number, but 5th number won't need to swap with number before it
•  » » » » » Thankss :D
 » For problem A, why does this matter? "The solutions works because each number in the sequence 1, 5, 10, 20, 100 is a divisor of the number after it."
•  » » Basically, this is a special version of the coin change problem.In general, this problem cannot be solved by Greedy, and instead you should use Dynamic programming, however if the coin system has certain properties, it can be proved that greedy works. The proof goes as follows for each coin you get the maximum amount you can do, and argue that any larger, it's better to use coin i + 1.
•  » » Lets say you have different coins. For instance coins with the values 1, 3, 4. Try to form the value 6 with them. The optimal solution is 3 + 3, while the greedy one gives the worse result 4 + 1 + 1.
•  » » » I think he asked for a proof of why does greedy algorithm work for that particular denomination and not for an example of how greedy fails.
•  » » » » Yeah that's exactly what I want.
•  » » » » » Here's a mathematical proof for it:Let denote with (a, b, c, d, e) a solution (you take a coins of value 1, b coins of value 5, ...) If you apply the greedy algorithm, then you obviously get a solution with . Also you can convert each such tuple back into its value a·1 + b·5 + c·10 + d·20 + e·100, a non-negative number.Obviously these two operations form inversions. E.g. if you apply the greedy algorithm on the number x = a·1 + b·5 + c·10 + d·20 + e·100, you will get e coins with value 100, because a·1 + b·5 + c·10 + d·20 ≤ 4·1 + 1·5 + 1·10 + 4·20 = 99. In the same way you get d coins with value 20, since a·1 + b·5 + c·10 ≤ 4·1 + 1·5 + 1·10 = 19. And so on.So the greedy approach is a bijective function between [0, ∞) and [0, 5) × [0, 2) × [0, 2) × [0, 5) × [0, ∞).Now, assume you have an optimal solution (a, b, c, d, e) for some x, that is not identical to the greedy solution. Because the greedy approach is a bijection, the solution cannot be in [0, 5) × [0, 2) × [0, 2) × [0, 5) × [0, ∞). Therefore either a ≥ 5, b ≥ 2, c ≥ 2 or d ≥ 5. In either case we can replace some coins and get an even better solution. Therefore we have a contradiction, which means that the greedy solution is always optimal.
•  » » » » » » 3 years ago, # ^ | ← Rev. 3 →   Very nice proof. Thanks. For denominations where one of them is not a divisor of the next, we cannot have such bounds for a,b,c,d,e, so greedy solution may or may not work for such cases right ?
•  » » » » » » » Yes, you can't find bounds that will form a bijection.
•  » » » » » » » You can still use greedy exchange though.This videa has nice proof starting at 9:30 and only takes about 10 minutes.
 » I think in editorial for 996 B the condition k+tn>=ak is not correct because on first step nothing is decreased so it should be k+tn>ak.
•  » » We start indexation since 0.
 » 3 years ago, # | ← Rev. 2 →   " (Maybe it can be even done in O(n), anyone?)."This is regarding div-2 D. Can anyone please link me an O(n) solution? desert97
•  » » It seems it is not possible http://codeforces.com/blog/entry/60217?#comment-440367 But maybe in O(n sqrt(logn)) http://codeforces.com/blog/entry/60217?#comment-440466
•  » » » Thanks :)
 » Isn't it too easy for coding when you have the idea of the problems? Div1 DEF can all be solved in 50-60 lines(maybe less) . I think a good contest should also focus on the implement difficulty.
•  » » I think div1 A was for implement difficulty.
•  » » E, F can be solved in 50-60 lines?
 » How did this bruteforce approach for Div-2 B get accepted ? Code : http://codeforces.com/contest/996/submission/39628778
•  » » check that comment http://codeforces.com/blog/entry/4825?#comment-98334
 » div1F , a much simpler solution is to just calculate dpi = number of ways to assign i distinct numbers to the tree nodes , then answer is just .
•  » » Could you please elaborate !!!
•  » » 3 years ago, # ^ | ← Rev. 2 →   rajat1603 can you explain how dp[i] is calculated? I am also confused on how to calculate D choose i for large D values efficiently.EDIT: I'm good with the D choose i part, since i is at most 3000.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   dp1i =  the number of ways of assigning numbers  ≤ i to tree [just the solution to the original problem] , this can be calculated as . now to calculate dpi =  number of ways of assigning exact i distinct numbers to tree , we can use the formula .
•  » » » » Please tell me what am I doing wrong, accroding to the way you suggested!! lets work for the sample testcase: 3 3 1 2i.e. tree has 3 nodes (1,2 and 3 such that, 3 is child of 2 and 2 is child of 1).dp1=1 (number of ways to assign numbers<=1 to tree of 3 nodes). dp1=2*2*2=8 (number of ways to assign numbers<=2 to tree of 3 nodes). dp1=3*3*3=27 (number of ways to assign numbers<=3 to tree of 3 nodes).dp=dp1=1; dp=dp1-dp*(2c1)=8-2*1=6 (whre 2c1 means binomial coeficent of 2,1) dp=dp1-(dp*(3c2)+dp*(3c1))=27-(1*3+6*3)=6now answer=3*dp+3*dp+1*dp (since D is 3) =3*1+3*6+6=27 But the answer stated in sample case is 10.Any help? I did the same as stated in your solution.
•  » » I don't get how this is the solution to original problem.
 » Can anyone please explain Div-2E(Div-1C) — Leaving the Bar? I have read the editorial but unable to understand anything. I can't visualize the solution described in the editorial and can't relate the editorial with the problem statement. Thanks in advance.
•  » » I have tried my best here. Let me know if it helps.
•  » » » Thank you for your proofs.
•  » » » great explanation!!!
 » Question regarding 995C — Leaving the Bar I wrote 2 functions to calculate magnitude of the total vectorThis one is giving wrong answer at test case 91long long int cal(long long int x, long long int y) { long long int ans =sqrt (x * x + y * y); return ans; }THis is giving correct answerlong long int cal(long long int x, long long int y) { if (x == 0) { return abs(y); } else if (y == 0) return abs(x); else { long long ans = sqrt(x * x + y * y); return ans; } }The question is aren't both function same?? Why is one giving correct answer and other one giving error.
 » 3 years ago, # | ← Rev. 2 →   basel-99 Gankutsuou The solutions works because each number in the sequence 1,5,10,20,100 is a divisor of the number after it.
 » 3 years ago, # | ← Rev. 2 →   Here are my solutions to the problems of this contest. I found Div2 E/ Div 1 C a very different question. So, I tried my best to explain it here with the help of the editorial here. Here's my editorial to Div 2 D/ Div 1 D
 » someone please explain editorial solution of Leaving the Bar 995C.
•  » » 3 years ago, # ^ | ← Rev. 2 →   let me tell you how i did it1.Store 1 in a array of size n in all index.( call this array arr). store the sum of all x and y co-ordinates of the given vectors and calculated the magnitude p. if magnitude is less than 1500000 display arr(all 1). 4.If the magnitude is greater than 1500000, use a loop and change the sign of input vector's x and y coordinate and calculate the new total sum (new_sum.x=old_sum.x-2*(x index of ith vector)) . Calculate new magnitude of the total . If the new magnitude is greater than old magnitude revert back the changes (since we want to decrease the magnitude , if any vector increase value their is no need to negate it). 7.If the new magnitude is less than old magnitude but greater than 1500000. Change the corresponding value in arr as -1. If magnitude less than 1500000. Display arr. This worked for me Sorry for bad english
•  » » » nice solution bro.
 » For the Div. 1 E problem, what would be a rough value of the probability for Solution 1? I don't find the probability of an "intersection" very high. Could you please show how to do the calculations? Thanks.
 » 3 years ago, # | ← Rev. 2 →   I did weird implementation of Suit and Tie of O(n sqr.) complexity:http://codeforces.com/contest/996/submission/39659575Happy Coding
 » Can someone direct me to the idea of Lagrange Interpolation? I understand the general idea of it, but how do you put it to work in div1F?
•  » » Given n+1 points, Lagrange interpolation lets you find the polynomial of degree bound n which passes through all the given points. Basically we define a polynomial f(x), which gives us the answer for d=x. Now, we calculate the first n+1 integer values of this polynomial via dynamic programming (f(0) through f(n)), and then use Lagrange interpolation to find the polynomial f(x) (which has degree bound n as per lemma in editorial), and then evaluate the polynomial, at f(d), to get the answer.
•  » » » mmmm and since Lagrange interpolation is the only unique solution at the lowest degree this fit. First of all thanks, I got the idea now because of that :) Maybe you also know why the lemma is correct? it has a maximum of x(x-1)(x-2)...(x-n) I guess because it will always use "d choose n" at max. Although this is true, how can you know this beforehand...?Never the less, this does make the code writing very simple...
•  » » » » Let P(x, a) denote the no of possible labellings for the subtree rooted at node n, and the label of node a equals to x. Now You can show that prefix sum of any polynomial on integers will have degree 1 higher than the polynomial itself (relate on the lines of sum of kth powers of first n natural numbers).Let ss[i] denote the subtree size of node iTo make induction work, we assume for now that the degree of polynomial for every child i of node a was ss[i] - 1. Hence, The base case for this induction will be the leaf nodes, where P(x, a) = 1 and thus the assumption is valid. Hence, our induction holds.Now, the final answer will be which'll have degree ss = n
•  » » » 3 years ago, # ^ | ← Rev. 3 →   But why the complexity of the interpolation is O(n) mentioned in the tutorial? I think the normal Lagrange interpolation is O(n2). I don't really get the point.
 » desert97 if div2C tesla had asked about the minimum number of moves to park all the cars, I guess rotating the circle wouldn't have been a good strategy. Any idea on how could we find it?
•  » » I doubt it's possible in polynomial time. Might even be possible to show it's NP-hard.
 » Can someone please disscuss the Binary indexed tree approach for Suit and Tie Ques
•  » » You can just simulate the process from the editorial. Let's say that the sequence looks like this: abc....ab...c.... First we want to bring the second a next to the first one. This takes |number of elements between a and a| steps. Then you want to bring the second b next to the first one. This takes |number of elements between b and b without the a-s| steps, because the second a is already to the left of the first b (if we simulate the process). And so on.To solve this with BIT. Initialize the bit with an array of 1s. For each letter you to range_sum steps, and afterwards you delete the two elements by setting them to 0.I'm sure that there are multiple approaches.
 » For problem Div 2E / 1C editorial : Any two points in this sector will have distance at most r. How to prove this ?
•  » » See this, or you can prove it with cosine theorem.
 » If div2 — 995C leaving the bar — if I greedily take every vector's sign so that it reduces the distance from the origin than this approach shows WA on TC79. What is wrong with this approach?My submission — #39620913
•  » » 3 years ago, # ^ | ← Rev. 2 →   Try this : 3 1000000 0 0 1000000 707105 707105 Draw the figure on paper and you'll know the greedy approach is wrong. You may want to see the discuss above.
 » In Div2.F / Div1.D , how can we get (v_i,0+v_i,1)/2=E_f by induction ? I tried some ways including induction, but failed. Can someone please explain it ?
 » According to the solution of problem B, shouldn´t the result for test case n = 3 and {5, 5, 5} be 2? Since for the first gate, you can write 1 + 3*2 = 7 > 5, for the second one 2 + 3*1 = 5, and for the third one 3 + 3*1 = 6 > 5. Can someone explain to me why is the answer 3?
•  » » I'm not sure why it says >= in the editorial when I think it should just be >. In your example, there are 5 people in each of the queues so the queues are only available starting at minute 6. So for each i you find the minimum t such that k + t*n > a[k] instead of >= a[k].
 » For div2.E/div1.C, I implemented in a tricky way like this.I wonder if this can be proved to be correct and if not, how to hack it.
 » Can someone please elaborate the euclidean algorithm solution to E? Thanks!
•  » » 3 years ago, # ^ | ← Rev. 2 →   First, since all operations are reversible, we can just get u and v to some common number (which is 1 in this case).Let (a,b) represent the number a*b^(-1) modulo p (for v != 0). Then, we can see the following operations: Subtract one operation corresponds to moving from (a,b) -> (a-b,b) Inverse operation corresponds to moving (a,b) -> (b,a) This is similar to the euclidean algorithm (we do the first operation if a > b, otherwise we do operation 2, until we get to (gcd(a,b), gcd(a,b))).Of course, this might not be very fast for (u,1), but we can instead do it with (u*x mod p, x) for some x!=0, which is an equivalent state. The claim without proof is that for random x, it is likely this will take < 100 steps (not sure why this is true either).
•  » » » Thanks for the clear explanation!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   I tried the gcd approach, however picking a single random x does not seem to work, but it does work for small enough number of attempts with different values of x to get an AC verdict. The submission is 39734619. Am I missing something here?
 » How the problem 996A Hit The Lottery can be solved using dp ? Please help if anyone knows.
•  » » Not really.. Considering the fact that n <**=** 10^9;
 » HiI was trying Problem C Tesla.I have written this code which gives Time Limit Exceeded on test case 6.http://codeforces.com/contest/996/submission/39723591I am rotating the cars clockwise.Can anyone tell me why is my program taking so much time? I think it is O(n^2). How do I reduce running time?
 » can someone please explain the initial dp used in F?
•  » » let f[i][j] = the answer of the i-th subtree and the max salary won't exceed j . Then f[i][j] = f[i][j-1] + π(f[son[i]][j]) where π means the product of all things involved in the brace .
 » 3 years ago, # | ← Rev. 5 →   In div2-E, div1-C 39809949 39809939 I don't know why first code is wrong but second is right. Difference is just for-loop 0 to n -> for-loop n-1 to -1. why? why second is right?? How about testcase like below 3 600000 -600000 0 999999 1000000 0 When input this testcase, first code output 1 1 -1, so p = (-40000, 399999) and second code output -1 1 1, so p = (40000, 1599999).
•  » » It is hard to design data to break all solutions in this problem. The second one just got lucky.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Oh, i know that make all-round testcase is hard. Anyway, I'm glad it's a tastcase-problem ... I thought there was something else I did not know about. Thx!
 » Tried solving by sorting the couple by there average position and then arrange them from left to right based on that. Why does it give WA? http://codeforces.com/contest/996/submission/40732471
 » I had seen some people's solution of Problem C. And some of the code are wrong when I input test case below: 3 600000 -600000 0 999999 1000000 0
 » https://codeforces.com/contest/996/submission/75694939here's my solution in 30 lines of code, way simpler and better than the ones i've seen here.
»

# include <bits/stdc++.h>

using namespace std;

int main() {

int n;
int bills = 0;

scanf("%d", &n);

while(n > 0) {

if(n >= 100)
n -= 100;
else if(n < 100 && n >= 20)
n -= 20;
else if(n < 20 && n >= 10)
n -= 10;
else if(n < 10 && n >= 5)
n -= 5;
else
n -= 1;

bills++;
}

printf("%d", bills);

} ~~~~~ Your code here... ~~~~~

 » Can anyone explain why my this code is giving TLE on 2nd test case https://codeforces.com/contest/996/submission/76763546
 » In Leaving the Bar problem, how can we be sure that it is always possible to construct a circle through any 3 points of some radius r with origin as the center?
 » 19 months ago, # | ← Rev. 3 →   #include #include #include using namespace std; /** * Problem : https://codeforces.com/problemset/problem/996/A * Checked : OK **/ int main() { int n; int bills = {100, 20, 10, 5, 1}; cin >> n; int response = 0; for (int i = 0; i < 5; i++) { while (n>=bills[i]) { response = response + n/bills[i]; n = n%bills[i]; } } cout << response; } 
 » desert97 Please consider adding implementation or link to submitted solution. Without implementation it is often hard to understand the editorial. Thanks in advance.
 » can anyone help me in the first part. I tried to solve the problem using dynamic programming,the solution worked for the small values of the given amount,but as the value increased to the 9th power of 10,it shows a "bad_array_new_length" error, ig its because of the large array size.Can anyone help me fix this error.
•  » » yes because of int overflow => n=100000000 becomes negative on n+1 and for negative numbers we cant allocate dp array .In this question due to type of currency , greedy works , no need for dp
 » Can anyone explain how to do 996A- Hit the lottery using do ?
 » 15 months ago, # | ← Rev. 7 →   //Standard Coin Change Problem but here greedy works //Because every bigger coin is divisible by smaller coins // So we are left with divide by greatest coin to minimize at each point // and we have coin 1 so no worries as every number is divisible by 1 if // we get 'n' as a prime no. int main() { long long int n,i,size=5,ans=0; cin>>n; long long int coins={1,5,10,20,100}; while(n>0) { for(i=4 ;i>=0 && n>0;i--) { int num=coins[i]; if(num<=n) { int q=n/num; int r=n%num; ans+=q; n=r; } } } cout<
 » n = int(input()) # amount coins = [100, 20, 10, 5, 1] num_of_coins = 0 for coin in coins: num_of_notes += n//coin n %= coin print(num_of_coins) `
 » For problem Div 2A , if the denominations of bills were {1,3,4} , the given strategy fails for n=6. for n=6 , minimum number of bills = 2 { 3+3 }, while the given strategy gives 3 {4+1+1}. can anyone please explain this ??
 » Of Div.1 C, what is the probability to pass a worst case performing $k$ times random_shuffle and greedy algorithm?
 » 996A — Hit the LotteryHello,I am trying to solve this problem in linear time(input value n) but still see TLE. As this problem is tagged under dynamic programming, can you please share the recurrence/DP approach that is accepted.Thanks in advance