2

Codeforces Round #304 (Div.2) editorial

 1 year ago
source link: https://codeforces.com/blog/entry/18034
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

A. Soldier and Bananas

We can easily calculate the sum of money that we need to buy all the bananas that we want, let's name it x.

If n >  = x the answer is 0, because we don't need to borrow anything.

Otherwise the answer is x - n.

B. Soldier and Badges

Let's count the number of badges with coolness factor 1, 2 and so on. Then, let's look at the number of badges with value equal to 1. If it's greater than 1, we have to increase a value of every of them except for one. Then, we look at number of badges with value 2, 3 and so on up to 2n - 2 (because maximum value of badge which we can achieve is 2n - 1). It is easy to see that this is the correct solution. We can implement it in O(n), but solutions that work in complexity O(n^2) also passed.

C. Soldier and Cards

It's easy to count who wins and after how many "fights", but it's harder to say, that game won't end. How to do it?

Firstly let's count a number of different states that we can have in the game. Cards can be arranged in any one of n! ways. In every of this combination, we must separate first soldier's cards from the second one's. We can separate it in n + 1 places (because we can count the before and after deck case too).

So war has (n + 1)! states. If we'd do (n + 1)! "fights" and we have not finished the game yes, then we'll be sure that there is a state, that we passed at least twice. That means that we have a cycle, and game won't end.

After checking this game more accurately I can say that the longest path in the state-graph for n = 10 has length 106, so it is enough to do 106 fights, but solutions that did about 40 millions also passed.

Alternative solution is to map states that we already passed. If we know, that we longest time needed to return to state is about 100, then we know that this solution is correct and fast.

D. Soldier and Number Game

Firstly we have to note, that second soldier should choose only prime numbers. If he choose a composite number x that is equal to p * q, he can choose first p, then q and get better score. So our task is to find a number of prime factors in factorization of n.

Now we have to note that factorization of number a! / b! is this same as factorization of numbers (b + 1)*(b + 2)*...*(a - 1)*a.

Let's count number of prime factor in factorization of every number from 2 to 5000000.

First, we use Sieve of Eratosthenes to find a prime diviser of each of these numbers. Then we can calculate a number of prime factors in factorization of a using the formula:

primefactors[a] = primefactors[a / primediviser[a]] + 1

When we know all these numbers, we can use a prefix sums, and then answer for sum on interval.

E. Soldier and Traveling

There are few ways to solve this task, but I'll describe the simplest (in my opinion) one.

Let's build a flow network in following way:

Make a source.

Make a first group of vertices consisting of n vertices, each of them for one city.

Connect a source with ith vertex in first group with edge that has capacity ai.

Make a sink and second group of vertices in the same way, but use bi except for ai.

If there is a road between cities i and j or i = j. Make two edges, first should be connecting ith vertex from first group, and jth vertex from second group, and has infinity capacity. Second should be similar, but connect jth from first group and ith from second group.

Then find a maxflow, in any complexity.

If maxflow is equal to sum of ai and is equal to sum of bi, then there exists an answer. How can we get it? We just have to check how many units are we pushing through edge connecting two vertices from different groups.

I told about many solutions, because every solution, which doesn't use greedy strategy, can undo it's previous pushes, and does it in reasonable complexity should pass.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK