rachitiitr's blog

[Video Tutorial] Codeforces Round #430 (Problem D)
By rachitiitr, history, 7 years ago, In English

Hi

I've explained the solution for problem D from today's contest in my YouTube video.
It was a nice math based problem, solved using tries. Code link will be added later in the video description.
I will be adding the video for C tomorrow.

If you want daily updates about my channel,
1. Subscribe to the channel.
2. Follow the facebook page.

Cheers!

  • Vote: I like it
  • +51
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

I don't think you strictly need tries. Just store occurrences of each prefix. But your solution would consume less memory. Solution without tries: 29900524

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your approach for the problem C

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For problem C, you just need to note that for each vertex the number of possible distinct gcds is small. This is because for each descendant of the root, the possible gcds divide lcm(a_root, a_child_of_root). Now keep that for each vertex, and in dfs, update that accordingly and call the dfs for the children.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks rachitiitr! It was wonderfully explained.

→ Reply