stgatilov's blog

Codeforces #47 problem solutions
By stgatilov, 14 years ago, translation, In English

Problem A: Answer is floor(N*M*0.5). Since there is N*M cells on the board and each domino covers exactly two of them we cannot place more for sure. Now let's show how to place exactly this number of dominoes. If N is even, then place M rows of N/2 dominoes and cover the whole board. Else N is odd, so cover N-1 row of the board as shown above and put floor(M/2) dominoes to the last row. In the worst case (N and M are odd) one cell remains uncovered.

Problem B: Of course you were expected to code solution which is not quadratic in time complexity. Iterate over the string and count how many times each char is used. Let Ki be the number of occurrences of char with ASCII-code i in the string S. Then answer is sum(Ki2). While coding the solution the following common mistakes were made:

1. Code quadratic solution (double loop over the string)
2. Forget to use int64. Whether in answer or in Ki squaring.
3. Wrong int64 output.

All these problems were easily hacked by max test with 100000 equal chars. This turned the hacking process into the game "who hacks the next B solution faster" because newbies often made all these mistakes. This problem was severed by the fact that GCC-compiler turned out to be MinGW-compiler, so output like printf("%lld", ...) did not work on it. Another strange problem hackers faced was quiet test truncation by length about 30000 when copy/pasting it into the test editor. Of course the overflow in solution disappears after it.

Problem C: You were asked to make all the cows strictly inside the interior of the route. Initially I planned to put "non-strict" there, but later I abandoned this idea because the answer for single point was really weird then=) The difference in solution is quite small. The answer for "strict" problem is always more than for "non-strict" by exactly 4. Some coders preferred to add four neighboring points for each point like a cross to switch to solving non-strict problem.

The non-strict problem is solved in the following way. Notice that the required route can always be searched as an octagon, perhaps with some zero sides. Take four pairs of parallel lines and "press" it to the points. In other words, we find axis-aligned bounding box for the set of points. Then find axis-aligned bounding box of the point set on the picture which is rotated by 45 degrees. Now intersect these two boxes (as filled figures). We get an octagon in the common case, which is the required one. To implement the solution, we have to calculate minimums and maximums of X, Y, X+Y, X-Y through all the points, then use non-trivial formulas to get the answer.

A lot of contestants solved the problem in other way. It is easy to see that to move by vector (X, Y) shepherd needs to make max(|X|, |Y|) turns. We can make the shepherd walk along the vertices of convex hull. We need to run a standard Graham scan and then iterate through all the points on the hull and sum max(|X'-X|, |Y'-Y|) for all pairs of neighboring vertices in it. This solution is also correct.

There was an idea to make limit on coordinates equal to 109, but we decided that there was no need to ask for int64 again. Perhaps it'd have been better if there'd been int64 in this problem instead of problem B.

Problem D: The problem statement looks intricate and aggressive. That's because the problem legend originates from civil defense classes in the university. Civil defense is such a discipline which for example teaches how to behave before and after nuclear attack...

First of all we should notice that the bigger the warhead, the better (I mean the probability to succeed is higher). This seems quite reasonable. Function P(D, R) increases as R increases with fixed D. Obviously the probability to hit at least K objects increases in this case too. Hence we can find the answer by binary search. We have to be able to find the probability to accomplish the mission with fixed and known radius R to perform binary search.

Now we have to solve the problem: there are N objects, each of them is destroyed with given probability (pi). Find the probability to destroy at least K of them. The problem is solved by dynamic programming which is similar to calculating binomial coefficients using Pascal's triangle. Let R[i, j] be the probability to hit exactly j objects among the first i of all the given ones. If we find all the R values for 0<=j<=i<=N, then the answer is calculated as sum_{j=k..N} R[N, j]. The base of DP is: R[0, 0] = 1. Induction (calculating the new values) is given by the formula R[i, j] = R[i-1, j-1] * pi + R[i-1, j] * (1-pi). Keep in mind that for j<0 or j>i all the elements of R are zeroes.

It was shown experimentally that many coders (me included) try to solve the problem by taking into account only the closest K targets. I.e. they think that the probability to succeed is simply p1 * p2 *... * pK. This is wrong: for example, if two buildings with equal distance are given, then the probability to hit at least one of them is 1-(1-p)2 instead of p. But I decided to please these coders and composed the pretests only of the cases on which this solution passes=) So this particular incorrect solution was passing all the pretests intentionally.

Problem E: Let D = b2-c be quarter of discriminant. The equation roots are -b-sqrt(D) и -b+sqrt(D). Thus there are two types of roots: irrational ones like x +- sqrt(y) and integer ones. We count the number of different roots separately for these types.

Irrational roots are in form x+sqrt(y) (y is not square of integer). If two numbers in this form are equal, then their x и y values are also equal. It can be checked on the piece of paper. The main idea is to use irrationality of sqrt(y). Thus if two irrational roots are equal, then the equations are the same. Hence all the irrational roots of all the given equations are different. Let's iterate b=1..N. For each of b values we have to find the number of equations with positive discriminant which are not squares on integers. I.e. number of c=1...M with D = b2-c is not square of integer. We can calculate set of all possible values of D as a segment [L; R] (L >= 0). Then take its size (R-L+1) and subtract number of squares in it. It is exactly the the number of equations with irrational roots for a fixed b. Multiply it by 2 (two roots per equation) and add it to the answer.

Now let's handle integer roots. For a fixed b we've calculated the segment [L;R] of all D values. Then sqrt(D) takes integer values in segment [l; r] = [ceil(sqrt(L)); floor(sqrt(R))]. We put this segment into the formula for equation roots and understand that all the integer roots of equations with fixed b compose segments [-b-r;-b-l] и [-b+l;-b+r]. However the integer roots may substantially be equal for different equations. That's why we have to mark in a global data structure that all the roots in these two segments are "found". After we iterate through all b=1..N, we have to find number of integers marked at least once in this data structure.

This data structure is implemented on array. All the integer roots of equations lie in bounds from -10000000 to 0. Allocate an array Q which is a bit larger in size. To mark segment [s; t] we increment Q[s] by one and decrement Q[t+1] by one. At the end of the solution iterate through the whole array Q from left to right and calculate prefix sums to array S. I.e. S[i] = Q[-10000010] + Q[-10000009] + ... + Q[i-1] + Q[i]. Then S[i] represents number of times we've marked number i. Now iterate through S array and count number of nonzero elements. It is the number of different integer roots.

The solution requires O(N) time since we have to iterate through all b values. It is likely that purely combinatoric (O(1)) formula for answer exists=)

Conclusion. I think that there were two problems in the contest (except the system's epic fail of course). The first: there was no technically hard problem. Because of this high-rated coders had solved all the problems by the end of first hour and had to torture themselves by hacking others in heavily instable contest system during the remaining hour. I think that problem E in any round should be really tough to code. The second problem is huge number of hacks for problem B. I should have set the limit on string length to 40000. There is one more interesting question: why are divisions merged together? It would be wiser if any room were first division only or second division only. Then first division coders would concentrate on hacking solution for difficult problems instead of catching simple newbies' mistakes.

Reminder: you can see the tests for all problems in contest system.



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

Comments Comments (17)
| Write comment?
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Good Post!
→ Reply
14 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
I think there are too many people in one room, someone may win this game only by hacking. And it's unfair when some competitors do hacking simultaneously, the one with better network always win. 
In this contest I finished Problem B soon and locked it. When I started hacking, unfortunately I have an opponent. Both of us refreshed the page again and again to check new submitter's source. But owe to the bad network condition, I always half a beat too slow. The final score is 1:11, I lost and wasted a lot of time.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In Problem B the length of string is not less than 10^5
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I don't understand why my code gets WA for problem B? please help.


#include<iostream>
#include <string>
using namespace std;
int mx,i,a[1000000],mn;
long long sum,t;

int main()
{
    string str;
    mx=0;
    cin>>str;
    for(i=0;i<str.size();i++)
    {
        t=str[i];
        if(t>mx)
            mx=t;       
        a[t]++;
    }
    for(i=0;i<=mx;i++)
        sum+=(a[i]*a[i]);
    cout<<sum<<endl;   
   
return 0;
}
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is the problem:

    sum+=(a[i]*a[i]);

    Here you multiply two numbers of type int and receive result in type int. But the result can be 1010.

    → Reply
14 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it
In problem E there is an easier way of finding all integer roots.

Clearly both roots are  < 0 ( product is positive & sum is negative).
Let roots be -p & -q.   ( p & q are positive integers ).
we have p + q <= 2 * N . Also p * q <=M.

Take an odd integer o. Lets see when would we have an equation having -o as a root. Other root should also be odd & hence absolute value at least 1 . So for all odd o  st 1<=o <= min( 2 * N -1 , M) there is an equation which has -o as root :  (x + o) ( x + 1)

Similarly for all even integers e, st  1 <= e <= min ( 2N -2, M/ 2) there is an equation with -e as root : ( x + e) ( x + 2 )

So  negatives of integer roots are just odd positive integers up till min (2N-1, M)  with even positive integers up till min ( 2 N -2 , M/2)

Desired number is = (min( 2N-1, M) + 1 ) / 2 +  min ( 2 N -2 , M/ 2) / 2


→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Great analysis!
In problem E to find integer roots I just iterated over all possible roots x and for each of them over all possible coefficients c (they must be divisible by x). Knowing x and c, we can find the second root and coefficient b and check the conditions. The time is .
→ Reply
14 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
i wrote the code for problem E but got time limit exceeded error.

My code is below (www.codetolearn.blogspot.com):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String ans=bf.readLine();
        String var[]=ans.split(" ");
        HashMap<Integer, Double> val=new HashMap<Integer, Double>();
        double dx=0;
        int cnt=0;
        double rt1=0;
        double rt2=0;
        val.put(null, (double)1);
        val.put(null, (double) 2);
       
        for(double i=1;i<=Integer.parseInt(var[0]);i++){
            for(double j=1;j<=Integer.parseInt(var[1]);j++){
                dx= Math.pow(2*i, 2)-(4*j);
                if(dx>0){
                    rt1=  (((-2*i)+ Math.sqrt(dx)))/2;
                    rt2=  (((-2*i) - Math.sqrt(dx)))/2;
                    if(val.get(cnt)==null){
                        cnt=cnt+1;
                        val.put(cnt,(double)rt2);
                    }
                   
                    if(val.get(cnt)==null){

                        cnt=cnt+1;
                        val.put(cnt,(double)rt1);
                       
                    }
                    if(val.containsValue(rt1) &&val.containsValue(rt2)){
                       
                    }else if(val.containsValue(rt1)){
                        cnt=cnt+1;
                        val.put(cnt,(double)rt2);
                       
                    }else if(val.containsValue(rt2)){

                        cnt=cnt+1;
                        val.put(cnt,(double)rt1);
                       
                    }else{
                        cnt=cnt+2;
                    val.put(cnt,(double)rt1);
                    val.put(cnt,(double)rt2);
                   
                    }
                   
                }else if(dx==0){
                    rt1=(double) ((-2*i)/2);
               
                    if(val.get(1)==null){
                        cnt=cnt+1;
                        val.put(cnt,(double) rt1);   
                    }
                   
                    if(val.containsValue(rt1)){
                       
                    }else{
                        cnt=cnt+1;
                        val.put(cnt,(double)rt1);
                    }

                }
            }
        }
        System.out.println(cnt);
    }
}
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    IMHO, You got time limit exceeded error becouse of double for(). In problem E n,m<=500000!
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Ok fine........for problem B it was said that the length of the string would not exceed the size 105. But i think it didn't hold the same. I think a larger sized of input was there in the input file. Because for counting occurrence of the respective ASCII characters in the string it is certainly  enough to use array int b[256], and for the result it is __int64 sum. but i repeatedly got WA until i replaced int b[256] with __int64 b[256]. I am really confused. PLz make me understand where is my shortcoming. even i am posting my code below. with which i got wa....
#include<stdio.h>
#include<string.h>
char a[1000009];
int b[256];
int main()
{
        __int64 i,sum,n;
        gets(a);
        n=strlen(a);
        for(i=0;i<n;i++){
                ++b[a[i]];
        }
        sum=0;
        for(i=0;i<256;i++){
                if(b[i]){
                        sum+=b[i]*b[i];
                        b[i]=0;
                }
        }
        printf("%I64d\n",sum);
        return 0;
}

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    sum+=b[i]*b[i];
    That's the mistake. Compiler will calculate the right part first: b[i] is int, so b[i]*b[i] is int too.
    If b[i]=100000, this line became the following: sum += 1410065408;
    So you should write
    sum    +=(__int64)b[i]*b[i];
    instead.
    Compiler see that the first operand is __int64, and will convert the second one to __int64 too.
    → Reply