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

# | User | Rating |
---|---|---|

1 | tourist | 3698 |

2 | Um_nik | 3463 |

3 | Petr | 3341 |

4 | wxhtxdy | 3329 |

5 | LHiC | 3300 |

6 | ecnerwala | 3285 |

7 | sunset | 3278 |

8 | V--o_o--V | 3275 |

9 | Benq | 3262 |

10 | mnbvmar | 3248 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 187 |

2 | Errichto | 181 |

3 | rng_58 | 161 |

4 | PikMike | 160 |

5 | Petr | 157 |

5 | Vovuh | 157 |

7 | 300iq | 151 |

8 | Ashishgup | 149 |

8 | Um_nik | 149 |

10 | majk | 148 |

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

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2019 10:09:27 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

Nnumbers with the minimum not less thanX. Build a bipartite graph where vertices on the left represent row, and vertices on the right represent column. For each cella_{i, j}, ifa_{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 consistNedges, it is possible to find a combination ofNnumbers satisfying the condition above (we choose all cell (i,j) such that the edge connectingi-th vertices on the left andj-th vertices on the right is in the maximum matching).Thank you ! got ACed on D. I'm trying to solve E.

Anyway, can anyone explain G and J?

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.

How did you precalculate these

Nefficiently?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.

Can you prove an upper bound on how many

ifrom 1 toNthat Bob will win?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.

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.

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

My Soln of A.

Can you share yours?

Here

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

J:

The first part can be computed by a

O(2^{V}V^{2}) TSP DP. The overall time complexity isO(2^{V}V^{3}) since you need to compute at most 2^{V}times Gaussian elimination.Do you know any tutorial on how to compute determinant of a

N*Nmatrix inO(N^{3})?After applying Gaussian elimination in

O(N^{3}), the determinant of the matrix is equal to the product of all the element on the main diagonal.How to solve B?

B can be solved by using DSU or DFS to check whether (i,n-i+1) is in the same connected conponents. ( i<=1<=(n+1)/2). Here is my sol (using DSU): Here

how to solve F?

My soln for F -

Chose a const

SIZE~sqrt(n). (500 gives AC, and 1500 gives TLE on last TC) Now divide allBinto two half one less thanSIZEand other greater than or equal toSIZE.For Type 1 queries - if

B> =SIZE. Directly update all values. //O(n/SIZE) ifB<SIZE, //O(1) Keep an arrayinc[SIZE][SIZE] i.e. (B,A)And update as

inc[b][a] + =cstFor Type 2 queries -

Time Complexity — O(Q*SIZE) in worst cases.

But unfortunately, it gives AC.

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

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

How to solve C, H, I?

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 assignT[0], we also assignT[2N- 1]. Keep a pointer to the head and tail ofS. When we assign positions inT, we may need to move the head and tail pointers ofS. WhenSis a subsequence of the prefix / suffix ofTthat 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 inSfor aO(n^{3}) 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^{2}+ ... +x^{m})^{n}. No idea how to do that efficiently.I is a pretty standard problem. For example, see 451E - Devu и цветы 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 (you need to count ways of splittingkinnnon-negative integer summands; that is the same as splittingn+kinnpositive integer summands; that is the same as splittingn+kballs lying in a row innnon-empty groups by placingn- 1 "walls" that separate the groups inn+k- 1 positions (between each pair of balls)).But we overcounted something: we counted the partitions of

kinnnon-negative summands where some summands are larger thanm, though we should have not done that. Let's use inclusion-exclusion to handle the overcounting.How many partitions of

kinnnon-negative summands there are, if we are required to make someifixed summands larger thanm? Let's note that there are as many of them as there are partitions ofk- (m+ 1)iinnnon-negative summands (simply subtractm+ 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 (we need to choose

idefinitely overflowing summands out ofnand count the partitions ofkintonsummands such thatiof them are definitely overflowing).Does there any way to solve this problem with polynomial multiplication?

For I, we can rewrite the expression as (1 -

x^{m + 1})^{n}(1 -x)^{ - n}. Just use the binomial expansion on both and you have to evaluate the following: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...

how to solve problem C An alphabetical string is a string consisting of 0 or more capital letters (i.e. [‘A’..‘Z’]). Given an alphabetical string S[1..N], determine the number of palindromic alphabetical strings of length 2N that contains S as a subsequence (not necessarily contiguous). A string is palindromic if it is equal to its reverse.