[GYM] Codeforces Round #383 (Hard) editorial

Revision en1, by Arpa, 2016-12-22 20:20:31

Hello again, It’s Arpa as usual :P. Hope you enjoyed from the Gym, and it’s here is the editorial.

Preparation details:

The problems authored by me when the main contest was authoring. Here is a table, showing percentage of expected accepts (in my opinion, before the contest) and the number of accepts.

A BCD
Expected 100% 30%70%10%
Accepted 27 080

Difference from main problems

A : n is bigger, binary_pow will not work. You need to calculate in a faster way.

B : n and also numbers are much bigger, simple xor will not work.

C : n is bigger, simple LCM will not work because answer would become really large.

D : Number of alphabet’s are 26 instead of 22, so it isn’t possible to allocate a array with size 2z (z = 26).

Hints

A : Write last digit of 1378n for several small values. Calculate in a fast way.

B : Note that if then . Use trie.

C : If the answer exists, it depends on the lengths of cycles in the functional graph. Factorize numbers and calculate LCM.

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. Give id to each mask.

Details

First accepts: A : retired_coder, C : wrinx.

Funniest code : shengdebao ’s code : 23229169. He was managing to get accepted in problem C, with a solution :O.

Solutions

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

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


مقدار یار همنفس چون من نداند هیچ کس ماهی که بر خشک اوفتد قیمت بداند آب را

Translation: No one knows value of good friend as I know, fish will know the value of water when it fall on the beach.

Goodbye ; )

Tags gym, round383, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Arpa 2017-06-28 19:23:32 212 Switched from Google drive to Mega.nz
en5 English Arpa 2016-12-22 21:01:49 4 time complexity of hrzuser solution has changed
en4 English Arpa 2016-12-22 20:32:03 247 packages added
en3 English Arpa 2016-12-22 20:24:05 6 * to \cdot
en2 English Arpa 2016-12-22 20:21:54 152 changed heading styles
en1 English Arpa 2016-12-22 20:20:31 2550 Initial revision (published)