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
* * * * *
Hey,
ReplyDeletefor 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!
its working ....
Deletemay be u forgot \n
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.
ReplyDeleteFor Hubullu, I'm thinking of it this way:
ReplyDeleteThink 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).
This comment has been removed by the author.
DeleteHye, 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