ahmed_aly's blog

Codeforces Beta Round #67 (Div. 2) Editorial
By ahmed_aly, 14 years ago, In English
Problem A:
In this problem you need to do what is written in the statement. You can do it in the following 3 steps:
1- Calculate C.
2- Remove all zeros from A, B and C.
3- Check if the new values form a correct equation.

C++ solution for problem A.


Problem B:
This problem is a direct simulation to the rules written in the problem statement.
You need to iterate over all actions and parse each one to know the type of the action, and the 2 names X and Y, and if your name is X or Y then update your priority factor with this person with the action corresponding value. And take care about some special names like "post", "wall", "commented" and "on".
Then sort all names according to the sorting criteria mentioned in the statement.
Just make sure to print all names which are mentioned in the input (excluding yourself), even if the priority factor with you is 0.

C++ solution for problem B.


Problem C:
In this problem you will need to generate all common divisors between a and b before answering any query.
The first step in this problem is to factorize a and b, you can use the trial division technique which runs in O(sqrt(N)), you can check getFactors function in my solutions.
Then using a recursive function you can generate all divisors for a and b from their prime factors, you can check getDivisors function in my solutions.
Then intersect the 2 sets of divisors for both to get all common divisors, you can do this in O(N+M) where N and M are the lengths of the 2 sets, and also you can do a trivial O(N*M) intersection algorithm, because the maximum number of divisors is not too big (it's 1344).
Now for each query you need to find the largest common divisor which lies in the given range, you can do this by sorting all common divisors and do binary search for the largest one which lies in the given range. Also you can do this using linear search, because the total number of queries is not too big.

Also there is much shorter solution for this problem. Here is a hint for it, the GCD between a and b should be dividable by all common divisors of a and b.

C++ solution for problem C (with binary search).
C++ solution for problem C (without binary search).
Java solution for problem C (with binary search).


Problem D:
This problem is my favorite one in this problem set. Maybe it will be easier to solve this problem if you know how to solve the standard one.
But because we can't construct the big array, so we can't apply the standard solution for this problem.
Let's see first how to solve the standard problem, the following code solves it for a given array arr with length len:

int mx = -(1 << 30);
int sum = 0;
for (int j = 0; j < len; j++) {
    mx = max(mx, arr[i]); // we need this for the case where all elements in the array are negatives
    sum += arr[i];
    if (sum < 0)
        sum = 0;
    else
        mx = max(mx, sum);
}

Now let's solve the big array problem, the first step is to calculate 4 values for each small array:
1- The total sum of it, let's call it tot.
2- The maximum sum of 0 or more consecutive elements starting from the first element in the array, let's call it lft.
3- The maximum sum of 0 or more consecutive elements ending at the last element in the array, let's call it rght.
4- The maximum sum of 1 or more consecutive elements, let's call it gen.

The final result will be 1 of 2 cases:
1- The consecutive elements with the maximum sum will start and end inside the same small array.
2- The consecutive elements with the maximum sum will start and end inside different small arrays.

For the first case, we can simply pick the maximum gen for all small arrays which exist in the big array.
For the second case, we can apply something similar to the standard solution, we will keep a variable called sum, and it's initialized to 0, this will be the maximum sum of 0 or more consecutive elements ending at the last element in the previous small array. Now for each small array, if the maximum possible sum will end in this small array, so it will be sum+lft and maximize over this value (make sure this will be for 1 or more elements). And we need to update sum to be the maximum of the following 3 values:
1- sum+tot (we will include all elements of this small array to the old sum).
2- rght (we will take the maximum sum ending at the last element in the current small array).
3- 0 (we will not take any elements in sum).

The running time for this solution will be just for reading the input, in my solutions I have no iterations except for reading the input.

You can check my solutions for more clarification.

C++ solution for problem D.
Java solution for problem D.


Problem E:
The main idea for this problem is not hard, but maybe the hard part is implementing it.
First we need to know if the straight line segment between the source and destination points intersect with the island or not. So we will intersect this line segment with all the polygon sides. If there are 2 segments intersect in more than 1 point we will consider as they don't intersect, because it's mentioned in the problem statement that you can move on the island's edge and it will be considered in the sea.
Now we have a set of all distinct intersection points of the polygon and the straight line segment between the source and destination points. Because the polygon is convex, this set will contain at most 2 points. We have 3 different cases now:
1- This set contains less than 2 points.
2- This set contains 2 points and they are on the same polygon side.
3- This set contains 2 points and they are not on the same polygon side.

In the first 2 cases the result will be simply the length of the straight line segment.
In the 3rd case you can do the following:
1- Move from the source point to the nearest point of the 2 intersection points.
2- You have 3 options here:
    a- Move inside the island to the other intersection point.
    b- Move in clockwise direction on the island's edge to the other intersection point.
    c- Move in anti-clockwise direction on the island's edge to the other intersection point.
    First option will be considered moving inside the island, and the other 2 options will be considered moving in the sea.
    You should pick the minimum one.
3- Move from the 2nd intersection point to the destination point.

Another solution:
You can construct a graph where the nodes are the source point, the destination point, the intersection points and the polygon corner points. Then add an edge between any 2 points which you can move between them with the corresponding cost. Then run any shortest path algorithm, Floyd Warshall for example.

You can check my solutions for more clarification.

C++ solution for problem E.
C++ solution for problem E (with Floyd Warshall).
  • Vote: I like it
  • +44
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
14 years ago, # |
  Vote: I like it +11 Vote: I do not like it
D is also my favourite problem in this problem set :)
And the whole problem set is very nice. It is very diverse: easy implementation, math, dp/classic, geometry. And problems do not require extraodinary knowledge in algorithms.
This round was very suitable for Div2.
→ Reply
14 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Excellent Tutorial's ,  several ways several code for each one , good luck ahmed_aly
→ Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
(In English)
Very nice contest
B can be also solved using regexps

Also in Java we use List, Vector is deprecated ;)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
thank's for your nice contest and tutorial.
I have a question for problem E:
why your algo is correct?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Because you can only move to safe points, so you don't have any other choice.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
(C++ solution for problem C)
std::back_inserter(cd) seems to be more applicable than std::inserter(cd, cd.begin())
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
The c++ code for problem A has integer overflow, since a and b can be up to 999999999, c=a+b cannot fit into 32-bit int. My solution had the same issue and got hacked.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Actually 1999999998 fits into 32bit signed integer
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      That's right. Just realized that my overflow is due to 8999999991, the reverse of 1999999998.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
what does the instruction factor[name1] do?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Just to make an entry for name1 in the map, and it will be 0. Because I have to print all names even if the factor is 0.
    If there is no entry for name1, nothing will happen. If there is no entry, it will be the same as factor[name1] = 0.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      interesting, I just did map.find()==map.end(), but this is much cooler.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        It's actually safer that way. If you search with if( map[ name1 ] ), every time you do the query, the size of the map increases by 1. Try this - 
         
    map< int,int > one, two;
    for(int i=1;i<=100; i++) if( one[i] );
    for(int i=1;i<=100; i++) if( two.find(i) == two.end() );
    cout << one.size() << " " << two.size() << endl;
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it
          In this problem it's the same, because I wanted to make an entry anyway if it doesn't exist.
          I didn't write this statement as an if condition.
          → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

great explanation for problem D!!!

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

I am here after 9 years, The explanation of problem D is the best explanation i have ever read on codeforces ! Thank you

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

Hello! I am here from the a2oj ladder. I received a WA on test case 14 in problem A. When I checked the test case and ran it locally, it is giving the correct answer. Why is the output different here? https://mirror.codeforces.com/contest/75/submission/78440577 Here is my submission.

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

    It looks like you're getting overflow from (digit*pow(10,nonZero)). This can be fixed by using a running place multiplier instead of pow.

    See 78443731 for an accepted version of your code with that change.

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In C problem : we can store the gcd(A,B) in a variable (X)

then compute all divisors of X :

for(int i=1;i*i<=X;i++) if(X%i==0) // then i and X/i are divisors of X

like we could store all divisors

and then apply binary search (upper bound )

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This submission 293191001 get Accepted and i think must get time limit exceeded.
Because I in this code calculate gcd of a and b and this take O(log min(a,b)),
Then store all prime factors in array this take O(sqrt(gcd(a, b))),
Then generate all possible subsets of prime factors array and store results of multiplication of each subset in set this take O(((2^n)*n) if n = size of array,
Then for every query I will print answer using upper_bound function this take O(logn),
So if gcd of a,b is greater than 25 must get time limit exceeded.

Example a = 536870912 b = 536870912 gcd(a, b) = 536870912
So we have 29 prime factors 2^29 = 536870912
So if generate all possible subsets this will take O((2^n)*n) ~ (2^29) * 29) = 15,569,256,448 ~ 1e10
time limit exceeded :)

→ Reply