Let's discuss problems.

How to solve A, D, G, J?

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

1 | tourist | 3434 |

2 | Petr | 3353 |

3 | OO0OOO00O0OOO0O0…O | 3314 |

4 | fateice | 3306 |

5 | Um_nik | 3286 |

6 | Syloviaely | 3274 |

7 | dotorya | 3145 |

8 | LHiC | 3114 |

9 | Radewoosh | 3098 |

10 | mnbvmar | 3096 |

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

1 | tourist | 178 |

2 | rng_58 | 166 |

3 | Petr | 155 |

3 | csacademy | 155 |

5 | Swistakk | 149 |

5 | lewin | 149 |

7 | Um_nik | 142 |

8 | Errichto | 140 |

9 | matthew99 | 138 |

9 | Vovuh | 138 |

Let's discuss problems.

How to solve A, D, G, J?

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/23/2018 20:28:32 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|

J: check on a lot of random modules <= 5000.

UPD: oops, my solution is wrong

If the given number is divisible by every number up to 5000, this will fail. To make it pass, we have to increase the upper limit.

Different tests (33-52) contain integers divisible by every prime up to 10

^{7}, and tests 33-34 are divisible by all primes from 2 to 833 947 simultaneously.Seems that there were no tests with given number divisible by every number up to 5000 because i have an OK

Yeah, taking larger powers of very small primes as witnesses can pass these tests.

Anyway, as with hashing, there sure are tests against every possible small collection of witnesses known in advance, but there is no known test against every possible witness, so it's normal for such solution to pass, except if it chooses only few small and fixed primes.

J:

We solve it by Euler's criterion. Pick about

Kprimes, module the given integer and test it with Euler's criterion. The probability of failure will be about 2^{ - K}.Thank you. Finally got AC with first 50 prime numbers bigger than 10

^{9}+ 7.G(div.2: up to 4*N moves):Spoiler 1Stand with knight in the same column, next stand in the same row. Now you are very close to him.

Spoiler 2Then on every move try to stay in the same row as knight do, but slightly go to the right if the knight is on the right, otherwise slightly go to the left. Later means to go diagonally.

Spoiler 3You don't need to read size of board or check borders, because you go only where the knight proved the board exists.

Is that all that you do? It seems that I can last for more then N turns this way

Suppose N = 2K — big enough

Queen=(1, 1);Knight = (K, N)

Turn1: Queen=(K, 1), Knight = (K+2, N — 1)

Turn2: Queen=(K, N — 1). Knight = (K + 1, N — 3)

Now I think you need 2N — 1 more turns to win And it will be even a bit more, if we move knight starting point to the left to (2,N) or so

(column first in all coordinates)

For N it is not enough. Div.2 problem statement is: to not exceed

4*Nmoves (`"Your task is to capture the Knight in at most 4N moves"`

). No access to Div.1 statement. My solution works in 2*N I think.For Div1 it is at most N moves.

I think your solution is 2N+1 moves

We used basically the same idea(go to the same row, then win in O(2 * halfwidth), but we needed additional bruteforce for first few turns because otherwise sometimes we needed N + 1 turns

How to solve B, H?

H is the computation of a resultant (case

t=xyin https://en.wikipedia.org/wiki/Resultant#Number_theory ), but general algorithms for computing resultants are not fast enough. It seems that an efficient algorithm is given in http://algo.inria.fr/flajolet/Publications/BoFlSaSc02.pdf (Corollary 4).H:

Using this one can easily find the

k-th coefficient of and then calculate .I am not sure if I understand how to use this equation

So we calculate all logarithms (), calculate from the logarithms of

fandgand calculate the exponent.B is similar to Jigsaw Puzzle from Moscow Subregional 2013.

We can solve it with dp by profile. State is:

column id

mask of colors in last column

list of possible masks (each mask: has 1 on position i if there is a horizontal pile from last column to next one in row i)

Yes, it looks like m * 2^n * 2^(2^n) states. But most of states are unreachable. And for n=6 there are about 1600 reachable states per column.

B. Checking if coloring is good can be done by dynamic programming on set of border points which are already colored. Dynamic programming of set of states reachable states of dynamic programming above on one layer works fast enough to pass or precalc (~1.2s in yandex context for me).

See code for more details. I think it's quite easy.

SpoilerCan you please explain meaning of a few things: mask, x.first, the for loop inside go (what does the i stand for)?

Edit: I think I understood the gist.

Mask: colors of previous column (not exactly previous column, if you are at r,c then they represent colors of cells i,c for i<r and I,c-1 for i>=r)

x.first: every bit represents status of the previous column (not exactly, defined as above). 0 means not yet covered and 1 means already covered.

Loop I: for each of the covered/uncovered status we try to figure out if we want to color current cell bit then what are the possible next statuses.

Yes, you are correct. Probably naming could be a bit more understandable :)

It took me 140 minutes to solve 7 tasks and more than 3 hours to solve H, I feel this is an overkill, but anyway...

We use Newton's identities. Check the definitions of

e_{i}andp_{i}there.Let

A= {a_{i}},B= {b_{i}},C= {a_{i}b_{j}}. We are given the values ofe_{i}(A) ande_{i}(B), and we want to gete_{i}(C).e_{i}(A), computep_{i}(A).e_{i}(B), computep_{i}(B).p_{i}(C). This is quite easy becausep_{i}(C) =p_{i}(A)p_{i}(B).p_{i}(C), computee_{i}(C).Thus, the main challenge is the conversion between

p_{i}ande_{i}.Now, let's use Newton's identities. It says that the convolution of (0,

p_{1}, -p_{2},p_{3}, -p_{4},p_{5}, -p_{6}, ...) and (e_{0},e_{1},e_{2}, ...) is (0,e_{1}, 2e_{2}, 3e_{3}, 4e_{4}, ...). LetP(X) = 0 +p_{1}X-p_{2}X^{2}+p_{3}X^{3}-p_{4}X^{4}+ ... andE(X) =e_{0}+e_{1}X+e_{2}X^{2}+e_{3}X^{3}+ .... We haveP(X)E(X) =E'(X)X(Don't miss derivative sign).The conversions between

PandEcan be done as follows:P(X) =E'(X)X×inverse(E(X)).P(X) /X=E'(X) /E(X) = (log(E(X)))', thus .Computation of inverses: Link (Check problem E)

Computation of exponentiation: Link (Left part of Fig.1 is enough)

(I'm not quite sure why these computations with integrations/differentiations are valid.)

Yes, it's exactly the author's solution. When I was preparing this problem, I first came up with the idea to use Newton's identities to convert between

e_{i}andp_{i}. After a while, I realized, that this could be done efficiently using and .So I decided to use this big constraints in the problem statement, so that more obvious solutions don't pass. If the constraints were smaller, one could use Berlekamp's algorithm or Cantor–Zassenhaus algorithm to factorize the polynomials, and after that just multiply a lot of linear polynomials.

Your solution and Golovanov399's solution are the same, by the way.

You can calculate

logandexpefficiently using Newton's method.Also, you should notice, that

logandexpare not well-defined when we are working modulo 998 244 353, because we sometimes divide by zero. But we don't need that. We are only interested in the first 10^{5}coefficients of polynomials, sologandexpare well-defined.Conversion between

p_{i}ande_{i}could be done by divide-and-conquer FFT.We solved H by Newton-Girard formulas and divide-and-conquer FFT.

D: first bring the outter point to the inner layer in the shortest possible way. Then continue descending in the same manner, checking whether it’s optimal to traverse the current layer to connect the two points :)

For

problem A, first consider the same problem on a square grid. It can be easily shown that, if we fix the perimeter, a polyline with the largest area is the polyline most closely resembling a square: the sides are either all equal or differ by 1.On a hexagonal grid, the reasoning is similar, although there happen to be more cases. Sure, our wall will be a convex hexagon. We can show that two consecutive sides differ by at most two: otherwise, we can get a larger area with the same perimeter. In Figure 1 below, we change the part ABC of the wall with lengths 2 and 5 to part DEF, increasing the total enclosed area by 1 (the difference is that we get XEFC instead of DABX).

Figure 1Thus we can take a rough guess of what will be the length of one side

s, then try all values froms- 2 tos+ 2 for the two neighboring sides, and so on.If we investigate further a bit, we can find the optimal solution for each possible perimeter. The six cases are shown on Figure 2 below.

Figure 2Here is a short solution summarizing the six cases.

A piece of hexagonal paper was provided in the statement to help solve the problem.