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).
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).
std::back_inserter(cd) seems to be more applicable than std::inserter(cd, cd.begin())
If there is no entry for name1, nothing will happen. If there is no entry, it will be the same as factor[name1] = 0.
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;I didn't write this statement as an if condition.
great explanation for problem D!!!
Seriously, guys, what's wrong with you?
I am here after 9 years, The explanation of problem D is the best explanation i have ever read on codeforces ! Thank you
Thanks!
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://codeforces.net/contest/75/submission/78440577 Here is my submission.
It looks like you're getting overflow from
(digit*pow(10,nonZero)). This can be fixed by using a running place multiplier instead ofpow.See 78443731 for an accepted version of your code with that change.
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 )