I couldn't seem to find a blog entry for this contest (COCI Round 4), so I created one! Let's discuss the problems of the fourth round of the COCI since the contest is already over. (http://hsin.hr/coci/)

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

1 | tourist | 3557 |

2 | Um_nik | 3494 |

3 | Radewoosh | 3344 |

4 | wxhtxdy | 3309 |

5 | LHiC | 3302 |

6 | Benq | 3286 |

7 | mnbvmar | 3274 |

8 | Petr | 3254 |

9 | yutaka1999 | 3190 |

10 | ksun48 | 3170 |

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

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | PikMike | 165 |

3 | antontrygubO_o | 165 |

3 | Vovuh | 165 |

6 | tourist | 162 |

7 | rng_58 | 160 |

8 | majk | 156 |

8 | Um_nik | 156 |

10 | 300iq | 155 |

I couldn't seem to find a blog entry for this contest (COCI Round 4), so I created one! Let's discuss the problems of the fourth round of the COCI since the contest is already over. (http://hsin.hr/coci/)

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/16/2019 11:23:44 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How did you guys solve the last problem, Akvizna?

I am the author of the last problem.

Let dp[i][j] be the maximum possible amount that Mirko can win in game with i rounds and j opponents at the beginning, divided by 100 000. dp[i][j] = min (dp[i — 1][j — k] + k / j), for k in 1, 2...j It is enugh to get 20 points.

To get 50% you need some observations. Let a_1, a_2...a_k be the number of people that have been thrown out in each round. It's not hard to prove that a_1 >= a_2 >= ... >= a_k. Also a_1+a_2+...+a_k = n so we get a_i <= n/i, because otherwise we would have a_1+a2+...+a_k > n. Because of that dp[i][j] = min (dp[i — 1][j — k] + k / j), for k in 1, 2,...n/i so total complexity is now n*(n+n/2+...+n/k) = n^2*(1+1/2+...+1/k) = n^2 log k and that is enough to get 65 points.

To get 100% you have that see that dp[i][j+1] — dp[i][j] <= dp[i][j] — dp[i][j — 1] which means that we can use aliens trick.

More about aliens trick you can learn here. https://ioinformatics.org/files/ioi2016solutions.pdf (the last problem, subtask 6.)

Wow, never before had I heard of Alien's trick, thank you so much! By the way, really nice problem, especially (now that I know how to solve it) the second subtask.

Thanks!

You can eliminate the log factor.

dp[i][j] =min(j×dp[i- 1][k] -k) /j+ 1, so it's a classical problem of finding a minimum y-intercept of functiondp[i- 1][k] ×x-k, aka convex hull trick.If you are not very confident on the precision, then you may prefer faster routines to make long doubles work..

Yes, and you can also use divide and conquer optimization (quadrangle inequality).

I need to know how to solve the third problem kisik, still don't know why my code fails so bad haha

Nevermind, didn't read the FAQ. It says:

4. Should I use %lld or %I64d for long long input/output in C++?%lld.

Yeah I've just read it :(

I'm not sure if you still need it, but I'll leave you my code for the problem here Code

I did something like that, mine only works for N <= 1000. I will check my code for correctness. Thank you!!

How to solve Slagalica?

Suppose after a mega move number at node

Xmoves to nodeY. Add an edge betweenXandY. If you do this for allN*Mnodes, the whole parallelogram will be decomposed into some simple cycles.Kmust be equal to lcm of those cycle lengths.Let the prime factorization of

Kbep_{1}^{a1}p_{2}^{a2}...p_{k}^{ak}. We must have . This condition is both necessary and sufficient for the existence of answer. Because it is possible to swap any 2 adjacent nodes of the parallelogram with the given operations. For example applyingT(x- 1,y- 1),T(x- 1,y- 1),R(x- 1,y- 1) consecutively swaps numbers at nodes (x,y) and (x- 1,y). Since now we can swap 2 adjecent numbers, it's not hard to construct cycles of lengthsp_{1}^{a1},p_{2}^{a2}, ...,p_{k}^{ak}