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

Автор bhishma, история, 8 лет назад, По-английски

Problem Link : PMARK

Can anyone please help me with an approach to this problem . I was thinking about it for about 2 days but I couldn't come up with a solution . And is there a general approach to these type of problems .

UDP: Thank you guys for clarifying my doubts.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

You can do this problem by simple math , say we have n subjects then ( sum of n subjects mark ) % n == 0 we can say we can set equal marks for all n subject otherwise here n — 1 is always possible .

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How can we say that we can make n-1 subjects when ( sum of n subjects mark ) % n != 0

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      suppose we have two values a, b. Can you change b to any value you desire using a?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I just tried your solution it resulted in Wrong answer

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        yeah bhikkhu , because even negative marks are allowed

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          I will give you an intuitive explanation.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

          Suppose the array is A = {a1, a2, a3, a4, ...., an}. The only operation allowed is take two elements ai, aj and replace ai by ai-1 and aj by aj+1 or vice versa. Let's take sum S = a1 + a2 + .... + an. We can see that after each such operation, sum remains same because we increase one element whereas decrease the other by 1.

          Also notice that if we fix an element a1, we can use it to set rest of the elements to a given value. So, we can make at least (n-1) elements same. Can we achieve n?

          Now, since we know that after such set of operations, final sum will be same and to achieve all equal we must have a1 = a2 = .... = an = k. Then k * n = S, which means sum must be divisible by n. This is a necessary condition. To see that it is sufficient too, we use previous knowledge. Lets make all a2, a3, ...., an to 0. Since sum is constant, we will have a1 = S after making rest of the elements 0. Now, we have found previously that using a1, we can make any of the element equal to some value which means we can use a1 to make a2 = k = S / n. Similarly we can make a3 = k = S / n. Finally after making all a2, a3,....an to S/n, a1 will be equal to S — (n-1)S/n = S/n. Thus all of them are equal. This proves (S % n == 0) is sufficient too.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Thanks for the great explanation !

            So the soln should be

            if(sum % n == 0)
            return n;
            else 
            return n-1;
            

            But when I submitted it it resulted in WA

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится

              Your sum might have overflowed.

              You may use long long / int64_t or use int to compute mod using modular arithmetic since (a1 + a2+a3...+an) % n = ((a1+a2) % n + rest) % n. and you won't need 64 bit integers.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Thanks a lot dude !! It finally worked , yeah the overflow caused the problem. Thanks for explaining it very clearly.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

At first I didn't read that the elements could go negative and thought about the problem for sometime but could not come up with anything. Any Suggestions on how to solve the problem if all numbers had been positive and you could not make the an element < 0 ?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That won't change anything. The previous idea can still be applied.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yeah because sum can be written as sum = (sum/n)*n + (sum%n) so if sum% == 0 all the subjects can be made equal or else n-1 subjects can be made equal

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by bhishma (previous revision, new revision, compare).