Div2 ppl — Let's rank up above some div1 guys.
Div1 ppl — Let's not get outperformed by some underdogs.

anupamshah_ ?

Then you'll be happy to hear that it is already written.

You know what is better? Editorial before the round happens.

I_love_Tanya_Romanova had posted some great answers on Quora regarding that, you may wanna refer them :)

See here

what a coincidence?

You here asking how to be red and in problem set problem is based on same topic.

I always make strong pretests.

Also, I never seen this Codeforces Round 470 (rated, Div. 1, based on VK Cup 2018 Round 1) before, officer.

Sounds like there'll be game theory problems

Oh shit goddamn grey Indians who love maths disliked my comment and made my contribution < 0

disagree

Hope that I will get rank in 3 digits.

Well done, majk did everything for after-contest.

Then you'll be happy to hear that it is already written.

atulyakv

You forgot to include Mathforces XD

Calculate the loss and profit of each person.

Assign the money from the ones in loss to the ones in profit one by one.

If the remainder of x%14 is zero the answer should be "NO".

xi <= 6 && xi >= 1. For this case answer should be NO.

Look up Splitwise

Calculate the loss and profit of every person. Now you have an array with positive and negative numbers. Store them in two separate vectors 'take' & 'give'.

Assign the money from the vectors 'give' to 'take' element by element greedily.

if (x < 15) 
{
cout << "NO\n";
return 0;
}
x %= 14;
if (1 <= x && x <= 6) cout << "YES\n";
else cout << "NO\n"; 

The reason for so many fails on test case 11 is the handling of the order of events. If you kept track of number of bonuses to a resource, there is a possibility of adding and subtracting the same resource in a single query i.e., a bonus (a,b,c) just ends up replacing the exact same. Only if I had swapped 2 lines...

I related it to a graph and GCD problem...

Me too, it could be simple greedy solution but made it mess by including graph theory

Yup, tried solutions involving moving all children to a parent node (Not even going to start with how I was trying to make it a DAG to root it in the first place) and all sorts of other absurd stuff treating it as a graph problem.

me too i was trying to do something with weighted directed graphs . you are not the only one.

Look at my comment above. Now I know I'm not the only one.

Easily available on internet. "Splitwise algorithm" or "Minimize cash flow between friends".

out of curiosity — how do you expect someone to answer the exact number of how many people proved?

Also IMO problem D is easily proved, but E is indeed the type of problem that many participants submit the correct solution without proper proof.

I did, I guess that's why I'm so slow. :(

I had a proof outline of E in my mind, just that if we produce the obvious minima, there's always a reached bonus because equal sums and proof by contradiction, and if we imagine that this reached bonus isn't a bonus but a normally produced resource, the same idea applies by induction. At that point, I told myself that I have nothing to lose by believing I didn't miss something important.

D is just obvious. We have the minimum required cash flow and we can send this flow any way we want.

I did

I couldn't prove D or E , I was just lucky that my solutions passed as I had no concrete proof. Had any one failed, I would have no idea what to do. Though, D was close to a proof, in the sense that if some subset of people is losing some amount and others are gaining that much(in terms of net amount) then that amount of edges must be there and it turns out we can attain that lower bound precisely, making it the best

You can't get awards for reaching the goals.

Well, consider two things :

1. 1 can never appear in the square. (Why?)

2. A row which makes gcd as 1, can be multiplied by x to get a gcd of x.

Now think of some numbers which make gcd 1 :), and you're almost done

https://codeforces.com/gym/100812 problem A

And not for programmers...

Oh shit goddamn grey Indians who love maths disliked my comment and made my contribution < 0

Thanks :)

It's me!!!!

This is sth I never thought!!!

You can't even image how excited I'm!!! Right now!!!

Because I have never won a prize in cf before, so I want to knwo how can I get it??

thanks a lot!!

My solution is using simulation with memoization. I don't know its time complexity. My implementation can probably be optimized, but I didn't have time to do it during the contest.

It works like this: there is a map, where the key is the current vertex and the current state of some set of vertices. The set is such that, starting from the current state, the token will enter each vertex in the set at least once before entering a vertex that is not in the set. The value is the vertex that is reached and the new state.

This approach should work really well on structured graphs, like red edge from $$$i$$$ to $$$1$$$ and blue edge from $$$i$$$ to $$$i+1$$$ for all $$$i$$$.

I think that my solution can be adapted to solve your bonus problem as well.

yeah!!! these sure are fun :)

because it's codeforces and not 程式设计forces

Thanks! Finally made it.