Блог пользователя pratikmoona

Google Code Jam Round 1A : Problem A
Автор pratikmoona, 14 лет назад, По-английски
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?
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    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.
    → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
    → Ответить