20 March 2018

UVA 10679 - I Love Strings!!

Problem Explanation

Category: Easy
Type: String Ad Hoc


This is simple string ad hoc problem. You just need to find out a substring of a given string. But the tricky situation is you have to find out a string which will match from the start of the given string.
Suppose you have a string  IamAgoodStudendAndILikeProgramming and your query string is mming . This is a substring string but in case of this problem this is not a solution. If your query string is IamAgoodS then it is a solution of the problem. That is your query string must have to match from the beginning of the main string.

For cource code link click here

10 March 2018

Codeforces 946 A Partition

Explanation

category : Easy

You just need to sum up all numbers. If you find any negative number just make it positive.

Source code link

09 March 2018

Codeforces 950 A Left-handers, Right-handers and Ambidexters

Problem Explanation

Category: Easy

One have to find out maximum number of player which is even. Check the amount of left hand player  right hand player. If the amount is not same then take a amount of player from ambidexters, which can make equal number for both left hand and right hand. after taking some player from ambidexters , if still there are some player remains in ambidexters then divide the player among left hand and right hand players. 
If the amount of ambidexters player is zero the just squre the value which is minimum of left hand and right hand players. 

Some test case
10 12 10
28
1 0 1
2
2 4 0
4
3 6 9
18
5 5 5
14

Source code link Click here

Find out divisors of a number with a efficient way

Suppose you have 24 and you need to find out all divisors of the number. The normally what we do? We just divide the number from 1 to 24. That is we have to check 24 times. For 24 it is not a problem. But if I ask you do the same operation for 1234567 or for 1000000 or for 2345678? 😛
The whole day will be spent, isn't it?
Now let's check one thing.
All divisor of 24 is 1,2,3,4,6,8,12,24 and
(1*24) = (2*12) = (3*8) = (4*6) = 24
Here we multiply first element with last element, second element with second last element and third element with third last element.
That is we need to multiply ith element and (n-1+i)th element and need to count total number of multiplication and then again multiply the total by 2.

But now the question is we are only given a number not the divisor list. Then what we should do? Yes, we will find out the list and just count with the above approach.
That is at first we divide

24 by 1 and we get 24 and the pair is (1,24)
24 by 2 and we get 12 and the pair is (2,12)
24 by 3 and we get 8 and the pair is (3,8)
24 by 4 and we get 6 and the pair is (4,6)
24 by 5 but this is not a divisor
24 by 6 and we get 4 and the pair is (4,6). We already got the pair so avoid it.
24 by 7 but this is not a divisor
24 by 8 and we get 3 and the pair is (3,8). We already got the pair so avoid it.

if we go more towards then same pair will appear that's why we will now stop. Now count how many time we did this. It is 8 times, isn't it? Carefully observe , if we stop our calculation at 5 or just before 6 that is when we get any pair which already occurred, we will be done. Carefully observe 5 is equal to integer part of (square root of 24 ) +1

Now lets take a look on the sudo code


  1. Take a number n
  2. For i=1 to (square-root of n) +1
  3.  check if n is dividable by i or not
  4. if dividable then count = count +1
  5. if not go to 2 again
  6. print value of count
You can check for 48,100,3000,4000. 

Now you have a home work. Follow bellow what I write
24 / 2 = 12
12 / 2 = 6
6 / 2 = 3
3 / 3 = 1

Upto 1 I get 4 result and now multiply 4*2 = 8. 
O My god!
Am I correct for the above calculation? Check yourself for 48, 100, 122 
If I correct then find out the sudo code or algorithm. 



UVA 10679 - I Love Strings!!