Here you can find solutions to the problems from the past round. Editorial for Problem D (Div 1) was prepared by sdya.
Division 2, problem A
In this problem one could transform all letters in both strings to lower case and then compare the strings lexicographically.
Division 2, problem B
One can notice that if we want to divide a square into two equal parts, then the cutting line should pass through the center of our square. Thus, if the marked cell contains the center of the square, then we can’t make a cut, otherwise we can. Here is the code which solves the problem:
scanf("%d%d%d", &n, &x, &y);
n /= 2;
if ((x == n || x == n + 1) && (y == n || y == n + 1)) printf("NO\n"); else printf("YES\n");
Division 2, problem C (Division 1, problem A)
It is easy to see that in order to maximize the sum of squares, one should make all numbers except the first one equal to 1 and maximize the first number. Keeping this in mind we only need to check whether the given value of y is large enough to satisfy a restriction that all n numbers are positive. If y is not to small, then all we need is to ensure that x ≤ 1 + 1 + … + (y - (n - 1))2
Division 2, Problem D (Divison 1, problem B)
Let’s create an array used[], j-th element of which will be the index of the last number from the input, which is divisible by j. Then for each query we’ll iterate over all divisors of xi and for each k, which divides xi we’ll check whether it is “unique”. After that we’ll update used[k].
Division 2, Problem E (Division 1, problem C)
This problem has many different approaches. One of them uses the fact that the overall number of possible inputs is small and it is possible to compute the answer manually for all of them. One could also write a brute-force with a few optimizations, which works even without a precalc.
However, the major part of all solutions involved dynamic programming with bitmasks. The solution below was described by Zlobober.
Instead of counting the maximal number of free cells, we’ll count the minimal number of occupied cells. We’ll assume that the number of rows is not greater than 6 (otherwise we can rotate the board).
Let D[k][pmask][mask] be the minimal number of occupied cells in the first k columns with the restrictions that the k-th column is described by pmask (ones correspond to occupied cells and zeroes correspond to free cells) and k+1-st column is described by mask. To make a transition from D[k-1][*][*] we can iterate over all possible masks for the k-1-st column, check whether we can distribute spiders in kth column knowing the masks for k+1-st and k-1-st columns and find the minimal value of D[k-1][*][pmask] for all such masks.
The overall complexity is O(n*23m), n > m.
Division 1, Problem D
One can notice that if m = 1 then the answer is kn, because all colorings are possible.
Now we’ll assume that m > 1. Let’s look on the first column of the board (i.e. the vertical cut will be made right next to the first column). Suppose there are x distinct colors in this column. Then in the rest of the board there are also x colors. If we move the vertical line by one unit to the right, the number of different colors to the left of it will not decrease and the number of colors to the right of it won’t increase. It means that the number of different colors in both parts of the board will be also x. We can repeat this process until the line reaches the rightmost column, which means that the number of distinct colors in it is also x. It is easy to see that we can only use colors which belong to the intersection of sets of colors in the leftmost and rightmost columns in the rest of the board.
Let’s iterate over all values of x and y, where x is the number of colors in the leftmost column and y is the number of elements in intersection of sets of colors in the rightmost and leftmost columns. It is easy to see that x is limited by the number of rows in the board and y can’t be greater than x. Let’s find the answer for all such pairs of x and y and at the end we’ll add them up together.
Suppose x and y are fixed. We first need to choose (2x - y) colors from the given k colors, which we will use, which means that the answer for will be multiplied by C(k, 2x — y). After that we’ll choose (x-y) unique colors which will be used in the first column, which means that the answer will be also multiplied by C(2x-y, x-y). Then we’ll choose x-y colors for the rightmost column and multiply the answer by C(x, x-y). Now all we need to know is how many ways of coloring n cells into x colors are there. We’ll use a dynamic programming approach to solve this sub-problem.
Let d[i][j] be the number of ways to color a rectangle of unit width and length i into colors, numerated from 1 to j with the following restriction: if a < b then the first appearence of color a in the rectangle will be before the first appearence of color b.
Then we can calculate this function using the following recurrence:
d[i][j] = j * d[i — 1][j] + d[i — 1][j — 1].
After we finish calculating d[i][j], we need to multiply the answer by d[n][x]2 (to color the first and the last columns). Now we need to notice that we can reorder all colors in the first and the last columns in arbitrary way, which means that the answer should be multiplied by (x!)2. Finally, we need to multiply the answer by yn(m-2), which correspond to coloring the rest of our board.
Here is the code, which solves the problem for the given values of x and y:
long long ans=0;
for (int y=0; y<=n; y++){
long long cur=powmod(y,n*(m-2));
for (int x=y; x<=n; x++)
if (2*x-y<=k)
{
long long tek=cnk[2*x-y];
tek*=cnn[2*x-y][x-y], tek%=mod;
tek*=cnn[x][x-y], tek%=mod;
tek*=d[n][x], tek%=mod;
tek*=d[n][x], tek%=mod;
tek*=f[x], tek%=mod;
tek*=f[x], tek%=mod;
tek*=cur;
ans+=tek;
ans%=mod;
}
}
cout<<ans<<endl;
Some contestants had problems with time limit, because of calculation of C(N,K). One can notice that we won’t need more than 2000 colors, which reduces the time significantly. Author’s solution worked less than 200ms with the time-limit of 5s.
Division 1, Problem E
Let the length of the maximal path be S. First, we’ll estimate the value of S without specifying the longest path itself.
Let’s color our board into a chess-coloring. Obviously, each two neighboring cells in the path will have different color. Keeping this in mind we can make some estimation on the value of S. For example, if there are 4 white cells and 5 black cells on the board and we know that both starting and ending cells are white, than the length of the path can’t be greater than 7, because white and black cells must alternate in the path. We can write a simple function which calculates the maximal value of S using only the fact described above. Here, n and m are the dimensions of the board, (sx, sy) is the starting cell and (fx, fy) is the ending cell.
int fnd_ans(int n,int m,int sx,int sy,int fx,int fy){
int col1=((sx+sy+1)%2); //color of the start cell
int col2=((fx+fy+1)%2); //color of the finish cell
int cntb=(n*m+1)/2; //the number of black cells
int cntw=(n*m)/2; //the number of white cells
if (col1==1&&col2==1)
return cntb*2-1;
if (col1==1&&col2==0)
return cntw*2;
if (col1==0&&col2==1)
return cntw*2;
if (col1==0&&col2==0)
return 2*cntw-1;
}
It appears that for the constraints mentioned in the statement, this theoretical bound for S is always achievable. All we need is to find the path of the length S. Author solution divides the board into 5 pieces and solves the problem for each piece separately.
Let’s divide the board into 5 parts as it was shown on the first picture. We’ll assume that the relative location of the starting and ending cells is the same as on the picture. In each part we’ll try to build a longest path which completely belongs to it. For the first part we’ll try to build a path from the upper-right corner to the upper-left corner. Similar rules will hold for all other parts (see the picture above for further clarification). Paths can be different for different boards, but they will have similar structure. One can notice that there are only two types of paths (with respect to rotations of the board): the one which starts at the upper-left corner and ends at the bottom-right corner and the one which starts at the upper-left corner and ends at the upper-right corner. Now we can write down an algorithm:
1) Divide the board into 5 parts.
2) Find the longest path in each of the parts.
3) Check if the total length is equal to S.
4) If the above is false, then rotate or reflect the board and continue to the step 1.
In order to find the longest path in a particular part, one can either consequently move through all rows of the part or through all its columns.
This solution gives correct answers for all 4 ≤ n, m ≤ 20. All possible cases of parity of each part are feasible within those constraints, which means that the solution will work for all boards, including ones with n > 20 or m > 20. The overall complexity of described algorithm is O(N*M).
Can you please provide a proof that in Div 2 B, a line must cross the central square ?
In case, anybody wants a more detailed analysis of Div 2 C, I have written a post about it here.
worst editorial ever for Div2 D
I think so
Yes I think the editorial for Div2 D Petya and Divisors, is not clear enough, So I will try to explain it a bit for anyone who comes after me.
Since the elements are only in range 1 to 100000, the possible divisors will be in that range, we can create an array used[] , where
used[j]will tell what was the last index when we encountered a X with j as one of its divisors.We can initialize used[] with -1.
Now for an Xi, we can iterate over all its divisors, for a divisor d, we can check that if
used[d]==-1(not encountered this divisor until now) orused[d]<i-y(it was last encountered outside of [x-1,x-y] range), we need to count these cases. Also take care of cases when y==0.After that, we will update used[d]=idx
code=> https://codeforces.net/contest/111/submission/82272791
Why this code is not giving TLE O(Nsqrt(N)) ?
because n=1e5 so nsqrt(n)=1e7.5 which can be done easily.Correct me if i am wrong.
Thanks. good editorial
112A — Petya and Strings I can't solve this problem. Does anyone help me?
just use python and then you can easily compare them by doing something like this: if s.lower > s1.lower: print(1)