Radewoosh's blog

Codeforces Round #304 (Div.2) editorial
By Radewoosh, 9 years ago, In English

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.

  • Vote: I like it
  • +58
  • Vote: I do not like it

Comments Comments (89)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Fast editorial!

→ Reply
»
9 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Ironically I hacked people using a test case my code fails on

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is it possible to solve E without using maxflow?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    It can be represented as a system of n linear equations of m variables, each representing the flow on each edge. So, it can be solved using Gaussian elimination.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      At first I thought the solution is Gaussian elimination, but I'm stuck because there are not just equation, there are inequality system too (we must send number of people in city i less than or equal a_i), how to handle this?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Of course we should use linear programming instead of Gaussian elimination. But every network flow can be modeled as linear programming, so that's not a surprise.

        → Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

cin / cout fails and scanf / printf passes.. BAD!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Hmmm I always thought cin/cout are fast enough if we put ios_base::sync_with_stdio(false); cin.tie(NULL);, but my code TLEed with those optimizations :(

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +9 Vote: I do not like it

      In cin cout try printing with "\n" instead of endl; In C++, "endl" clears the buffer after adding a new line character so there is an overhead, which might be the cause of your TLE.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hmm I replaced them, but it didn't change much 11228459 .

        I think it's because I have #define endl '\n', so any endl is already replaced while compiling.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          Try these 3 together with the "\n". It worked for me

          ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I finally got AC after adding cin.tie(0);. Thanks!

            → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    This was the reason I had left other judges and joined CodeForces..
    But this contest.. brought back bad memories..
    disheartened...

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you are talking about codechef...

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can any one tell what hash function will accept Question — C .

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +4 Vote: I do not like it

    the cards are numbered distinctly from 1 to n, hence the state can be represented in base 11 and converted to decimal. Hence, if player 1 has cards numbered a0,a1,a2... the hash can be a0*(11**0) + a1*(11**1) +a2*(11**2) and so on... This can be stored in a set of pair<long long,long long>

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      or you could just subtract 1 from each number and then you have base 10.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        wont this approach fail if we have the card numbered 1 at the end of the stack? for eg. take 2 states: player 1 has the cards 1,2 and another state where player 1 has just card 2. These two states collide if the above hashing is used.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          oh well yes, that could happen. Sorry, I guess there was no testcase where the second set's hash was also same. It would have given a wrong answer then.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Do hacks which fail many solutions get added to the final system tests?

            → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well card 1 cannot come to the bottom of the stack after it has been at the top once, because the opponent will first put card 1 to the bottom and then his top card to the bottom.

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Or, you can use strings and maps, Or, you can change the queue say, 2 4 3 1-> integer 2431.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you're not really keen on using a hash function, then using set< pair< vector , vector >> will also do.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I don't use any hash at all. I just compare all the queue. See 11213781 for details

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is no special function, I use pair <list, list> and gave me AC . (It was after the contest since before I forget placing a single line).

    s.insert (t);

    :'( Here is my submission

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    i converted numbers to string then using **unordered_set < string > ** got AC

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

i implement D with same idea !!

but got TLE !!!

my code !! 11222167 can anyone tell my why please :)

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    cin cout are too slow for such a large size of input output. Try switching to scanf, printf and it will work :)

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for C is more tricky! I thought about using map/unordered_map with hashes but if this will fit in the TL then we will fit in TL without using them. So if the elapsed time is greater than 1.80 I just print -1 stop working.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

" It's easy to count who wins and after how many "fights" "

Does this sentence means that we can find number of fights without simulation ?

→ Reply
»
9 years ago, # |
  Vote: I like it +38 Vote: I do not like it

How to prove that the longest path in the state-graph for n = 10 has length 106 in problem C ?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I wrote a program that calculated the entire graph and the length of the longest path in it.

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem C has tag "dfs and similar"; does this only refer to calculating longest path or is there real way to solve with dfs?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The alternative solution can be viewed as something similar to DFS. A vertex represents a state (queues of players). The only neighbour of a vertex is the result of a fight. Keep traversing the graph until there's no neighbours (game ended) or you visit a vertex twice (cycle).

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

8 successful hacking attempts on 2nd question and my own code failed! Feeling meh..!!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did figure out that Problem E needs Max Flow and build the graph. But I got Wrong Answer for grid printing on pre test. My Code: http://codeforces.net/contest/546/submission/11223671

Can anyone help me that where and what I am doing wrong ?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In your answer there are 105 soldiers in 10th city.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain what's the mathematical thought behind this statement?

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    the number of prime factors of a number a is equal to the number of prime factors of the number a divided by any of its prime factors, plus one (the one you are removing).

    For example: primeFactors[8] = primeFactors[8 / 2] + 1.

    If "a" is a prime itself: primeFactors[a] = primeFactors[a / a] + 1 = 1

    Hope this helped

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you choose a factor X such X=A*B (X is a composite number) you couldn't get the maximum score (you must select first A, and then B).

    That's why you must use a prime numbers:

    primefactors(a) = primefactors(a / PRIMEDIVISOR_OF[a]) + 1

    I hope this help you.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved C using four queues and comparing them each time with their original ones . I got AC. But what is the Hash thing most of the coders are talking about it in the comments?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In 2nd sample test case, pair<2,13>,pair<3,12> are states. Use a set to store these pairs. If on any turn you get one of these pairs again, you know that you've ended up in a cycle.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are cards stored as strings in pair like pair< " State of Player 1 " , "State of Player "> ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Either that, or convert the queue into an integer. eg: if player 1's queue is 1,3,2,4,10 then it can be hashed as 02139.

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I did it with a string. Since all cards are  ≤ 10, you can just subtract one from them and work base 10.

    Then you build a string from all the numbers from deck 1, then an asterisk or whatever non-numeric symbol you want, then all the numbers from deck 2. If you ever happen across a string you've seen before, you're in a cycle.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Would this approach be helpful if no of cards were large? Will it get TLE ?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Clearly, if number of cards is  > 254, then you couldn't hash with a string.

        I didn't do the math, but I'm certain that with big enough number of cards, the brute-force solution would get TLE. Let's say, for example, that you have 105 cards numbered 1..105, well... this solution wouldn't work at all.

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In question B, how do you know that the max coolness is 2n — 1?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    The worst case is that all cards have value N. In that case, for N - 1 cards, you would need to increase the value. The maximum of the final values will be N + (N - 1), which is 2N - 1.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have written the solution for Soldier and Bananas and it works on my computer. But when I submit the solution I get a compilation error — "program.cpp:1:21: fatal error: iostream.h: No such file or directory #include<iostream.h> " I tried even #include but still the same result :(

I am new here and not sure how to submit the solution. I have written the solution in c++.

Thanks

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    iostream is used for C++. iostream.h is deprecated iostream vs iostream.h

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    remove the '.h' and just type "#include"..this should work fine i think!!

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    I have check your submissions, you will be correct while using iostream and submitting with "C++" but not "C".

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There are a list of compilers there...which one should I use? Sorry if its a silly question :)

      Thanks

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        I always use gnu g++ 4.9.2, but I think gnu g++11 and vc++ is ok. It depends on your programs.

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone suggest me some exercises about max flow in order to solve the problem E? (I am newbie in max-flow problems...) Thanks in advance.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be great if you could add solution code links (at least for problems D and E).

Thanks

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's really disheartening when one's code fails only due to cin/cout. the D problem. TLE : 11222951 AC : 11234082

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why does this solution give AC? Problem D, I think worst case complexity in still N*sqrt(N).SOLUTION

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me optimize this code — 11218347. I checked all the states to find the result.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because of n is too small , you can set a condition like if(step>1000) than the game will never end .

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You compare with first state. It's wrong. Test 29:

    2 4 3 1 and 5

    4 3 1 and 2 5

    3 1 2 4 and 5

    1 2 4 and 3 5

    2 4 and 5 1 3!!!

    4 and 1 3 2 5

    1 4 and 3 2 5

    4 and 2 5 1 3

    2 4 and 5 1 3!!!

    You need to compare with all states.

    Combinatorics says that 11! ~ 4*10^7 states exists. So you can make 4*10^7 "fights". In optimize, you can use queue instead of vector. 11239957

    Another way — use set<pair<queue, queue>>. 11226550

    P.S. Sorry for bad English

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone find the bug of this code 11240132 for problem C? It looks completely ok, but can't even pass the 1st sample case!! I spoiled my 1 hour during the contest but couldn't understand why :(

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Someone missed else)

    if (a.front()>b.front())
{
...
}
//???
if (a.front()<b.front())
{
...		
}
    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E, I guess you missed adding V links, from i (in the left subset) to i+V (on the right subset), this would means the soldiers which started on vertex i can stay there.

→ Reply
»
9 years ago, # |
  Vote: I like it -14 Vote: I do not like it

The contest is too easy.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help. I am getting this as the flow for the first test-case in Problem E. This seems to be a valid flow. But I know this is not the final answer. Where am I going wrong? YES 3 -2 0 0 0 1 1 0 0 3 3 0 0 3 -1 1

P.S. https://ideone.com/bGtOyZ

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me why this solution for problem E gives TLE ? :\ I used Edmonds Karp’s algorithm

12995795

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D has tag "dp".If anyone can solve it using dp can you please explain the logic?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C question is a good one!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain how in Question C the total number of states cannot exceed 106?

    → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anyone explain how they got length 106 in C.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell how in Question C the total number of states cannot exceed 106?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, normal System.out.println(f[a]-f[b]) for each test case will result in a TLE, if you're using Java. So, it's better to use a StringBuilder, append test results to it, and output the composite result after processing all the test cases.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C is fun. I firstly solve it using unordered_map to track card 1 with card 2 and i received wrong answer on test 32, i have realized it's wrong hash, so I give 2 players play at most 1e6 turns, if no one wins, it means they draw. Although 1e6 is much greater than 106, it's the best way i can handle in this situation because I think the time limit is 1s, so i pass 1e6 turns =))

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Easy and Detailed solution for Problem D : https://codeforces.net/gym/328681/submission/116502457

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my code giving TLE? can someone please check?

this is the code —

include <bits/stdc++.h>

using namespace std; typedef long long ll; vector prime_divisor(5000005); vector prime_factors(5000005);

void sieve(){ for(ll i=2;i<=5000000;i++){ ll curr = i; for(ll j=2;j<=curr;j++){ if(curr % j == 0){ prime_divisor[curr] = j; break; } } prime_factors[curr] = prime_factors[curr/prime_divisor[curr]] + 1; } }

int main() { // your code goes here prime_factors[0] = 0; prime_factors[1] = 0; sieve(); for(ll i=2;i<=5000000;i++){ prime_factors[i] += prime_factors[i-1];
}

int t;
scanf("%d",&t);
while(t--){
    int a,b;
    scanf("%d",&a);
    scanf("%d",&b);

    int ans = prime_factors[a] - prime_factors[b];
    printf("%d",ans);
    printf("\n");
}
return 0;

}

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    your sieve is O (n ^ 2) and it should be linear (most likely — I don't know what task is about)

    → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I am performing the same thing in D, but it is showing TLE, I am doing O(k), k = constant, for pre-calculating my prime factors sum and then O(T) for all the test cases.

Problem is my code runs on Test case 3 and 4 which are having same number of test cases as in Test case 5 and it runs on Test case 3 and 4 but shows TLE on Test Case 5..

Why this is happening if it is taking same time (as before taking test cases input operations are same for Test case 3 and 5, and after taking test cases, no. of test cases are same for Test case 3 and 5)

My solution : https://codeforces.net/problemset/submission/546/157507503

A Help would really be appreciated!

→ Reply