TheGreatLoveImmortal's blog

How is "Shohag loves GCD" just 1700?
By TheGreatLoveImmortal, history, 2 weeks ago, In English

Just how did so many solve this problem. I understand the rating is related to the number of people who solved it during the contest but I don't get it. Even with the editorial it seems so tough. Just what prerequisties should I have to solve these types of problems during contests?

Though I have to say I learnt a lot from the editorial. Building using given conditions, Sufficiency of a condition.

Is there a better way to solve than the given editorial?

Problem Link — Shohag Loves GCD

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

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Maybe coz you have a strong knowledge in many topics, but not in sieve (like me), its solution using sieve looks very 1700 :)

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't know if it is better. But Look at my submission 293137515. without using sieve and simple marking solution.

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Read solution 2 in the tutorial, its easier. In fact, we can do it without sets and just using vectors 292960644

→ Reply
»
2 weeks ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

The main difficulty was reducing the condition in the statement to $$$a_j \nmid a_i$$$ if $$$j \mid i$$$

I knew that this condition was necessary, but in contest I just guessed that it was sufficient and proceeded based on that. I'm pretty sure many others did the same.

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have a fairly simple solution for it. To make you understand better, I have explained everything from getting the intuition, coming up with the claims, proving them, constructing the algorithm and handling the edge cases as comments in a very clean and beginner friendly code.

You can check it here — 295494155

→ Reply