2018 Asia Singapore Preliminary Contest

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:57:14
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя YeuDieuNhieu

2018 Asia Singapore Preliminary Contest

Автор YeuDieuNhieu, история, 6 лет назад, По-английски

[](https://open.kattis.com/contests/asiasg18-prelim-open/standings) How to solve D and E, I tried but failed.

YeuDieuNhieu
6 лет назад
29

Комментарии (25)

Показать архивные | Написать комментарий?

xuanquang1999

6 лет назад, # |

D: Find all bridge in the graph, then DFS to see how many vertices reachable from vertex 0 after removing all the bridge.

E: Binary search the answer. Suppose we need to check whether it is possible to find a combination of N numbers with the minimum not less than X. Build a bipartite graph where vertices on the left represent row, and vertices on the right represent column. For each cell a_i, j, if a_i, j ≥ X, connect an edge from i-th vertices on the left to j-th vertices on the right. If the maximum matching of the bipartite graph consist N edges, it is possible to find a combination of N numbers satisfying the condition above (we choose all cell (i, j) such that the edge connecting i-th vertices on the left and j-th vertices on the right is in the maximum matching).

→ Ответить

xuanquang1999

6 лет назад, # |

Anyway, can anyone explain G and J?

→ Ответить

Jeffrey

6 лет назад, # ^ |

G: precalculate all N such that Bob will win. There are only less than 400 such values. You need an efficient enough precalculate program. Ours runs in less than 10 minutes.

→ Ответить

xuanquang1999

6 лет назад, # ^ |

How did you precalculate these N efficiently?

→ Ответить

Jeffrey

6 лет назад, # ^ |

For each i<=10^9, determine if there is any N found so far such that i-N+1 is prime. If none of them is, i is a new N we found.

→ Ответить

xuanquang1999

6 лет назад, # ^ |

Can you prove an upper bound on how many i from 1 to N that Bob will win?

→ Ответить

Jeffrey

6 лет назад, # ^ |

No, I guess it's related to distribution of primes which is really complicated. In contest, I discovered there are really few N that Bob will win only by experiment.

→ Ответить

aryanc403

6 лет назад, # ^ |

If someone is interested.
My offline sol to find all possible nos.
And AC soln with all no hardcoded.
But I as of now I don't have any proof on the upper bound.

→ Ответить

YeuDieuNhieu

6 лет назад, # ^ |

Unable to solve A with DFS? I tried but got TLE, so I changed to an algorithm O(9*n^4).

→ Ответить

aryanc403

6 лет назад, # ^ |

My Soln of A.
Can you share yours?

→ Ответить

YeuDieuNhieu

6 лет назад, # ^ |

Here

→ Ответить

aryanc403

6 лет назад, # ^ |

Thanks. You can reduce your time complexity to O(9*8*n^2). By using this piece of code.

const lli r[10]={-2,-2,-1,-1,1,1,2,2};
const lli c[10]={-1,1,-2,2,-2,2,-1,1};

for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=0;k<8;k++)
{
p=x+r[k];
q=y+c[k];
if (1<=p&&p<=n&&1<=q&&q<=n&&a[i][j]=='I' && a[p][q]=='C')
dd[p][q]=1;
}

→ Ответить

eddy1021

6 лет назад, # ^ |

+21

Enumerate all the possible cycles
For a cycle, contract all the vertices into one vertex
then, we can calculate the number of spanning tree after contracting with Kirchhoff theorem

The first part can be computed by a O(2^VV²) TSP DP. The overall time complexity is O(2^VV³) since you need to compute at most 2^V times Gaussian elimination.

→ Ответить

xuanquang1999

6 лет назад, # ^ |

Do you know any tutorial on how to compute determinant of a N * N matrix in O(N³)?

→ Ответить

eddy1021

6 лет назад, # ^ |

After applying Gaussian elimination in O(N³), the determinant of the matrix is equal to the product of all the element on the main diagonal.

→ Ответить

des1997

6 лет назад, # |

how to solve F?

→ Ответить

aryanc403

6 лет назад, # ^ |

My soln for F -

Chose a const SIZE ~ sqrt(n). (500 gives AC, and 1500 gives TLE on last TC) Now divide all B into two half one less than SIZE and other greater than or equal to SIZE.

For Type 1 queries - if B > = SIZE. Directly update all values. //O(n/SIZE) if B < SIZE, //O(1) Keep an array inc[SIZE][SIZE] i.e. (B,A)
And update as inc[b][a] + = cst

For Type 2 queries -

cnt=a[D];
for(i=1;i<SIZE;++i) //O(SIZE)
cnt+=inc[i][D%i];

Time Complexity — O(Q*SIZE) in worst cases.
But unfortunately, it gives AC.

→ Ответить

AnLeHuu

6 лет назад, # ^ |

Can I see your full code? send it for me to this email thanks. phamnhi8910@gmail.com

→ Ответить

aryanc403

6 лет назад, # ^ |

Link of code is already present in the comment. Just click on soln in first line. :P

→ Ответить

aryanc403

6 лет назад, # |

How to solve C, H, I?

→ Ответить

arknave

6 лет назад, # ^ |

← Rev. 2 →

C: Dynamic Programming. Consider building the big string (I'll call it T) character by character. Because it has to be a palindrome, when we assign T[0], we also assign T[2N - 1]. Keep a pointer to the head and tail of S. When we assign positions in T, we may need to move the head and tail pointers of S. When S is a subsequence of the prefix / suffix of T that we've built so far, just multiply by 26^remaining. The state is just how many characters are remaining and the positions of the pointers in S for a O(n³) solution.

H: Just BFS from outside the grid and count how many walls you hit. If you enter an "active" cell don't continue the BFS from there.

I: It looks like finding the coefficient of x^k in (1 + x + x² + ... + x^m)ⁿ. No idea how to do that efficiently.

→ Ответить

Kaban-5

6 лет назад, # ^ |

← Rev. 3 →

+13

I is a pretty standard problem. For example, see 451E - Devu and Flowers for the application of the same idea.

Firstly, consider the case when m (the number of objects of each type) is infinite. In this case the answer is simply $\text{[math]}$ (you need to count ways of splitting k in n non-negative integer summands; that is the same as splitting n + k in n positive integer summands; that is the same as splitting n + k balls lying in a row in n non-empty groups by placing n - 1 "walls" that separate the groups in n + k - 1 positions (between each pair of balls)).

But we overcounted something: we counted the partitions of k in n non-negative summands where some summands are larger than m, though we should have not done that. Let's use inclusion-exclusion to handle the overcounting.

How many partitions of k in n non-negative summands there are, if we are required to make some i fixed summands larger than m? Let's note that there are as many of them as there are partitions of k - (m + 1)i in n non-negative summands (simply subtract m + 1 from each "definitely overflowing" summand, after that there will be no restrictions on said summand).

In the end, by inclusion-exclusion, the answer is equal to $\text{[math]}$ (we need to choose i definitely overflowing summands out of n and count the partitions of k into n summands such that i of them are definitely overflowing).

→ Ответить

.anis.

6 лет назад, # ^ |

Does there any way to solve this problem with polynomial multiplication?

→ Ответить

Death_Scythe

6 лет назад, # ^ |

+20

For I, we can rewrite the expression as (1 - x^m + 1)ⁿ(1 - x)^- n. Just use the binomial expansion on both and you have to evaluate the following:

$\text{[math]}$

→ Ответить

vamaddur

6 лет назад, # ^ |

← Rev. 2 →

I do not really understand the solution for C.

"Because it has to be a palindrome, when we assign T[0], we also assign T[0]." Do you mean T[0] and T[2*N-1]?

How do you handle S being in the middle (i.e. it does not lie entirely in the first N letters or the last N letters) for the DP state? I do not see how the transitions work for this case.

EDIT: I misread the question as substring instead of subsequence, so the solution makes a lot more sense now...

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 22.11.2024 09:37:46 (k3).

Десктопная версия, переключиться на мобильную.

При поддержке