Good Morning, Codeforces!
Analyzing the task C (Div1), E (div2) I came to the conclusion that the author’s solution is wrong, so I bring to you all a huge apology.
However it turned out all pretests were correct and there are only a few number of incorrect hacks (only 3). After discussing the situation with MikeMirzayanov we made this decision:
Problem E almost do not effect on contest results for Div2 participants (there are only a few number of submits and no hacks), so the contest will be rated for Div2 participants.
The contest will be rated for Div1 participants, only if this problem have right and fast solution. I wasted all todays night (or morning) finding this solution. Therefore I propose to solve this problem by the community (if it’s possible). If during the day, i.e. 24 hours after publishing this post, one cannot find solution, Div1 competition will be considered unrated.
Once again I bring you my apologies for this mistake. I hope that we will be able to master this problem together. Feel free to write all your ideas in this post, even some wrong idea may hint at the right solution. We would be very grateful to everyone who will take part in solving of that problem.
Note that this problem appeared in problemset. All tests are correct and you may try to solve it.
UPD: 24 hours have passed. Unfortunately, no one has written the correct solution, or close to it. Div1 round is declared unrated. Many thanks to all those who put their efforts and tried to solve this problem.
Best regards, Gerald Agapov.
Добрый день, Codeforces!
Меня интересует, умеет ли кто-нибудь считать такую сумму 
. Или такую сумму (они друг через друга выражаются) 
(деление целочисленное).
Буду очень признателен любым методам подсчета быстрее чем линия (или около-линия).
Good Day, Codeforces!
Remember, that at 17:15 the final of the Open Moscow Programming Championship By CROC will start.
As usual anyone wishing to participate in this round can compete in it out of competition. But as this competition is quite complex, it will be rated only for participants from Div.1.
Note that this competition is closely connected with onsite competition in Moscow. So the starting time can be shifted. Watch closely for changes in the schedule.
Good day, Codeforces!
Today at 19:00 the Round 1 of the Open Moscow Programming Championship By CROC will start.
This is usual two-hour Codeforces round with hacks and decreasing values of problems. Everybody, who passed Qualification Round and registered for today’s round, has advanced to Round 1. The remain participants are allowed to participate in this Round out of competition. Round will be rated for everyone as usual. Contestants who gain a score equal to the 300-th place finisher score or greater will advance to the Round 2 (also you need to gain positive score).
You will find a few problems, roughly ordered by the increasing complexity. Score distribution is standard (500-1000-1500-2000-2500). During the Round the problems are judged only on pretests and system testing will take place after the end of the Round. The pretests do not cover all possible cases of input data, test your programs carefully!
Before the end of the round it is strictly forbidden to publish the problem statements/solutions/any thoughts and ideas about them elsewhere. It is forbidden to talk about the problems, discuss the statements and so on. Be honest and let the best men make it into Round 2. When the Round is over, you can discuss the problems and solutions.
It seems that this Round could be a bit hard for Div2 participants. Don’t forget that rating will be calculated only for participants, who make at least one submit.
In today’s round preparation take part: Ripatti, havaliza, HamedSaleh, RAD, Gerald, MikeMirzayanov, Delinur. A huge thank you to all of them for their work!
Good round to everybody!
152A - Marks
In this problem you should do exactly what is written in the statement. Here is rough code of solution:
for (int i = 0; i < n; ++i){
bool wasBest = false;
for(int j = 0; j < m; ++j){
bool isBest = true;
for(int k = 0; k < n; ++k)
if(a[k][j] > a[i][j])
isBest = false;
if(isBest)
wasBest = true;
}
if(wasBest)
ans++;
}
152B - Steps
Let’s find a formula for the position (x, y) and vector (dx, dy), how many steps to stop the boy can do. You should use “almost” binary search, for example, see the code written by RAD.
for (long long cof = 1100000000; cof; cof /= 2)
while (onField(xc + cof * dx, yc + cof * dy)) {
xc = xc + cof * dx;
yc = yc + cof * dy;
ans += cof;
}
152C - Pocket Book
In this task, it was necessary to understand that in position 1 Vasya can get any name of a special form. More exactly, it’s the name of form s = s1 s2 s3 s4 … sm, where s1 — the first letter of any of the names, s2 — the second letter of any of the names, … sm — m-th letter of any of the names. Then the answer to the problem is the product of cnti (1 ≤ i ≤ m), where cnti is a number of different letters in the names placed in position i.
152D - Frames
It was necessary to understand if there are two borders or not.
Let’s distinguish those x — and y-coordinates, in which there are at least 3 consecutive symbols ‘#’, becouse the length of each border is no less then 3. It is clear that the coordinates of the corners of borders should be chosen only from those selected x and y. In general, the various selected x no more then 4 and various selected y no more then 4.
Except that case when the height or width of the first border is 3, and length of the second side of this border is more than 3, and one side of the second border fills a part of the inside first at least.
For example:
####### ####### ####### #.....# #######
The first border:
####### #.....# ####### ....... .......
The second border:
....... ####### #.....# #.....# #######
There are 7 different y-coordinates in the example.
Carefully processed these cases separately, it is quite simple. (Let’s choose 4 y-coordinates: minimum, maximum, second minimum and second maximum).
Otherwise, if the amount selected x — and y-coordinates no more then 4, then let’s choose opposite corners of the first and second borders and verify that the selected borders — the correct borders and there are no other characters ‘#’. Checking is carried out at O(n + m) or O(1) (using partial sums).
152E - Garden
The solution of this problem is based on dynamic programming. dp[mask][v] — the value of the minimum correct concrete cover, if we consider as important elements only elements of the mask mask, and there are additionally covered the vertex v = (i, j) of the field.
There are two types of transfers.
First of all we can, as if to cut coverage on the vertex v. Then you need to go through subpattern of vertex submask, which will go to the left coverage and make an optimizing transfer. Update dp[mask][v] with the value dp[submask][v] + dp[mask ^ submask][v] - cost(v).
Second, perhaps in the vertex v in the optimal coverage mask mask, which covers the vertex v, you can not make the cut separating the set of vertices. In this case, this vertex forms something a kind of «tail». And there a vertex u exists, on which we can make the cut, with the whole shortest path from a vertex u to v belongs to the optimal coverage. Let’s precalculate the shortest paths between all pairs of cells. Now to make this transition, we should count the value of dynamics dp[mask][v] for all vertices v only on the basis of the first transition. Now you can make the second transition. For all u, dp[mask][v], update the value of dp[mask][u] + dist(v, u) - cost(u).
Let’s process separately state in which exactly one bit in the mask, and the vertex which corresponding to this bit is equal to v. In this case the answer is equal to cost(v), of course.
Thus, each solution is obtained for the O(min(3k· n· m, 2k· (n· m)2)).
Good day, friends!
UPD: Problem analysis
the answer is "YES" else "NO". Let's generate the weighted directed graph of all ramps. The graphs' vertexes are the important points on the line Ox, there are points: 0, L, xi - pi, xi + di. The graphs' edges are the possible ramp jumps: transfer from point xi - pi to point xi + di or transfer from vertex in neighboring vertexes (neighboring means that we get the next and previous important points on the line). The weights of these edges are correspondingly pi + ti and xv + 1 - xv, xv - xv - 1. We must note that in the transfers we can't get in the negative part of Ox, and we must delete this transfers.
Then we must find and output the shortest path in this graph from vertex 0 to L. This can be done, for example, with Dijkstra's algorithm for the sparse graphs.
In this problem we must find the minimum spanning tree, in which the half of edges are marked with letter 'S'.
There are n - 1 edges in this tree, because of it if n is even then the answer is "-1".
Let's delete from the given graph all S-edges. And there are cnt components in obtained graph. For making this graph be connected we must add cnt - 1 edges or more, that's why if cnt - 1 > (n - 1) / 2 the answer is "-1". Then we find cnt - 1 S-edges, that we must add to the graph, so that it become connected. If cnt - 1 < (n - 1) / 2 then we will try to add in this set of edges another S-edges, so that the S-edges don't make circle. We must do all of this analogically to Kruskal's algorithm of finding a minimum spanning tree. If we could get a set of S-edges of (n - 1) / 2 elements, that there are exactly cnt - 1 edges and no S-circles, then the answer exists, Then we must add to this set (n - 1) / 2 M-edges, that forms with our set of edges the minimum spanning tree, it must be done analogically with Kruskal's algorithm.
- s = f, ans = t.
- s < f, we must find the smallest non-negative k such, that t ≤ (s - 1) + 2(m - 1)k. ans = s - 1 + 2(m - 1)k + (f - s).
- s > f, similarly, we must find the smallest non-negative k such, that t ≤ 2(m - 1) - (s - 1) + 2(m - 1)k. ans = 2(m - 1) - (s - 1) + 2(m - 1)k + (s - f).
Hello everybody! My name is Gerald Agapov. I study at Saratov State University. Today I present you the set of, I hope interesting, problems. Good luck to all!
- ГМТ - угол, в том случае, если проекции их на плоскость Oxy есть вектора линейно независимые. Получить этот угол достаточно просто. Вершина его будет очевидно в точке старта ДравДэ, один из образующих лучей будет сонаправлен с проекцией вектора скорости самолета, другой просто вычисляется
Az + Vz * tv + Uz * tu = 0
Ax + Vx * tv + Ux* tu = Bx
Ay + Vy * tv + Uy * tu = By
где A стартовая точка, а B та точка куда ДравДэ приземлится. Подставив в качестве tv например 1 можно легко вычислить t2 из первого уравнения и далее найти точку B. Это и будет точка на втором луче. - ГМТ - луч или прямая, в том случае если проекции векторов скоростей линейно зависимы, луч когда ветер дует не слишком сильно =).