Tuesday, December 15, 2009

Some more problems of SPOJ...

I recently breached into the top 1200 ranks in the world, but sad news is, soon I'll be thrown out too. The points keep on decreasing on a regular basis. Never mind this works as an incentive to work on more and more problems. :)
So, m writing this post for some more problems of SPOJ. The problems I m going to discuss are of an average level.

BISHOPS: Its an easy problem, if we try verbally. The answer is (2*n-2) i.e. equal to the number of diagonals. But the difficulty lies in the range of the inputs. N<=10^100..!! OMG!!.. :).. Try strings..

MINCOUNT: Actually what I did.. I tried it out for certain test cases and found that the answer is.. (n*(n+1)/2)/3.. i.e. the total number of coins in the triangle divided by 3. But why its so.. its still unanswered for me.. kindly post the explanation if you get one..!! :)

HUBULLU: Same mincount type problem here too.. seeing the discussion in the forum I got some hints that who so ever plays first wins.. So, it became a very very easy question for me to crack but why it happens is yet not understood by me..

TRICOUNT: Its another mathematics problem.. try it for sometime with all yours geometrical anlysis and at one time you will definitely come out with a solution that is much like (t*(t+2)*(2*t+1))/8.. where t is the level of triangle. Try it now yourself..!!

SAMER08F: Another age old problem of how many squares are there in a given bunch of squares?? Answer lies in the sum all squared numbers till the number of squares in each side of the grid i.e. if N=8 then answer= (1*1) + (2*2) + ... + (8*8).

Seeing my last three posts of SPOJ I think now its easy for any newbie to get started. So, no more discussing algorithms of SPOJ problems from my side. Keep practicing and who knows one day you beat [Trichromatic] XilinX..!! :p

* * * * *

6 comments:

  1. Hey,
    for the mincount problem,(n*(n+1)/2)/3 is not being accepted.
    I tried this,says wrong answer even though i am using unsigned long long int!

    ReplyDelete
  2. Vipul... n*(n+1) may return out of the limit of an unsigned long long int ;) even if the whole operation (after dividing by 6) doesn't.

    ReplyDelete
  3. For Hubullu, I'm thinking of it this way:
    Think 1 is out of the list of numbers he can choose.
    If the first player knows he would win, he will choose a number that'll make him win. If he knows he'll lose, all he needs to do is choose 1 and the problem is still the same except that he has already chosen 1 and the other player is bound to lose (since both of them play optimally).

    ReplyDelete
    Replies
    1. This comment has been removed by the author.

      Delete
    2. Hye, I have been cramming on this question. But as you say, If he knows he'll lose , all he needs to do is choose 1 .... then hasn't he passed the ball in other player's court??

      Delete