January Long Challenge 2020

kshitij_789 · January 21, 2020, 3:37pm

I also do cubing(not professionaly though) take around 25 sec on average and 17 is pb. just can say that there are a lot of common people in cp ,math ,cubing and chess.

alei · January 22, 2020, 12:07am

Ada also solves Rubik’s cubes … in around a minute

vijju123 · January 23, 2020, 8:16pm

Unofficial editorial of ENGLISH can now be requested. The editorial is pending approval from setter and admin.

ananth360 · January 24, 2020, 4:42am

@alei Hi! I liked the anthill problem! Thanks!

I just had a question about it, what is your optimal solution for it? (Or rather your best approximate solution).

When you said contestants found cliques, I’m not sure how they did that, since as far as I know finding max cliques is NP hard.

And even once you find cliques, I’m not sure the best way to connect neighboring cliques, do you construct it edge by edge?

Thanks again

ananth360 · January 24, 2020, 4:43am

Hi! Not sure how to request for the unofficial editorial?

l_returns · January 24, 2020, 7:23am

Mail vijju123 on his email id.

alei · January 24, 2020, 3:19pm

I only had some general ideas of the possible approaches. The problem is based in that finding the square root of graphs is an unsolved problem. One idea is to find a covering with special subgraphs e.g if we divide the graph in many triangles we can save one operation, is not necessary to find exactly the max clique because there are also remove edge operations.

vijju123 · March 10, 2020, 3:13pm

Hi all,

Sorry for not being very prompt in updating - had a lot of things going on in personal life. All editorials are finished and already published on discuss. Out of all the editorials, I really recommend you all to read the following:

OWCAFILE - If you are struggling to learn FFT or how to solve similar problems, I’d suggest to read the note at end, read FFT in the mentioned way from pre-requisites and at least conceptually try to problem. Reading the editorial after that will help you knowing how to tackle FFT problems in long and short contests alike.
ARMYOFME - This is one of those hard problems which are actually conceptually interesting. As long as you know the pre-requisites, which is binary lifting and segment tree with lazy-propagation, you will see this is one of those hard problems which are ideal to learn from and practice. The editorial tried to make sure that any coder with required pre-requisite should grasp it without trouble.
DFMTRX - If you solved the problem using patterns, do give editorial a brief read. Try to look for interesting mathematical concepts which can help you.

Thanks to @kmaaszraa for the set of interesting problems - all the three problems were proposed by him.