pratikmoona's blog

Google Code Jam Round 1A : Problem A
By pratikmoona, 13 years ago, In English
Problem A of the recently held CodeJam Round 1A has the following official analysis. I however coded an O(1) solution.


Did anyone else do this directly like this?
  • Vote: I like it
  • +5
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Your solution is the same with official. However it isn't O(1), because in your code GCD can't be calculated with O(1) time.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    It is O(1) as complexity of GCD(a, b) is log(max(a, b)). Here one of them is 100 and that will be >= the percentage, which is a constant.
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It can be coded simplier. Frined solved this like:

cin >> n >> pd >> pg;
bool possible;
if ( pd != 0 && pg == 0 || pd != 100 && pg == 100) possbile = false;
else possible = (100/__gcd(pd, 100) <= n);

But it's described in analysis
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I wouldn't call this simpler! It is definitely shorter though...

    I couldn't figure out which part of the analysis actually talked about this solution.
    → Reply