VK Cup 2019-2020 — Отборочный раунд (Engine) и Codeforces Round #623

Автор PavelKunyavskiy, история, 5 лет назад, перевод, По-русски

Tutorial is loading...

Разбор задач VK Cup 2019-2020 - Отборочный раунд (Engine)

Разбор задач Codeforces Round 623 (Div. 1, по задачам VK Cup 2019-2020 - Отборочный раунд, Engine)

Разбор задач Codeforces Round 623 (Div. 2, по задачам VK Cup 2019-2020 - Отборочный раунд, Engine)

PavelKunyavskiy
5 лет назад
23

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

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

PavelKunyavskiy

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

+10

Автокомментарий: текст был переведен пользователем PavelKunyavskiy (оригинальная версия, переведенная версия, сравнить).

→ Ответить

jqdai0815

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

+194

Maybe you need to improve your English.

→ Ответить

adamant

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

← Rev. 2 →

Russian statement and editorial is full of typos and silly mistakes as well, so I think author should either buy a new keyboard or learn to type... (Or maybe stop using google translate)

→ Ответить

snorkel

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

We need codes also!

→ Ответить

programmisstt

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

-8

Почему разбор только последней задачи на русском?

→ Ответить

PavelKunyavskiy

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

Остальные пока не перевели, в процессе.

→ Ответить

adamant

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

In problem F you may observe that one of primitive roots in nimber field of size $$$2^{2^k}$$$ is $$$2^{2^k}-1$$$ so you may precalculate some of its powers beforehand to further simplify BSGS-algorithm and take discrete logarithm with base being a primitive root. If you do so, you won't need to develop tricky multiplication algorithm as $$$64^2$$$ algo with precalc for powers of two would be enough.

→ Ответить

Basilhijaz

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

Can you give a better explanation for the optimization of problem (A. Recommendations)? I got to the O(n^2) solution during the contest but couldn't improve it.

→ Ответить

nikeshthapa255

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

-8

https://codeforces.net/blog/entry/74214?#comment-583996

→ Ответить

_Damon

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

Can you please explain more on how to improve the complexity of A.Recommendations from N^2 to Nlogn.

→ Ответить

nikeshthapa255

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

I have used heap and greedy approach 71716787

First i have put all unique elements in a dictionary with list of values.

Then i keep a temp list to store all the list and pop one largest element to keep in that position and others increase one position and carry on doing this till temp is empty , time complexity — O(N) + N*O(log(N))

→ Ответить