Auto comment: topic has been updated by wrg0ababd (previous revision, new revision, compare).

И почему ваше решение по G должно работать 6.5 секунд? А мое 26623331 с таким же количеством вершин и ребер — нет?

UPD: выложите, пожалуйста, код авторского решения.

Доказательство G в студию? На опенкапе была похожая задача (была ли эта придумана после той?), но ее решение оказалось кукареканьем.

UPD Со ссылкой на викиконспекты стало понятно, откуда это берется. Страно, что эта полезная информация раньше была не сильно известна. Впрочем, для задачи с опенкапа эта оценка совершенно не работает, но там и тесты были с большим временем работы постфактум сделаны.

I think Problem D constraints are very bad, because O((n + m) * n ^ 2 * k) solutions passed, but there is O((n + m) * n * k) solution...

and using intervals instead of segments

What is the difference between intervals and segments?

Можно ли как-то оценить, какой эпсилон нужен в C? Кроме как методом тыка, имея целочисленное решение

Откуда такая асимптотика в D? Перебираем за n*n*2*k(левая граница, правая граница, в левой или в правой границе мы сейчас, сколько ходов осталось) все отрезки. Переходы из каждого отрезка находим за n. В итоге O(n^3*k)

For Problem C, making the value of eps more precise changes verdict from WA to AC. But, aren't we supposed to take any difference < 1e-6 as zero, as it is mentioned in the problem statement as well, that even the judge will compare the answers with error limit = 1e-6?

I thought that there has to be an equal number of vertices instead of leaves in E. The renaming of "leaves" and "vertices not being leaves" to "offices" and "departments" was strange. ;_;

I tried the following for problem C:

1. Find a time Ti for each mice i in which the mice will be in the maze, using ternary search.
2. Use binary search to find the lower and upper bound of the time, using Ti
3. Do the intersection of the bounds and take the smallest time.

But I got WA on test 30 because of the precision error. Can you find where I did the mistake? and How to find a good EPS which will meet the requirement.

Submission: http://mirror.codeforces.com/contest/793/submission/26625111

При n=1 и m=1, как может гарантироватся что символы «S» и «T» встречаются ровно по одному разу?

here is my Solution for B i used almost exactly what you mentioned first (naive recursive). passed pretests but got TLE on test 10.

adding the below code passes test 10 but TLE on 11. any help please?

if(turns==2 && (dir=='u' || dir=='d') && y!=sj) return;
if(turns==2 && (dir=='l' || dir=='r') && x!=si) return;

It seems to me C is in something easier to solve this way(sorry if someone have alredy written about this): We used bisection method for minimal time calculate. Let start with L=0, R=10^11. Let us now be at time M = (L + R) / 2. Then it is easy to calculate for every mouse her coordinates Xi and Yi. Obviously when Yi >= Y2 and her y-speed >= 0, we must move the right border, since she will never be inside a rectangle. Similarly examine the three other cases:

Yi <= Y1 and y-speed <= 0

Xi <= X1 and x-speed <= 0

Xi >= X2 and x-speed >= 0

And we must move the right border, if all mouses are in the rectangle. If these conditions are not met, move the left border. When we have done all iterations, we have right border as an answer. We will get it, if all mouses were in the rectangle at the same time. Else deduce -1

B has easier solution. Paint crosses on S and T with different colors (say 's' and 't'), then examine each line and each column if any of them contains /S\.*T/ or /T\.*S/ (c++26615732).

Why do you give him so many downvotes?After all he prepared the round and posted the editorial!

The post is hidden because of too negative feedback, click here to view it

Same code shows two different verdict why?

Accepted code: Wrong Answer code:

For problem B, I got WA on test 62. Here is my submission: 26615111

Can anybody help me ? What's wrong in my code ?

Update: I have found my bug. I was using visited array as vis[row][col][mov], using visvis[row][col][dir][mov] got AC. Here is my AC code: 26632674

I have written dfs solution for Problem B but it has got WA for test case 24.

#include <bits/stdc++.h>
using namespace std;
string s[1000];
bool vis[1000][1000][4];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int n,m,sx,sy;
bool is_turn(int px,int py,int tx,int ty){
	if(abs(px-tx)==1&&abs(py-ty)==1)
		return true;
	return false;
}
bool is_valid(int x,int y,int i){
	if(x==n||y==m||y<0||x<0)
		return false;
	if((s[x][y]=='.'||s[x][y]=='T')&&!vis[x][y][i])
		return true;
	return false;
}
bool dfs(int px,int py,int x,int y,int t,int in){
	if(t>2){
		return false;
	}
	if(s[x][y]=='T')
		return true;
	vis[x][y][in]=true;
	bool tr=false;
	for(int i=0;i<4;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(is_valid(tx,ty,i)){
			if(is_turn(px,py,tx,ty))
			tr|=dfs(x,y,tx,ty,t+1,i);
		    else
		    	tr|=dfs(x,y,tx,ty,t,i);
		}
	}
	return tr;
}
int main(){
    scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		cin>>s[i];
	}
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) for(int k=0;k<4;k++) vis[i][j][k]=false;
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(s[i][j]=='S'){sx=i;sy=j;}
	bool res=false;
	for(int i=0;i<4;i++){
		if(is_valid(sx+dx[i],sy+dy[i],i)) res|=dfs(sx,sy,sx+dx[i],sy+dy[i],0,i);
	}
	if(res)
		puts("YES");
	else
		puts("NO");

	return 0;
}

С из разряда "сначала подумай, потом пиши". Я вот не догадался решать отдельно для x и y, а бросился решать в 2D.

I don't like this round...

In problem B, I used DP to get the minimum number of direction changes to reach 'T' from a given cell.

The DP state is: (row, column, current direction).

If the starting cell can reach 'T' in 2 direction changes or less, then the answer is YES.

This code gives me WA.

Is there a logical problem with my method?

How can problem B be solved just using 3(currx,curry,dir) states in case of bfs whereas for recursive dfs I need 4 states (currx,curry,dir,turn). I couldn't understand this part can someone explain it to me . Thank you

Скажите пожалуйста,как вы решали задачу B через DFS(строка,столбец,направление,кол-во поворотов).Я так и сдавал,но почему-то не заходило(

For Problem G,could anyone please tell me the detailed way to cut the field into O(n) rectangles without deleted cells? I can't understand the way mentioned in the editorial.Thanks!

Can E be solved for N ≤ 10⁶? It's possible to calculate knapsack for this constrains.

Can someone give more detailed explanation of problem D ?

Thanks

Problem G can be solved using Hopcroft-Karp algorithm, if you optimize it hard enough: 26669894.

I think problem B has a better solution with brute force and a little dp firstly, initialize 2 arrays h and v so that h[i,j]=number of cell with road work from (i,1) -> (i,j) and v[i,j]=number of cell with road work from (1,j)->(i,j) since igor can only make 2 turns so his way must be one of these: --- — ---- | ^ | | | | | | <-- --> | V ---- so we just need brute force and calculate the number of cell with road work on the path (get it from h and v cause he can only go up, down, left or right)

Problem F has a tag "divide and conquer". Is there a solution with O((n + m + q)polylog(n + m + q)) time complexity?

I have a solution for problem F with time complexity O((N+M)logN) using segment tree.

Just in case someone is looking for a proof for problem A (793A - Oleg and shares)

We can't increase the values of any number, so we have to make bigger numbers equal to smaller numbers by subtracting k (zero or more times) of them.

Suppose the array is sorted.

At some point we'll have to make numbers arr[i] and arr[0] equal, and the only way is by subtracting k from arr[i] some number (q) of times and subtracting k from arr[0] some number (p) of times so we have: (a = arr[0], b = arr[i] for simplicity, 0 < i < n)

a — pk = b — qk

(b — a) = k (q — p)

We don't know (and we don't need to know) values p and q, but now it's certain that (b — a) must be divisible by k.

Now the key step is that if k divides (b — a), then we can make b equal to a by subtracting k (b — a) / k times because the only criteria to make a = b — qk is that k divides (b — a). This is optimal.

Getting W.A. for problem B......Can anyone provide a test case for which this fails?

Very easy solution brute force solution B- no DP or dfs/bfs at all. It takes full advantage of the fact that the solution must use at most 2 turns:

Because of the two turns limitation, there are two possible cases for our final path. Our directions for the travel can either be D/U => L/R => D/U or L/R => D/U => L/R.

Assuming the two locations are (r1, c1), (r2, c2), the first case case can be handled as such:

Iterate through all subarrays board[i][c1:c2]. If a subarray with 0 obstacles inside is found, and the subcolumns board[i:r1][c1] and board[i:r2][c2] also contain 0 obstacles, then we've found an answer. These subarrays/subcols by themselves will represent a valid 2 turn path, so if they contain no obstacles, it is obvious an answer has been found.

This same logic can also be applied to the second case. If searching both cases yields no answer, then we can safely return "NO".

Accepted implementation: https://mirror.codeforces.com/contest/793/submission/164203477