bhishma's blog

Can anyone help me with this codechef problem [SOLVED]
By bhishma, history, 9 years ago, In English

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.

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

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 .

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

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

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

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

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

        I just tried your solution it resulted in Wrong answer

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

        yeah bhikkhu , because even negative marks are allowed

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

          I will give you an intuitive explanation.

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

          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.

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

            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

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

              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.

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

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

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

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 ?

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

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

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

      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

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

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

→ Reply