Codeforces Round #383 editorial

Revision en5, by Arpa, 2016-12-07 16:09:21

UPD. sorry, it seems there is some problems with packages, I'll fix the problems tonight.

Hello again, and hope you have been Joon-Joon of the round :P

I’m preparing harder version of some of problems (Div.2 A, B, and Div.1 A, D) and I’ll put them on some gym, so if you are interested in harder version of problems please wait for about one week.

You can see and download the problem archives (pretests, tests, statements, validator, checker, solutions) here.

Preparation details:

In 25 May _-_Sa1378_-_ came up with problem Div.1 D and other problems authored inchmeal. Several problems has changed during the process. And several new problems authored, in fact I have another problem set to prepare another div.1 + div.2 round, but I haven’t enough time now : (.

Paintings in problems was suggested by me, painted by _-_Sa1378_-_ and edited by me. Problem stories and this editorial were suggested and written by me. KAN helped us preparing the round very much, we are thankful to him. This table for each person and for each problem shows the number of the committed changes (in polygon) he has made in preparing the problem (it is good for showing how much someone was involved in preparing).

User\Problem Div.2 A Div.2 BDiv.1 ADiv.1 BDiv.1 CDiv.1 DDiv.1 ETotal
Me891616101937114
_-_Sa1378_-_321070114
KAN and testers 3359771361

Here is another table, showing the number of expected accepts (in my opinion, before the contest) and the number of accepts (after system testing).

Div.2 A Div.2 BDiv.2 CDiv.2 DDiv.2 EDiv.1 ADiv.1 BDiv.1 CDiv.1 DDiv.1 E
Expected 6000450020005001506004003005010
Accepted 3966172311316841047947450151

Hints

Div.2 A : Write last digit of 1378n for several small values.

Div.2 B : Note that if then .

Div.1 A : If the answer exists, it depends on the lengths of cycles in the functional graph.

Div.1 B : It’s similar to a simple knapsack problem, think on O(n·W) solution using dynamic programming.

Div.1 C : Build a graph and put edges between each 2 * i, 2 * i + 1 and each BF and GF.

Div.1 D : Keep a mask for each vertex, i-th bit of maskv is true if the number of edges in the path from root to v such that letter i is written on them is odd. Now if number of bits in is 0 or 1, path between v and u is Dokhtar-kosh.

Div.1 E : Sort all of the options, then problem becomes easier, solve the new problem with sqrt decomposition.

Details

Div.2 A

Idea, authoring, solution by _-_Sa1378_-_, preparation by _-_Sa1378_-_ and me.

My and _-_Sa1378_-_ ’s birth year in Solar Hijri calendar is 1378.

Div.2 B

Idea, authoring, solution by _-_Sa1378_-_, preparation by _-_Sa1378_-_ and me.

Div.1 A

Idea, authoring, solution, preparation by me.

Attractive boys/girls are called Joon-Joon in persian. Owf is a sound used when we (persian) are interested in something, especially when we see something attractive, such as our crush :P

Div.1 B :

Idea, authoring, solution, preparation by me.

The problem authored by me 2 days before the contest :D (#FastAsFerrari). Attractive girls are called (some word similar to) “Hos” in persian. It’s a good place to thank Amsen, whose name (Hir) gave me this idea (to use word “Hos” instead of “attractive girl”).

Div.1 C :

Idea, authoring, solution by _-_Sa1378_-_, preparation by _-_Sa1378_-_ and me.

“Kooft” is something make people die. “Zahre-mar” meaning is “Venom of snake”.

Div.1 D :

Idea by _-_Sa1378_-_, authoring, solution, preparation by me.

“Dokhtar-kosh” is an adjective, used when something is very very attractive.

Div.1 E :

Idea, authoring, solution, preparation by me.

Solutions

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

I’d like to finish the editorial with below poem by Hafez:


از صدای سخن عشق ندیدم خوش‌تر یادگاری که در این گنبد دوار بماند

Translation: I have never seen anything that sounds better than love, it’s the relic which will remains in the universe.

Good luck and see you soon in “Round #383 hard version” ; )

Tags edirorial, 383

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English Arpa 2017-06-29 09:11:03 95 Switched from Google drive to Mega.nz
en8 English Arpa 2017-06-03 09:14:56 753 Fixed grammar mistakes using Grammarly, added more details in prepration details section, added "I used Google Docs for writing everything."
en7 English Arpa 2017-01-01 14:43:22 178 The upd from top removed. _-_sa1378_-_ --> sa1378.
en6 English Arpa 2016-12-07 23:41:36 182 Tiny change: 'tonight. -Done.\n\nH' -
en5 English Arpa 2016-12-07 16:09:21 97
en4 English Arpa 2016-12-07 14:22:32 444
en3 English Arpa 2016-12-07 13:21:56 25 Tiny change: 'In the name of God.\n\n\nI’d like t' -> 'I’d like t'
en2 English Arpa 2016-12-06 21:36:47 94
en1 English Arpa 2016-12-06 21:12:38 6125 Initial revision (published)