ACM 1787. Turn for MEGA / Поворот на МЕГУ

 Every minute can pass only k cars, which means after if there were M cars at the Ith minute, then if that number is less or equal than k than all will pass or else the remaining M-k cars will be left to pass on the I+1 th minute. We need to do this on our given array, loop over it from 1 to n and see if the current element is less or equal than k then turn it to 0 and move on, otherwise subtract k and add the remaining number to A[I+1] . The final answer will be held in the element A[n+1]

       FULL SOURCE CODE

ACM 1149. Sinus Dances / Танцы синуса

 There is nothing much to explain here, you just need to implement and get the string as given in the task description carefully. Check the source code for some details and hints on implementation.

       FULL SOURCE CODE

ACM 1493. One Step from Happiness / В одном шаге от счастья

  We can just check for the numbers N-1 and N+1 and output the answer. The checking part is easy, you need to take the last three digits and sum up and then the rest 3 digits and sum up and check for equality. There is a little thing which we need to take care about. The number can have a preceding 0. For handling it, you can input it as string and then digit by digit add to number 1 where in the end you will have a 7 digit number where the digits from 1 to 6 can be 0s because the number will have an unusable digit 1.

       FULL SOURCE CODE

ACM 1785. Lost in Localization / Трудности локализации

 This task is just a bunch of if statements which need to be carefully implemented.

       FULL SOURCE CODE

ACM 1654. Cipher Message / Шифровка

 We will use C++ STL stack for this one. If you are using other language than you should implement stack yourself, stack basically is a sequence which has an option of accepting elements form the beginning and removing elements from the beginning. You can find more info about stack/C++ stack here. We need to keep a stack which will give the answer string. We need to loop over out string and check, if the new element which we are about to add to the stack equals to the top element of the stack, then we remove the top element of the stack, otherwise we push the new element to the top of the stack. After those operations we will be down to a stack which will contain out final answer.

       FULL SOURCE CODE

ACM 1083. Factorials!!! / Факториалы!!!

 Just input the number and the string and calculate with the given formula n*(n-k)*(n-2*k).....(n-m*k) where m*k<n.  (k is the number of !s).

       FULL SOURCE CODE

ACM 1086. Cryptography / Криптография

    The 15000 the prime number is 160000 and something so we can find all the prime numbers up to 200000 and save them and then process the input. The fast way of finding the prime numbers from 1 to N is the sieve of Eratostenes which works for O(NlogN) time. You can find info about the sieve of Eratostenes here.

       FULL SOURCE CODE

ACM 1001. Reverse Root / Обратный корень

You need to input some numbers and then output their square roots in the reverse order.

       FULL SOURCE CODE 

ACM 1209. 1, 10, 100, 1000...

I am not sure about the pattern in here but we can do it with recovering the sequence. indeed the query can be up to 2^32 where we can't keep the full sequence but just because it consists of only 1s and 0s, we can only keep the positions of 1s. In C++ the STL container map can handle this situation. So how do we do it, the first one is 1. The second one is also 1. Then the next 1 can be found by jumping form the previous one 2 steps. Then 3, then 4, .... We can do it until we calculate all the 1s up to 2^32 which is not too long in our case, it will be a little more than sqrt(N).

       FULL SOURCE CODE

ACM 1319. Hotel / Отель

 Suppose we have a function which takes a point and starts going into the direction of the diagonal and filling the elements on the way until it gets out of the border N. It is easy to implement, we need to take the given coordinate and add every time 1 to both of the coordinates to get to the next cell. We need to launch this function for the cells A[1][n...1] which will complete the first half and also A[2...n][1] which will complete the matrix.

       FULL SOURCE CODE

ACM 1079. Maximum / Максимум

There might some pattern in this sequence but just because n<99999 then I suggest building the sequence and then calculate the maximums. I suggest precalculating all the answers before processing the input. You can keep an additional array of answer ANS[100000] where ANS[i] shows max (A[1],A[2],....A[i]).

       FULL SOURCE CODE

ACM 1313. Some Words about Sport / К вопросу о спорте

Here is how our program should work. We start from a certain cell, and decrease both coordinates by 1 and output the number of the new cell if it is within the range [1..n][1..n].  We need to do this for all the elemenets of the first column one after another which will cover the half of the solution and then continue it for the elements [2..n][n].

        FULL SOURCE CODE

ACM 1264. Workdays / Трудовые будни

 We check for every number N times. Just because the numeration starts from 0  (0...M) we have M+1 number to check for which gives the final answer of N*(M+1).

       FULL SOURCE CODE

ACM 1197. Lonesome Knight / Один в поле воин

 We need to input the coordinates in the chess format and turn it to number and then check for every coordinate the knight can strike.
This is the list of all the corresponding coordinates needed to add to the current coordinate to get to a cell which a knight can strike.
  1, 1, 2, 2,-1,-1,-2,-2
  2,-2, 1,-1, 2,-2, 1,-1

       FULL SOURCE CODE

ACM 1005. Stone Pile / Куча камней

N is up to 20. Which means there are total of 2^20 ways of forming 2 different piles. The brute force solution will be enough but we need to find the best way to implement it. We can do it with bitmasks.  In other words, we take numbers from 1 to 2^20 and get their binary representation (which must have a length of N, if it is not long enough we add zeroes to it). Then in our binary representation , the Ith position will tell us to which pile do we take our Ith elemenr. If it is 1 than we need to take it to the first pile otherwise to the second pile.

       FULL SOURCE CODE

ACM 1293. Eniya / Эния

    Surface of each will be AxB and also x2 because we need both sides and the final answer will be AxBx2xN.

       FULL SOURCE CODE

ACM 1409. Two Gangsters / Два бандита

Just because both of them shot the last bottle , the entire number of bottles will be A+B-1. And the final answer A+B-1-A, and A+B-1-B.

       FULL SOURCE CODE

ACM 1025. Democracy in Danger / Демократия в опасности

It is easy to understand that we need to choose the groups which have the smallest amount of people so that the half of it would be small and the total number of voters would be as small as possible. So we need to sort our given data and choose the first N/2+1 groups.

       FULL SOURCE CODE

ACM 1068. Sum / Сумма

Just a simple sum problem with little constraints, but be careful when dealing with the negative numbers because the input can consist of negative number as well.

       FULL SOURCE CODE

ACM 1000. A+B Problem

 read 2 number and output their sum, the first task of almost any programmer.

       FULL SOURCE CODE

SPOJ 5976. Traversing Grid (TRGRID)

The constraints of this task give us a hint that there is no complicated algorithm which must be hardly implemented. After doing a few tests with pen on paper you might figure out a few things. First of all suppose we have NxM grid, so after doing one full cycle (on cycle means that we went to the end of the first row, then turned down, went to the bottom of the grid, then turned left went to the end and then turned upwards and went until we reached the coordinate (2,1) which means that we are again facing right which means that we have go all over again but on the grid of size (N-2,M-2). For a better understanding have a look at the picture below.

The red line represents the first cycle, after it we are again facing right and it is the same as passing 1x2 grid. So, the first thing is decreasing the grid as much as we can by cutting 2s out of it. How do we cut 2s? We take the minimum of 2 sides minus one, and if that number is even then we subtract it from both sides or we decrease it with 1 and then subtract it.  After the cutting process the smaller side of grid will be left either 1 or 2. Now it is time only for a few conditions. In case of (1,1) the answer is R, in case of (1,2) it is R, in case of (2,1) it is D , in case of (2,2) it is 'U' , in case of (1,other)  ,  it is R and in case of , (other ,1) is D and for (2,other) is 'L' and (other, 2) is 'U'. Also check out the source code .

       FULL SOURCE CODE 

SPOJ 1728. Common Permutation (CPRMT)

  From the first look it really smells like a complicated dynamic programming algorithm but we need to have a deeper look to understand the difficulty of this task. Here is what the task wants from us: find a string x that a permutation of x will be a subsequence of s1 and s2. Subsequence means that the letters should exist on those strings s1 and s2 and every other letter must be on the right than the previous one (they don't have to be consequetive) . This would be a dynamic programming task if there wasn't the phrase "one permutation of x". Let me demonstrate with an example. CgrAyuT

(I made some letters uppercase for clarity). So , if we have an X="CAT" than it can be considered as a subsequence of the given string but x="TAC", can't , but we are free to take any permutation of X we want so we will move the elements and form the word "CAT" and check. So,  the answer is simple, it will be just a string which contains all the letters which both of the strings contain. It can be found easily in O(s.size()^2) time which is enough. NOTE don't forget to sort the final answer because the problem requires the first answer in alphabetical order.

       FULL SOURCE CODE

SPOJ 8061. Christmas Play (AMR10G)

N<=20000. We need to sort the entire array and then for every i , if i+k-1<=n choose the minimum of A[i+k-1]-A[i].

       FULL SOURCE CODE

SPOJ 7169. Pizza

The first thing just comes to mind is to add all the number and round up and output the answer, but unfortunately it is not how it works. Suppose we have 3/4 3/4 and 1/2 by doing the way I described above you will calculate 2 pizza's for friends but the answer is 3, because if we by 2 pizzas for 3/4 s then with the remaining 1/4 and 1/4 we can't form one 1/2 . So, here is what I suggest doing for being correct. First of all we need to buy pizzas for all 1/2s (take 2 1/2s and add 1 pizza) until either one 1/2 is left or none. Then we need to buy 1 pizza for 1/2 and 3/4 (until we run out either of 1/4s or 3/4s). If we have 3/4s left then we need to increment the answer by their number. Then we need to add the number of 1/2s *0.5 and the number of 1/4s *0.25 and round up the answer. NOTE Don't forget to add 1 to the total answer (see the problem statement) and output the new line.

       FULL SOURCE CODE

SPOJ 8670. THE MAX LINES

    First of all, it is easy to notice that the triangle is a right angle triangle because it has a base which is the diameter of the circle. that means that BC^2=AC^2 + AB^2 we can add and subtract one AC which will not change the equation. BC^2=AC^2 + AB^2 -AC + AC  . Let us write BC^2 as (2r)^2 which will be 4r^2 and let's group the right part properly. 4r^2= (AB^2+AC)+AC^2-AC . =>

AB^2+AC= 4r^2 -AC^2+AC which can be considered as a function f(AC) where AC is the unknown variable. We need to find the maximum value of function f(AC) which can be done with differentiation . f '(AC)= 0 -2*AC +1 .
-2*AC+1=0 => AC=1/2  => we can easily notice that the function increases up to f(1/2) and then it decreases so the maximum value is at AC=1/2 which gives the full answer of 4*r*r -1/4+1/2 =4*r*r+1/4.

       FULL SOURCE CODE

SPOJ 6219. Edit Distance

  This is a basic problem of edit distance which you can read about in here http://manyprogrammingtutorials.blogspot.com/2014/09/edit-distance-levenshtein-distance.html

.

       FULL SOURCE CODE

Edit Distance ( Levenshtein distance)

  The task is to find the minimum number of operations necessary to turn one string into another. The available operations are 1. insert a char everywhere in a string 2. Delete any char of the string 3. Replace any char in a string.  This is another Dynamic Programming problem. Suppose the length of the first string (S1) is N and the length of the second one (S2) is M. We need an array of NxM where the element A[I[J] shows the answer for the segments S1[1..I] and S2[1..J] (let us add a blank char in front of both string). For a better understanding let's have a look at a table below.

As you can see the string starts with an empty character, which means that the first row and the first columns are filled by formula a[1,I]=I and a[J][1]=J which is true because for obtaining an empty string we need to delete all the elements of the other string which will give an answer of the size of the non empty string. Basically when looking at the cell A[I][J] we need to look to the cells A[I-1][J] , A[I][J-1] and A[I-1][J-1]. Let's consider the cell A[I-1][J] of we were able to build the string S2[1..J] from S1[1...I-1] for A[I-1][J] steps then fro building the string S[1..J] from S[1..I] we need to add one more step (just add the new character (new means the Ith) and it will be A[I-1][J]+1 moves). The same goes for A[I][J-1]. Now let's consider the A[I-1][J-1] the, int this case we have 2 new elements S1[I] and S2[J], we can build it with the same number of steps if we won't have to deal with the new elements which means that if S1[I[==s2[J] then we only need A[i-1][j-1] operations to make the string S2[1..J[ from S1[1..I] otherwise A[I-1][J-1]+1 operations. So the final formula is A[i][j]=min( A[I-1][J], A[I][J-1], A[I-1][J-1]  + 1 (+1 if S1[I]not equal to S2[J]). 

SPOJ 7757. Flowers Flourish from France

The task itself is not hard, but we need to carefully handle the implementation. Here is hat I suggest, take the first letter and keep it in a variable. Let's call it K. K is the symbol which we need to check every time. and also turn it into upper case, if it is already uppercase it will not change, we do it so that we can avoid the problem of letters being the same but the cases being different. Then loop over the given string , whenever we encountered a space that means that the next letter is a first letter of a word, we take that letter, turn it into uppercase and check with variable K. If they are the same we keep going, but now the value of K becomes the newly found letter uppercased. If at some point a letter which was after ' ' (the forst letter of a certain word) is not equal to current K than we abort and output 'N'.

       FULL SOURCE CODE

       

COJ 1626. Adding Reversed Numbers

This task is a simple implementation task. Juts keep the number in an array digit by digit so that you can calculate the reversed number easily. The numbers are small so this means that we won't have to do the long number sum.

DOWNLOAD THE FULL SOURCE CODE

SPOJ 7406. Beehive Numbers (BEENUMS)

The important thing here is to notice the pattern of the beehive. The first layer contains 1 cell. When building a new layer we lay 6 more. If you just take out pen and paper and start drawing you will figure out the pattern, when laying the next layer we lay 6*2 12 cells, so for laying Nth layer we will need N=6*(N-1) cells when N>2. I recommend calculating all the numbers and store them in the map before processing the input.

       FULL SOURCE CODE

SPOJ 95. Street Parade (STPAR)

   We need to take out elements in order with a little help of one stack.  We need to solve this by eliminating every possible element starting from the left and also taking out those very same elements from the stack if it's their turn ( the phrase "their turn" means that we already eliminated all the elements up to the current one , and we can eliminate him if he is one the leftmost spot or on top of the stack). We need to loop over the given array from left to right and see, if it's his turn then eliminate it (this can be understood in many ways, just ignoring and passing to the next one  or removing it from the array, it depends on your preference ). (note that we keep a variable cur (current) which shows which is the current element to be eliminated), now if we can't eliminate it we add it to our stack waiting for it's turn, (NOTE there is no other way, if our current element can;t be eliminated now because it's not his turn then we do not have any other option but to push him into stack). And in every step we also check "if it's now the turn of the top element of stack", if yes we need to keep removing them until we either reach an element which can't be eliminated now or our stack gets empty.  We need to keep doing those until we have looped over all elements. If we were able to successfully remove all of them then the answer is yes.

       FULL SOURCE CODE

SPOJ 379. Ambiguous Permutations (PERMUT2)

The constraints N<=100000 make this task an easy one. We need to build the sequence and check if every element is equal to the given sequence if it is then the answer is yes otherwise no.

       FULL SOURCE CODE

COJ 1189. Skew Binary

It is guaranteed that the number will fit in 32 bit integer, the rest is easy,we need to input the number as a string, then from right to left loop over it and every time multiply the current digit with it's appropriate power of 2 minus 1.

       FULL SOURCE CODE

COJ 1143. To and Fro

This is an implementation task so we need to think the easiest and the most understandable method. I suggest trying to recover the matrix then the string itself. We can do it in the following way. The first element of the given string S[0] is the first element of an array A[1][1] . Now we need to move according to the direction, and every time write the current char in the current spot, whenever we reached the end (or the beginning) of the array we need to flip the direction, get down to the next row and keep on going. Check out the source code for a better understanding.

       FULL SOURCE CODE

SPOJ 400. To and Fro

This is an implementation task so we need to think the easiest and the most understandable method. I suggest trying to recover the matrix then the string itself. We can do it in the following way. The first element of the given string S[0] is the first element of an array A[1][1] . Now we need to move according to the direction, and every time write the current char in the current spot, whenever we reached the end (or the beginning) of the array we need to flip the direction, get down to the next row and keep on going. Check out the source code for a better understanding.

       FULL SOURCE CODE

COJ 1457. Baseball Tournament

The number of distinct pairs of N people is ( N*(N-1) )  /2 here is why
suppose we have all the members numbered from 1 to N.
1,2,3...N.
So, one can be a pair( can play a game) with 2,3,4,...N.  Total N-1 games
2 can be pair with all starting from 3 . with 3,4,5,...N. Total N-2
........
..........
and N-1 can be a pair with N. total 1 pair.
So the result is, 1+2+3+..+N-1 which has a good formula of  ( (N-1)*(N-1+1) ) /2
The final answer is the answer above multiplied with the given parameter K.

       FULL SOURCE CODE

COJ 1179. Optimal Parking

  The task might not be very clear on the statement part or maybe it is left up to the reader to understand. Anyway, the task wants the best coordinate to park where the distance which we walk would be minimal, and the distance means, getting out of the car, entering every store and coming back to the car. No matter where we park our car the distance walked will be minimal if we get to the beginning (or to the end) of the line and start visiting stores one after another until we have reached the other end of the line and then we also need to add the distance which takes from the other end of the line to our car. The constraints are only from 0 to 99 so we can just try out every single coordinate and calculate with brute force method.

      FULL SOURCE CODE

COJ 1808. Hamming Distance

We only need to input the 2 strings then loop over and see if elements on the same index match or not.

       FULL SOURCE CODE

COJ 1328. CAVerage

We only need to sum up all the numbers, then divide on N and then check if it is smaller than every element or not.

       DOWNLOAD THE FULL SOURCE CODE