Hello,

Recently my friend encountered the following problem during a coding interview:

You are given a string $$$S$$$ and a set $$$T$$$ of $$$n$$$ strings. You need to choose a multiset from $$$T$$$ (you can choose the same string any number of times) and then concatenate the strings from the multiset in any order to obtain the string $$$S$$$. What is the maximum possible size of such a multiset?

There is a simple $$$O(|S|^2)$$$ solution using DP + trie. First add all strings from $$$T$$$ to a trie. Let $$$DP[i]$$$ be the answer for $$$S_{i...|S|-1}$$$. To calculate $$$DP[i]$$$, we traverse the trie according to the substring $$$S_{i...|S|-1}$$$, and try to update $$$DP[i]$$$ for each string we encounter in the trie.

Assuming the sum of the lengths of strings from the set $$$T$$$ is $$$X$$$, there is also a solution with complexity $$$O(|S| * sqrt(X))$$$:

Is there a faster solution to this problem? I've tried for a long time without any success.

Any help would be appreciated, thanks!

Today my friend told me that my solution for problem D in yesterday's educational contest failed on system tests. "Another silly bug", I thought.

I opened my submissions to check why it failed and I was surprised to see that the verdict was compilation error!

This is my submission, and this is what the error message says:

Can't compile file: Compilation process returned error: idleness limit exceeded (process hangs)

Any idea why this could happen? It's unrated anyways so it's not a big deal but this may have happened to other rated participants too.

Hello everyone,

This issue was mentioned several times before like here. Someone participates in a contest, doesn't do well, submits his solutions from another account so that his submissions are skipped and he is removed from the contest. No rating loss, no penalty, no ban, nothing.

Why not skip the submissions and keep the user in the contest? is there a reason for this? perhaps sometimes solutions are skipped for other reasons which aren't the participant's fault?

First I would like to apologize for the error in the test cases of problem G. All solutions were rejudged and 3 teams/participants were affected, I am very sorry.

Also, thanks to Ashishgup for discovering the error.

I hope you enjoyed the problems in general, below is a brief description of the solutions (if you need a detailed explanation of some problem write in the comments)

Any feedback is appreciated :)

A. Printing Books

While the number of digits left is enough, increase X to the closest power of 10, and subtract the number of digits needed from N. Let's denote the number of digits in X as d(X) and the smallest power of 10 greater than X as p(X).

while (p(X)-X)*d(X) <= N
    N-=(p(X)-X)*d(X)
    X=p(X)
    ans+=p(X)-X

At the end, there might be some leftovers from N, if it is not divisible by d(X), then the answer is -1. Otherwise, add to ans.

B. Ali and Wi-Fi

Let's say you want to join a subset of the given networks, to do this, you must stand in the area of intersection of all the circles of these networks. This area is enclosed by some arcs of the circles and points of intersection of these arcs, the area always contains points of intersection between 2 or more of these circles, or a center of one or more of the circles. So it is possible to obtain the optimal answer at one of the intersection points or at the center of some circle.

This way, we need to check O(n²) points (n centers, and at most 2 points from each pair of circles). To check each point, we go through all circles and store the speeds of the circles that cover this point, then sort these speeds and take the maximum m speeds.

Complexity: O(n³log(n))

C. Shahhoud Training Hussain

Each day, Hussein receives K problems, and solves min(P, K) of them. So he will miss K - min(P, K) problems everyday.

Since we have N days, the answer is N * (K - min(K, P))

Complexity: O(1)

D. Largest Group

For each girl, calculate the mask of the boys that this girl is friends with. Now for each one of the 2^P possible subsets of girls, calculate the bitwise AND of the masks of these girls, the number of 1's in the binary representation of the resulting number is equal to the number of boys that are friends with each of the chosen girls, we add it to the number of chosen girls and we get the answer for this subset. Find the maximum answer between all subsets.

Complexity: O(2^PP)

E. Minesweeper

This problem can be solved using backtrack or DP Bitmask, I will explain the DP solution:

Let's add rows one by one. We represent a row using a mask (0 if its a mine, 1 if its a free cell).

In order to know which mask can be added as the current row, we need to know the masks of the 2 previous rows, and check that the last row can be placed between the current mask and the one before the last.

So we have dp[i][mask1][mask2] is the number of ways to set the first i rows, with the last 2 rows being mask1 and mask2. To calculate it, we loop through all valid masks for the new row and add dp[i + 1][mask2][newMask].

The only thing left is to write a function that takes 3 masks, and checks if the middle row does not violate any of the rules when placed between the other 2 masks.

Complexity: O(rc2^3c)

F. A Missing Problem in TCPC2017

There are many ways to solve this problem, either mark the available problems and then find the unmarked problem, or calculate the sum of the available problems and print n * (n + 1) / 2 - sum, or find the first i that is not equal to a[i] and print it.

Complexity: O(n)

G. Robots

Solution 1:

Sort the robots by x_i, and go through them in decreasing order. Simulate the first query step by step and store in a set the value of edges that this robot goes through. Now for each query, starting from the node that the previous query ends in, keep going up in the tree and deleting those edges from the set until every element in the set is less than x_i. After that, continue simulating the query going down step by step, adding the edges to the set.

Each edge will be added at most once to the set, and it gets deleted when it is larger than all x values left, so it won't be added to the set again.

Complexity: O(nlog(n))

Solution 2:

Sort the robots by x_i.

If a robot x_i and robot x_j (x_i < x_j) pass through a node during their movement, then every other robot x_k such that x_i ≤ x_k ≤ x_j will also pass through this node.

We can start a dfs traversal at node 1 and keep the range of robots that will pass through this node. Then, in each node, we go through the children, and for each one find the range of robots that will go to that child. And also find the range that will end up in this node and add them to the answer.

Complexity: O(n + qlog(q))

H. Buying Products

For each shop, take the two cheapest products, and add them to a set.

The answer is the sum of the cheapest k products in the set.

Complexity: O(nlog(n) + k)

I. A Movie in Byteland

First give each name (ltr and rtl) a number according to it's order lexicographically among all names. and also store for each name whether is has an 'm' or not.

Now we have n pairs of numbers and we need to find the longest increasing subsequence, where a pair (a, b) is bigger than another pair (c, d) if a > c and b > d. We also need to satisfy the rule that any two consecutive names exactly one of them has an 'm' in it.

To solve this problem, we sort the pairs by the first value, then we only need the subsequence to be increasing by the second value.

Use two segment trees, one for the pairs that have an 'm' in it, and one for the pairs that don't. The rest is just like the ordinary nlogn solution for LIS. The answer for the pair that has an 'm' is calculated using the segment tree that doesn't have an 'm' and so on.

Complexity: O(nlog(n))

J. The Volcano Eruption

Create a graph where each circle is a node, and any pair of intersecting circles have an edge between them.

Let's find the number of components that have at least once circle that intersects with each side of the street, this component will cut the street, so we must use a suit to pass it. Therefore the answer is the number of such components.

Complexity: O(n²)

K. Poor Ramzi

Let dp[l][r] be the number of sumindromes that can be achieved from the range [l, r].

To calculate this dp, iterate through all possible prefixes [l, i] and suffixes [j, r] such that i < j and sum(l..i) = sum(j...r) and add dp[i][j] to the answer.

Also add 1 to dp[l][r] to consider summing all the range into one integer.

Complexity: O(n⁴)

L. Eyb0ss

First, we can calculate the sum of maximums alone, and the sum of minimums alone, then subtract them.

How to find the sum of maximums?

Let's consider the linear version of the problem, given n integers, find the sum of maximum numbers in each range [l, r].

To solve this problem, we go through each number and find the number of ranges where this number is the maximum.

We can find the closest number x greater than it before it and the closest number y greater than it after it using a stack.

The current number is the maximum in all ranges that start after x and end before y. We add to the answer the current number multiplied by the number of these ranges.

Now, let's go back to the 2D version.

For each pair of rows r1 and r2 (r1 < r2), we want to calculate the sum of maximums in all rectangles that start at r1 and end at r2. For each column, only the maximum number in this column between r1 and r2 can be a possible maximum in the rectangle. So we find the maximum number in each column and store them in an array, then apply the linear version of the problem on this array.

Note: to simplify the implementation, you can first calculate the sum of maximums, then multiply all the numbers in the array by -1, then find the sum of maximums again and sum the two answers.

Complexity: O(n³)

A. Martadella Strikes Again

if R * R > 2 * r * r print 1, otherwise print 2

R and r should be long long or double to avoid overflow

C++ Code

B. Amer and Graphs

Since the edges are undirected ,we can store the edges {u, v} as (u ≤ v) for every edge (1 ≤ i ≤ n).

Let's assign a unique number for every unique edge in the array, then our problem will be reduced to :

Find the number of different segments of the array which have the exact same elements ( same frequencies as well for each element ).

This problem is a classic hashing problem that can be solved this way :

let's choose some random large prime numbers P and MOD ,for example P = 304933, MOD = 10⁹ + 7.

replace every element {x_i} from the array with P^x_i%MOD.

now the final problem is about finding different segments of the array which have the same sum value %MOD .

This solution will get "Wrong Answer", so you need to do a double-hashing in the same way using other numbers P₂, MOD₂

Time Complexity : O(n² * log(n)) .

C++ Code

C. Help Shahhoud

We greedily iterate from the sides and when two items need to be reversed we reverse the whole segment that contains them and add one to the final answer

If they can’t be equal even if we reverse them then it is impossible and answer = -1 .

We only need to keep a flag for the current state :

0 means the segment between the 2 pointers is not reversed.

1 means the segment between the 2 pointers is reversed.

C++ Code

D. Simplified 2048

The main idea is that we only need to keep track of the number of active cells and the last strictly increasing sequence of powers from right to left, this is because if we have a cell with number X and the cell to the right has number Y where Y > X , these two cells will never merge and therefore anything to the left of them won't add anything to the score so we don't need to keep track of them.

This leads to a DP Bitmask solution where we store the bitmask of available powers of 2 (they are guaranteed to be strictly increasing from right to left because we ignore any powers that aren't) and the number of active cells (free cells + number of bits in the mask).

If the current mask is msk and a 4 is generated, the new mask will become msk + 4 and ((msk)^(msk + 4)) - 4 will be added to the score.

When a 2 is generated, the new mask will become msk + 2 and ((msk)^(msk + 2)) - 2 will be added to the score.

The added score explained above is the score added from all the merge operations that will happen after adding the new number, not only the first one. Merging them all at once will not affect the final answer.

^ is the bitwise XOR operator.

C++ Code

E. Floods

The answer is the sum of areas of zero or more simple polygons that keep rainwater.

We will explain an easy way to find these polygons and then calculate their areas.

Look at the picture while reading for better understanding :

We will say that a point is important if it isn't underwater(red points in the picture ).

We can easily determine if the i - th point is important if it has the maximum value of y-coordinate from the first i points or the last N - i + 1 points of the polyline.

Any other point will have one or more points on it's left and one or more points on it's right with larger y-coordinate , so it will be underwater for sure (this point will not be important for us for now).

Now for every important point let us draw a horizontal line to the left (or to the right) to find the intersection point with some segment of the polyline (green points in the picture ).

We need to handle the 2 cases (when to draw a line to left and when to draw a line to the right).

The problem now is reduced to calculating the sum of areas of the resulting polygons.

Time Complexity : O(N)

C++ Code

F. Random Sort

let cnt[x] = number of occurences of x in the array

the answer is the multiplication of factorial$( cnt[x] )$

C++ Code

G. Weird Requirements

The problem asks you to make the minimum number of changes on the array to make GCD of all elements equals to X and LCM of all elements equals to Y.

First of all, let's count the number of elements that must be changed and call it C i.e. the elements where A_i isn't a multiple of X or a divisor of Y.

Note: the GCD of a group of numbers is the product of the common prime factors with the lowest power, and the LCM of a group of numbers is the product of all prime factors that appear in the numbers with the highest power.

There are 5 cases to handle :

1) Ans =  - 1: if ( Y isn't a multiple of X ) or ( N = 1 and X ≠ Y ).

2) Ans = 0: if C = 0 and GCD(A_i) = X and LCM(A_i) = Y
for all (1 ≤ i ≤ N)

3 and 4) Ans = 1: if C = 0 and there is an element A_i satisfies the following condition or C = 1 and the element that must be changed satisfies the following condition:

Let's first factorize both X and Y.

The element satisfies the condition if after deleting it, each prime factor that appears in X or Y, must satisfy the GCD OR the LCM rule from the note above in at least one of the remaining elements. This way, if either the LCM or the GCD rule is not satisfied, it can be fixed by changing the deleted element. We can't fix both the LCM and GCD rule for some prime factor by changing one number, unless the power of the prime factor is equal in both X and Y (this case should also be taken care of).

5) Ans = max(2, C): otherwise

C++ Code

H. Shahhoud the Chief Judge

First of all, you need to calculate this dp :

dp[u] = the number of paths that includes node u.

The solution has three cases:

case 1: Ans = 0

calculate S = sum W[u] * dp[u]

if S = 0 then the Ans = 0.

case 2: Ans = 1

a node u is a solution if and only if ( S mod dp[u] = 0 )

let x be the new weight of u

0 = S — dp[u] * W[u] + dp[u] * x

=>

x = W[u] — S / dp[u]

which is an integer

case 3: Ans = 2

for each pair (u,v) if gcd(dp[u],dp[v]) = 1 then they can be an answer because:

( let's say that x, y are their new weights respectively )

0 = S — dp[u] * W[u] + dp[u] * x — dp[v] * W[v] + dp[v] * y

=>

a*x + b*y = c therefore such x and y always exist

and the pair (u,v) always exists because:

let u be a node with biggest possible depth, hence u is a leaf, and its other

sibling is also a leaf (it has a sibling because the tree is binary, and its sibling doesn't have any children because u is of maximal depth)

now if we look at dp[u] and dp[parentOf(u)] :

dp[u] = (n-1) * 2 + 1 = n-1 path ends at u with two directions + one path from u to u

dp[parent] = 6n - 11

and we have gcd(2n - 1, 6n - 11) = gcd(2n - 1, 6n - 11 — 3 * (2n - 1) ) = gcd(2n - 1,  - 8) = 1

2n - 1 is odd, 8 can be only divided by 2.

C++ Code

I. Ildar Yalalov

The winning states are:

1) N is odd and sum(A_i) is odd.

2) N is even and at least one of sum(A_i) and min(A_i) is odd.

Let's look at the optimal strategy for Yalalov in the winning states:

1) N is odd. In this case, the number of stones removed in each step is always odd (either 1 or N). This means that the parity of the amount of stones left will flip in each move, so if sum(A_i) is odd, then there will always be an odd number of stones in Yalalov's turn, and since the losing state has an even number of stones, Yalalov will never reach the losing state so he wins. Otherwise, he will lose because he always ends up in a state with an even number of stones.

2) N is even and min(A_i) is odd. If sum(A_i) is odd, then the optimal strategy would be to use a move of the first type on the pile with the minimum number of stones, leaving an even number of second type moves, and an odd number of stones for the second player (losing position). The only way for the opponent to leave the losing position is to use a move of the second type, but you can negate the effect of it by using another move of the second type (there is an even number of them). When sum(A_i) is even, the best strategy is to use a second type move, leaving your opponent with an even number of stones, and and even number of second type moves, which is also a losing poition.

3) N is even and min(A_i) is even. If sum(A_i) is odd, the best strategy is to use first type moves, unless your opponent uses a second type move, you then also use a second type move to negate it's effect. If sum(A_i) is even, this is a losing state mentioned above.

C++ Code

J. Saeed and Folan

Since K is small, you can just simulate all the movements for both Saeed and Folan and add 1 to the answer when their positions are equal.

In each second, you need to first fix the direction of movement (if the person is currently at position L then the direction should be right, and if the person is currently at position R, the direction should be left), then move 1 step in the current direction.

After each step, check if the positions are equal.

Time Complexity : O(K)

C++ Code

K. Another Shortest Path Problem

The first thing to notice is that an undirected connected graph with N nodes and N edges has exactly one cycle and each node on this cycle can be a root of a tree.

Delete any edge from the cycle, let's say it connects nodes u and v with weight w.

The resulting graph is a tree. There are 3 cases for the shortest path between X and Y.

1) It does not pass through the deleted edge. So the shortest path is equal to the distance between X and Y in the resulting tree.

2) It passes through the deleted edge from u to v. So the shortest path is equal to the distance between X and u in the tree + the distance from v to Y in the tree + w.

3) It passes through the deleted edge from v to u. So the shortest path is equal to the distance between X and v in the tree + the distance from u to Y in the tree + w.

So, in each query, we take the minimum between the previous cases.

Note:

To find the shortest path between any two nodes in a tree:

First, consider any node to be the root, and calculate the distance from each node to the root in O(n) with a simple dfs.

Next, you can find the distance between any two nodes in a tree in O(log(n)) using LCA.

dist(a, b) = distToRoot[a] + distToRoot[b] - 2 * distToRoot[LCA(a, b)].

Another solution finds the cycle and finds the best way to go around the cycle using prefix sum for queries that are in different trees.

C++ Code for second solution

L. V--o_o--V

Coming Soon.

C++ Code

Hello Everyone!

Yesterday when I was participating virtually in a mashup contest I created, a weird thing happened.
When I submit a solution, sometimes it is considered "Out of Contest" (and shows that the contest has ended on the right) Even though the contest should still be running.
When I refresh the status page, the "out of contest" submission disappears and it shows the correct time (contest is still running). So I have to resubmit the solution several times until it shows up as a contest submission. I noticed that when it says that the contest has ended, it also says that manager mode is activated.

It seems that manager mode is being activated somehow when submitting a solution. Did anyone else have this problem?

I was looking at contest 200 div.1, but problem B has no statement, it shows an empty page with the following sentence: "Statement is not available".
What's wrong?

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.

I apologize for the mistake in the constraints of problem J, and for my bad English.

Problem A: Random Fightings:

DP[i] is the probability that mask i (i.e. the people whose indexes are equal to 1 in mask i) are still alive.

DP[2ⁿ - 1] = 1
For each mask, for every pair of alive gangsters (i, j), calculate the probability of gangster i dying in the next fight against gangster j, let us call it p, and add p * DP[mask] to DP[mask - 2ⁱ] (i.e. the same mask but with the i^th bit switched to 0).

How to calculate p?
p is the product of the probability of the j^th gangster killing the i^th one if they fight each other (A_ji) and the probability of having a match between them.

The number of possible matches for a mask is x * (x - 1) / 2 where x is the number of alive gangsters, therefore the probability of having a match between them is 2 / (x * (x - 1)).

Problem B: Rectangles:

You need to cover all x s and y s, therefore the rectangle should cover all points from (min_x, min_y) to (max_x, max_y).
The area is (max_x - min_x) * (max_y - min_y)
Complexity: O(n)

Problem C: Too many coins:

Sort the types of coins in decreasing order by the amount of each type (the product of the value of the type and the number of coins of this type), and if there is a tie the larger value comes first.
Then, start adding the types one by one until the sum is greater than or equal to M.
Complexity: O(ClogC)

Problem D: Card Game:

Binary search the answer, to check if it is possible to distribute the cards such that the maximum power is less than M, keep giving cards to the first player while his power is less than M, then move to the second player and so on. If at the end you were able to distribute all the cards, then it's possible.
Complexity: O(nlogn)

Problem E: Xortion:

a xor b$ is maximal when the i^th bit in a is not equal to the i^th bit in b.

Since , we should try to match each bit with it's opposite greedily starting with the most significant bit.

Build a trie that consists of the binary representation of each number, starting from the most significant bit.
For each query with number x, go through the trie matching the most significant bits first.

Problem F: Print mix strings:

Generate all possible strings:

void generate(int i,int j,string res)
{
     if (i==a.length() && j==b.length()) // no more letters left, add the string to the set of possible strings.
         s.insert(res);
     else
     {
         if (i<a.length())
             generate(i+1,j,res+a[i]); // add a letter from string 'a'
         if (j<b.length())
             generate(i,j+1,res+b[j]); // add a letter from string 'b'
     }
}
  

Problem G: Count mix strings:

The resulting string will have length n + m, and you want to fill it with two types of letters, letters from the first string, and letters from the second string. You can consider letters from the same type identical, because there is only one way for the relative order of letters from the same type (they should remain in the same order as the original string).
So we need to choose n indexes from the n + m indexes available, and fill them with letters from the first string, and fill the rest with letters from the second string. Therefore the answer is:

You can precalculate all i! mod 10⁹ + 7 for 1 ≤ i ≤ 20000 and use modular multiplicative inverse to find the answer:
(((fact[n + m] * inv(fact[n]))%MOD) * inv(fact[m]))%MOD where fact[x] = x! mod 10⁹ + 7 and inv(x) is the modular multiplicative inverse of x.

Problem H: Tourists:

We need to find a solution for the equation: x * n1 + y * n2 = n such that x * c1 + y * c2 is minimum.
The equation can be solved only when n is divisible by gcd(n1, n2).
We can use the extended euclidean algorithm to find a solution to the equation a * n1 + b * n2 = gcd(n1, n2), if we multiply this equation by n / gcd(n1, n2), we get: (a * (n / gcd(n1, n2))) * n1 + (b * (n / gcd(n1, n2))) * n2 = n
Therefore: x = a * (n / gcd(n1, n2)) , y = b * (n / gcd(n1, n2)).
After finding this solution, the other solutions would be:
X = x - r * (n2 / gcd(n1, n2)) , Y = y + r * (n1 / gcd(n1, n2))
If the cost per passenger of the first boat is less than the cost per passenger for the second boat, we should try to maximize X, while keeping Y positive. to do that we can find the minimum r which makes Y positive by binary search.
Otherwise we look for the maximum r which makes X positive, also with binary search.

Problem I: Teleportia:

Build a directed graph of n + 1 nodes: The stations, the starting and the ending points. The distance between node A and node B is the manhattan distance between the 2 points, or min(2, manhattan distance) if A, B are stations, and B is a target of A. After that, Apply Dijkstra from the starting point to get the answer.
Complexity: O(n²log(n))

Problem J: Palprime:

between 1 and 2²¹ are about 2¹⁰ binary palindromes, generate all of them, store the ones that are prime numbers in a set, then answer each test case with binary search.

Hello!

On Friday, 12 February 2016, an online mirror of the ACM Damascus Collegiate Programming Contest 2015 will be held in Codeforces Gym.

The problems were prepared by : Pepe.Chess, majd.gda1, Jarrar, Alaa Jarad, Feras Al-Kassar, Mohammad Asaad, Mousaab Orabi.

You will be given 5 hours to solve the problems.

The difficulty will be similar to a div2 round.

Good Luck and have fun!

UPD: The contest will start in 30 minutes

Why does the registration end too early for Round 338? is it a bug?

Note: All complexities mentioned in this editorial are per test case.

A: Arcade Game

Let perm be the number of permutations for the digits of n.
First, sort all these permutations in decreasing order and give each permutation a rank (0 is the largest permutation, 1 is the second largest and so on).
ans[0] = 0


find the rank of n and print it's value from the array.

Note: the relation mentioned above can be reduced to:

Which could be written as (to avoid overflow):

Complexity: O(rank)

B: Unlucky Teacher

There are two ways for an answer to a question to be unique:
1) this question was answered correctly in one of the papers.
2) this question was answered incorrectly for three different choices.
So, for every question, we maintain a set of the possible answers for this question. Initially, the set of every question is {A, B, C, D} , when we get a wrong answer for this question, we remove that answer from the set. When we get a correct answer for this question, we remove all the answers except this one from the set.
Now, for every question, if the set contains one answer, print it, otherwise print '?'.
Complexity: O(MQ).

C: Connecting Graph

In this solution, I am going to use a more basic version of DSU, which is storing for each component all the elements that it includes, and merging two components is done by choosing the smaller component (i.e. the one with a smaller number of elements). And then moving its elements one by one to the other (big) component.

Solution:

We are going to use a DSU that has two kinds of elements, Nodes and type B Queries.

In the beginning, each component has a single node and all the queries of type B that involve it.

Then let’s process the queries of type A in their given order, for each query we’ll merge components of u, v using the mentioned above method, but for each type B Query element we have to cases:

1) This current type A query is the earliest query which connects the nodes in Query B. Then both of its nodes will belong to one component after merging, (it can be checked in O(1)), thus this Type B query is answered, we’ll store it’s answer in some array and then delete it from the component.

2) Its nodes aren’t connected yet, so we should add it normally to the component.

Complexity: O((N + Q)log(N + Q))

D: Frozen Rivers

Traverse the tree using DFS while storing the time needed to reach each node in an array, let us call it T.
T[1] = 1
If we are in node v:
1) we find the length of the shortest edge from v to one of it's sons, let us call it shortest.
2) we go through every son u_i of v, T[u_i] = T[v] + shortest + (len[v][u_i] - shortest) * 2 (since the water will flow for shortest seconds at a rate of 1 unit/s. and then it will slow down to 0.5 unit/s for the rest of the distance).
Now, we sort the leaves of the tree by the time needed to reach each of them, and answer the queries by binary search or 2-pointers.
Complexity: O(nlog(n))

E: Palmyra

Note:
1) A number L ends in x trailing zeros when written in base-6, if it could be written as:
L = 6^x * h (h is a number that is not divisible by 6)
L = 2^x * 3^x * h
2) If a number H can be written as H = 2^a * 3^b * h , H will have min(a, b) trailing zeros when written in base-6.

In this problem , we need to maximize x which can be done by DP:
DP[i][j][k] is the maximum x such that there is a path that starts in (1,1) and ends in (i,j) and the product of the numbers along the path is divisible by 2^x * 3^k
DP[i][j][k] = max(dp[i - 1][j][k - n3], dp[i][j - 1][k - n3]) + n2
Where n2, n3 are the number of times the power of the current stone can be divided by 2,3 respectively.
The answer is the maximum of min(k, dp[n][m][k]) for all k

Complexity:
The length of the path is n + m - 1
Each stone power can be divided by 3 at most log₃(a[i][j]) times.
So the maximum k is log₃(max(a[i][j])) * (n + m - 1)
Total Complexity: O(nm(n + m)log₃(max(a[i][j])))

F: Geometry

If H = W the shape is a square, otherwise it's a rectangle
Complexity: O(1)

G: It is all about wisdom

We can find the minimum wisdom value needed to go from 1 to N with cost <K by binary search.

To check if a wisdom value x is enough to go from 1 to N with cost <K, we can use dijkstra by considering edges that need wisdom value  ≤ x.
Total Complexity: O(mlog(n)log(m))

H: Tonight Dinner

1) There is always a way to assign seats for the 2 tables without having any intersections between paths, by just reverse the order of the guests in the seats.

The problem is equivalent to given 2 circular permutations, determine the least number of swaps between adjacent elements to turn one permutation into the reverse of the other.

There are at least 2 adjacent elements with crossing paths. If A, B are 2 not adjacent corners and their paths are crossing then there is a corner C between them where its path intersects with A or with B.

We can remove one intersection by swapping A and B.

To calculate the number of swaps of adjacent elements to turn sequence A to sequence B, you can try all rotations of B with A.

We can assume without loss of generality that A is the first permutation (1234…) then we can define displacement vector of B with A as V[i] = B[i]–i

Then count the crosses between all pairs by comparing the old and new place for each guest (if guest g₁ was right to guest g₂ and after the movement he is on the left, or vice versa, then there is a crossing)

To handle circular movement, try all rotations of vector V[i]

print the minimum number of crossings.

Complexity: O(n⁴)

I: Salem

Go through all pairs of integers, convert them to binary, and calculate the hamming distance between them, and return the maximum.
Calculating the hamming distance between x and y:

int dist=0;
while(x>0 && y>0)  
{
    if (x%2!=y%2) dist++;
    x/=2,y/=2;
}

Or you can count the number of bits in x xor y for a shorter code:
dist=__builtin_popcount(x^y)

Complexity: O(n²log(n))

J: Game

Observation: After every move, the length of the string is halved. Therefore, after log(n) moves, the game will end.
We can try all possible moves. A state with string s is called winning if one of the following is true:
1) |s| = 1, s[0] is a vowel, and it's Salah's turn.
2) |s| = 1, s[0] is not a vowel, and it's Marzo's turn.
3) |s| > 1 and one of the 2 possible moves leads to a losing state.

If the initial string is a winning state, Salah wins, otherwise Marzo wins.
The complexity of this solution can be proved to be O(nlog(n)) (n is the length of the initial string)

Proof:
For each state with string s, we need O(|s|) to get s1, s2 (the result of applying LEFT and RIGHT moves on string s respectively)
Let f(i) be the number of strings(states) we might end up with after finishing i moves. f(i) = 2ⁱ
Let g(i) be the length of the string we end up with after finishing i moves.
The total complexity is

K: PhD Math

First calculate the first n decimal digits of and store them in an array s
Let DP[i][j] be the number of substrings of s that ends at i and the value of this substring mod p = j.
If we have a substring that ends at i - 1 and it's value mod p = j then we can extend it to i , and the value mod p will become:
(j * 10 + s[i])modp
So we add the value of DP[i - 1][j] to DP[i][(j * 10 + s[i])%p]
and since we can start a new substring at i , we add 1 to DP[i][s[i]%p]
The answer is:

In order to use less memory, we can notice that every value in DP[i] depends only on some values from DP[i - 1] , so we only store DP[i] and DP[i - 1]

Complexity: O(n * p)

L: Candy Jars

Notes:
1) If all jars have 1 to N - 1 candies, that is a losing state.

2) If there is at least one jar that has N to N(N - 1) candies, that is a wining state.

3) If all jars have N(N - 1) + 1 to N(N - 1) + (N - 1) candies that is a losing state because any move will put N to N(N - 1) candies in one jar.

4) Adding N(N - 1) candies will not change the state.

So:

If candies c in all jars satisfy 1 ≤ c%N(N - 1) < N then this is a losing state (print Bob) else it is a wining state (print Alice)

Complexity: O(n)

M: Building Force Fields

After sorting all points by x coordinates.

It’s easy to show that optimal polyline for a group is the upper part of a convex hull (i.e. the upper polyline that starts from earliest x coordinate in the convex hull to the latest x coordinate).

So the optimal solution should divide consecutive points into groups after sorting.

If we can calculate the cost of creating a group from point i to j let’s name it C(i, j).

The problem is reduced to a classical DP problem.

DP[x] = min(DP[i] + C(i + 1, x)) : i < x - 1

Where DP[i] is the least cost to solve the problem for the first i points.

How to calculate C(j, i) ?

For each element i, start from i and go backwards while maintaining a stack that includes the points of the polyline, using the classic convex hull algorithm.

Total Complexity O(n²).

Hello!

On Sunday, 15 November 2015, 08:00:00 GMT , an online mirror of the ACM Egyptian Collegiate Programming Contest 2015 will be held in Codeforces Gym.

The problems were prepared by :
m.radwan, Alex7, amrSamir, nnahas, muaz-32, Jarrar, ahmad_mamdouh,Madhat Alsoos, Noor Alasadi, Islam Diaa, Alhussain Aly.

You will be given 5 hours to solve the problems.

The problems vary in difficulty and need a wide range of solving techniques, so I strongly recommend to participate in this contest.

Good Luck and have fun!

UPD: The contest has ended
Any feedback about the contest is appreciated.

When I submit a solution to a problem outside a contest, usually I can see the test cases, if I press on the submission number, however, long test cases are not shown complete, is there any way I can see the full test case?