#include <bits/stdc++.h>
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<<sum;
return 0;
}

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.

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://mirror.codeforces.com/contest/995/submission/39639811

You should post it here if you figure out what it is :P

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."

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.

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.

try using int instead of long long.

It is hard to make good data. Probably the latter solution just gets lucky.

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?

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?

There are only k cars in the cycle. So advancing k cars by one is O(k).

http://mirror.codeforces.com/contest/996/submission/39618290

Okay, you're right. So is probably the best we can do.

How do you reduce counting inversions to suit and tie?

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.

Wrong logic.

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.

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 before

For 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.

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.

We start indexation since 0.

It seems it is not possible http://mirror.codeforces.com/blog/entry/60217?#comment-440367 But maybe in O(n sqrt(logn)) http://mirror.codeforces.com/blog/entry/60217?#comment-440466

I think div1 A was for implement difficulty.

E, F can be solved in 50-60 lines?

I’m very surprised ! Explain your approach please.

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.

I don't get how this is the solution to original problem.

I have tried my best here. Let me know if it helps.

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.

I doubt it's possible in polynomial time. Might even be possible to show it's NP-hard.

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.

See this, or you can prove it with cosine theorem.

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.

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].

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).

Not really.. Considering the fact that n <**=** 10^9;

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 .

It is hard to design data to break all solutions in this problem. The second one just got lucky.