nipul1's blog

Help in third problem of google kickstart round B
By nipul1, history, 4 years ago, In English

Problem My approach was to keep the multiplication factors in stack and pop them when a bracket ends

code

Please Help I am unable to find the mistake

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The value of factor will most probably overflow if it is something like 9(9(9(9(9(9.........)))

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

    so how can I deal with it, I thought of using modular arithmatic while contest but got stuck in the fact that fermat's theorem can't be applied to non prime numbers for taking mod so how actually we can handle that. thanks for replying

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Fermat's little theorem only comes into play when computing modulo inverse. There are no divisions, so it doesn't really matter if the value you've to take modulo by is prime or not.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        actually I had divided the factor value by the top of stack but now I have changed my code a bit and removed division part by recalculating the factor value each time it is needed

        code

        and it is still giving me wrong answer on second test case

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          In your submission

          1 factor should be long long

          2 value of map mp should be long long

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      I solved it using modular arithmetic.
      There are only additions and multiplications. Why would you need Fermat's theorem?

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

        Now I have changed the code using addition and multiplications but still getting a WA earlier I used division in my logic that's why I needed fermat's theorem Please review the code in my previous comment

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

          you could keep a stack of values instead of doing division you can just go back to the previous value, Example you encounter 2(9(..)).

          You append into your stack [1, 2, 18] as we encounter them in 2 .. 9 order, then after 9's parenthesis is closed you can just pop the 18 and go back to using 2, no need of division.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      My approach : Total digits will be at max 500 since each digit will be linked with at least 2 parenthesis and one char. So there are total 500digits. Just brute them every time you encounter ')', do some arithmetic, count frequency of each char. complexity will be (n^2 + m) where n is 500 and m is length of string. AC code https://ideone.com/qXVQCT

      → Reply