Cards

We notice that the second box includes only even numbers , because all numbers in it are in the form 2X

• if the number is odd it's obviously in the first box .

• if the number X is even then X and X/2 will not be in the same box .

So we can keep dividing the number on 2 until we get an odd number which is obviously in the first box, After that we can easily compute the answer depending on how many times we divided the number until it became odd .

Total Complexity: O(log(Q))
Problem by: Ahmad1

RGB plants

Since n is very large, we have to find a fast way to calculate the answer.

We can notice that after each day, we can calculate the number of each one of the flowers New, based on the number of the flowers on the day before Old, like the following:

• The number of red flowers would be equal to NewRed = OldRed*1 + OldGreen*4 + OldBlue*7.

• The number of green flowers would be equal to NewGreen = OldRed*2 + OldGreen*5 + OldBlue*8.

• The number of blue flowers would be equal to NewBlue = OldRed*3 + OldGreen*6 + OldBlue*9.

This can be done using fast matrix multiplication, where both base and transition matrices would be of size 3x3.

Total Complexity: O(Log(n)).
Problem by: Ali Hasan

Ramzi

This is a simple Floyd-Warshall problem. For each edge, store a pair of integers (walking distance,total distance).

For car roads, walking distance = 0,total distance = length of edge

For pedestrian roads, walking distance = total distance = length of edge

Now perform Floyd-Warshall on these pairs:

pair<int, int> operator+(pair<int, int> A, pair<int, int> B) {
    return make_pair(A.first + B.first, A.second + B.second);
}
int n;
pair<int,int> b[1001][1001];
void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                b[i][j] = min(b[i][j], b[i][k] + b[k][j]);
}

It can also be solved with Dijkstra, but the constraints allow Floyd-Warshall, and it is easier to code.
Total Complexity: O(n^3) (Floyd) or O(n*log(n)+m) (Dijkstra)
Problem by: muaz-32

Max or Min .. that is the question!

The answer is the product of the biggest two numbers :D
Total Complexity: O(1)
Problem by: muaz-32

Playing with numbers

First solution

If we were asked to find the smallest number by deleting only one number , we will find the first digit which is greater than the digit to the right of it and delete it, or delete the right most digit if there is no such digit.

By deleting K digits we can repeat the above process K times but this will give TLE, By using a stack we can solve it in O(n) where the stack contains the non deleted digits to the left of the current digit.
Starting from first digit where the stack is empty , we will keep deleting digits from top of the stack while the top of stack is bigger than the current digit and we can delete more digits , after that we push current digit to the stack and move to the next one .

Now the final result is in the stack ( from bottom to top) .

here is a c++ small code :

        string S;
	int K;
	stack<char> Stack; 
	for (int i = 0; i < S.size(); i++){
		while (!Stack.empty() && K > 0 && S[i] < Stack.top()){
			Stack.pop();
			K--;
		}
		Stack.push(S[i]);
	}
        while(k--)
                Stack.pop();

repeat a similar process to find the biggest number .

Second solution

Deleting N digits from S can be also understood as keeping len - N digits from the number S, where len is the length of the number S.

Let's calculate an array cnt[i][j] which represents the last appearance of the digit i after the position j. This array can be calculated using simple dynamic approach.

The maximum number can be obtained using the following approach: Let's iterate over the digits of the number S from left to right, taking as many 9's as we can, and skipping other digits. When we can't take any more 9's (either because there is no more 9's, or because taking the next 9 would result in a string with length less than len - N), let's start taking as many 8's as we can in the same manner, and so on.

The minimum number can be obtained using a similar approach: Let's iterate over the digits of the number S from left to right, taking as many 0's as we can, and skipping other digits. When we can't take any more 0's (either because there is no more 0's, or because taking the next 0 would result in a string with length less than len - N), let's start taking as many 1's as we can in the same manner, and so on.

Total Complexity: O(length(S)).
Problem by: Ahmad1

Fairness

Let DP[i][j] be the minimum possible unfairness factor after distributing the first i coins, while the current difference between the sum of Dwik's and Samir's coins is j.
Since j might be negative, Add M to all differences. (M is the maximum possible difference).
At each step, you can either give the next coin to the Samir or to Dwik.
If you give it to Samir, the difference will increase by a[i+1]. Otherwise it will decrease by a[i+1].

And the unfairness value would be max(maximum difference so far,current difference)

DP[0][M]=0

DP[i+1][j+a[i+1]]=min(DP[i+1][j+a[i+1]],max(DP[i][j],abs(j+a[i+1]-M)))

DP[i+1][j-a[i+1]]=min(DP[i+1][j-a[i+1]],max(DP[i][j],abs(j-a[i+1]-M)))

Total Complexity: O(n*M)

Note: With these constraints, it would be enough to consider that M equals the sum of all coins.

However, you can prove that the difference will never be more than the maximum coin. (If giving the coin to one of the kids will make the difference more than the maximum coin, you can give it to the other kid and guarantee a difference less than or equal to the maximum coin).

Problem by: Ahmad1

Repeat it

First Solution

If we started with N , Adding 'N' to the right of it means adding N * 10^len, then to add another N we should add N * 10^{(len * 2)} and so on ..

It's easy to see that the final number is equal to :

Second solution

We can notice that the answer can be calculated on M steps.

On the first step for example the answer would be (N * 10^len + N)%10⁹ + 7, where len is the length of the number N.

Using this we can solve the problem with fast matrix multiplication.

Total Complexity: O(Log(M)).

Problem by: Pepe.Chess

Robocon Club

• let's convert the revolution speed to linear speed by multiplying v_r , v_l by 2 * π * R

• it can be proven that the linear speed of the center is v_c = (v_l + v_r) / 2

• if v_r = v_l then the robot is moving forward in a straight line and the coordinates of the center will be (0, v_r * s)

• if v_r ≠ v_l then it can be proven that the robot is moving around a point in a circular path , if we know the coordinates of this point we can compute the new coordinate of the center by rotating it around this point.

• Draw a vector of length v_r from (0, L) (right wheel point ) facing positive Y axis (because the speed is positive), and another one of length v_l from (0,  - L) (left wheel point ) facing positive Y axis, then draw a line that passes from the ends of these two vectors , it will intersect with the X axis in a point which is the center of the circular path of the robot , it is let it be P .

Now rotate C(0, 0) (the center of the robot ) around P by angle Q degrees clockwise if v_l > v_r or counter clockwise if v_l < v_r where where r is the distance between C and P .

Problem by: Ahmad1

Playing With Strings

We can easily notice that the order of the letters in each string is not important. Therefore, all we have to do, is to calculate the number of appearances for each alphabetical letter. Let's calculate two arrays cnt1 and cnt2.

cnt1[i] represents the number of times the letter i has appeared in the string S1.

cnt2[i] represents the number of times the letter i has appeared in the string S2.

The answer is simply to accumulate abs(cnt1[i] - cnt2[i]) for all i from a to z.

Total Complexity: O(n), where n is the length of the longest string among S1 and S2.

Problem by: SAeed

Cola

1) The order of processing the queries does not change the outcome.
2)

Add x to position i
Add y to position i

No matter where they appear in the sequence of queries, are equivalent to:

Add x+y to position i

Using the previous observations, we can process the queries offline.

Let A[i] be the sum of all values of queries related to i.

Start from left to right, if A[i] is more than the size of the i^th bottle, fill it and add the rest to A[i+1], otherwise add A[i] liters to the bottle.

A[n+1] is the amount of wasted cola.

Total Complexity: O(n+q)

Problem by: Ahmad1

Army

That's a simple Maximum Bipartite Matching problem.

Put the soldiers on the left and places on the right then add an edge between soldier x and place y if place y is one of the places preferred by soldier x and the union of the set of weapons available in place y and the set of weapons preferred by soldier x is not an empty set .

Then find the maximum matching using any algorithm .

Problem by: Ahmad1 and muaz-32

Thanks for participating! I hope you liked the problems, any feedback is appreciated.