USACO - Combination Lock

After you read the problem statement you must have some insights about the solution (brute force over all possible settings, mark them and finally count them to print the answer).

We have to brute force over all possible settings that open the combination, the tricky case is where one setting opens both combinations, you must not count this twice, I used a set data structure to mark good settings (a setting that opens at least one of the combinations).

Now you have to decide how you want to do the brute force? Since I like recursions I did it using a simple recursive function.

A recursive functions consists of repetitive work on some state :

In my recursive function "markThem", I work on x[ idx ] and call the same method to work on x[idx + 1]. What must happen to x[ idx ]? It can have any value in range [x[idx]-2, x[idx]+2], so there are 5 possible values for x[idx], at each step (in for loop) I assign a value from that range to x[idx] and call markThem with argument idx+1.
What is the stop condition? When idx equals 3, then we have changed values of x[0], x[1] and x[2] and we have a possible settings and we must mark that.

Finally in main function I print size of the set data structure as the answer.

UVa - 13249 - A Contest to Meet

Link to the problem on UVa Online Judge

There are a few key points in the problem statement that can guide you to the solution. We want to calculate the worst case scenario of putting three people in random intersections and calculate the time they arrive at a common intersection. So no matter where they are located initially they will find an intersection and meet each other there. It's not the best choice, and that's the point, we have to calculate how long a live TV broadcast must last to cover their journey.
First question : From the three persons who is the worst walker and will take longer to get to the destination? The person with the slowest speed.
Next question : Which path is the worst for the slowest person to traverse? Actually which two intersections as start and end is the worst for the slowest person of the group? The two intersections that are farthest from each other.
So we have to calculate shortest path between each two pairs of intersections. Which algorithm you know that is asymptotically optimal for this job? The answer is Floyd-Warshall algorithm. After calculating all pairs shortest path using this algorithm, find the two farthest intersections and calculate how long does it take for the slowest person to get from one of them to the other.

As you know X = V.T so T = X / T. If we want to round up a division operation instead of X / T we can use (X + T - 1) / T, think about this, why this rounds up the division?

USACO - Ordered Fractions

One way to solve this problem is to construct all possible fractions, reduce all of them as possible, sort them and print them.

Another way is to use DFS.
 

Lets start with (0,1) and see what can we build? (Check it yourself)
and fraction is something like this :
 

USACO - Arithmetic Progressions

Let's think about it, Have you noticed the small boundary of N & M, What can we do with this small boundary? Isn't producing all possible values of p^2+q^2 good? Because they are not too many, and the biggest p^2+q^2 is when p=250 and q=250, in which p^2+q^2 = 125,000. So let's produce all of them.
Now take a look at N, If we brute force over the length of the progression, and start from each possible starting value, and check whether this start with this length can end up an arithmetic progression with N values? There is a little thing we have to be concerned about, after picking starting value and length of the progression, how do we check whether this would end up in a progression with N values?
Suppose the starting value is 13 and the length is 5, we want to know whether 18, 23, 28, 33 are available or not? To do so, when producing all possible p^2+q^2 just mark them in an array, if mark[x] is set to true, then we know that there exist p and q such that p^2+q^2 = x. In this way you can pass the test in the given time limit.

USACO - The Clocks

Let's think about the problem statement more, what do we have?

We have a set of 9 clocks that we want them all to show 12 o'clock and we have a set of 9 different keys that we can push to change the time of a subset of clocks. For example key #1 can change the time of clocks ABDE, so if you press key #1 then clocks labeled A, B, D and E will show a new time which is 3 hours plus their previous time.

If you don't observe any facts in the problem statement, This problem can be modeled as a graph which you want to go from a 'start' node to a 'destination' node, and can be solved using BFS. How many nodes do we have? By 'node' I mean a set of 9 clocks each of which shows a specific time (12-3-6-9), so each clock has 4 situations and the number of nodes is equal to 4*4*...*4 = 4^9 = 262144 that's not too many for a graph to run BFS on it. So you run BFS from the start node and try to reach node(12,12,12 --- 12,12,12 --- 12,12,12) How many neighbors does a node have? Each node has 9 other neighbors through 9 different keys.

But as I told if you observe a simple fact you can see that each key has 4 different situations, so instead of running BFS to find the solution you can use recursion to decide how many times you want to push key #i, and check if you can change all the clocks to show 12 o'clock. I myself think the second solution is more cute than the first solution, there is also another solution which takes O(1) and needs much more insight about the problem.

Codeforces Beta Round #91 (Div. 2 Only) - C. Lucky Sum

problem statement
After reading the problem statement, at first I was shocked by the range of input, 1<=left<=right<=10^9, but after a close look to the problem again, I found that there are not too much lucky numbers in the range, I recursively generate lucky numbers with this function :

#define ll (long long)
vector all;
void back(ll v, ll p10)
{
    all.push_back(v);
    if(v > 1000000000)
        return;
    back(v+4*p10, p10*10);
    back(v+7*p10, p10*10);
}

then I sort "all", sort(all.begin(), all.end()),
and after that, I iterate through "all", I have a variable x that is the leftmost point that next(x) is not calculated yet, then if x <= all[i] this means all of the points k in range [x, all[i]], next(k) = all[i],
so I add (all[i]-x+1) * all[i] to the output, but if for example input is like this 2 6, I add (4-2+1)*4 + (7-5+1)*7 which is wrong, actual output is (4-2+1)*4 + (6-5+1)*7 so I added this if else to my code :
            if(all[i] <= right)
            {
                sum += (all[i]-x+1) * all[i];
                x = all[i]+1;
            }
            else
            {
                sum += (right-x+1) * all[i];
                x = all[i]+1;
            }

Codeforces Beta Round #91 (Div. 2 Only) - B. Lucky Substring

problem statement
After reading the problem statement carefully and checking the sample test cases, I noticed this part of the problem "needs the lexicographically minimum one", and thought by myself if it is gonna be a substring of input and lucky and lexicographically minimum one, then it has to be "4" or "7" because other substrings that are lucky contain 4 and 7, and there is no lucky number other than "4" or "7" that is repeated more times than "4" or "7" because at least the lucky number is going to be "44", "77", "47", "74", and at this cases "4" and "7" are repeated more times than these substrings.
So I just iterated through input string and counted number of 4's and number of  7's, if there is no 4 or 7, then output -1, otherwise if cnt7 is less than cnt4 output 4 else output 7.

Codeforces Beta Round #91 (Div. 2 Only) - A. Lucky Division

problem statement
As you read in the problem statement, you have to find out whether a number has a divisor which is also a lucky number, so iterate from 1 to n, if n is divisible by i, then check whether it is a lucky number or not?
Easily write a function that take a number and tell whether it is lucky or not, in other words the function checks whether all of the digits in the given number are 4 or 7.

1. bool isLucky(int n)
2. {
3.     int rem;
4.     while(n)
5.     {
6.         rem = n%10;
7.         if(rem != 7 && rem != 4)
8.             return false;
9.         n /= 10;
10.     }
11.     return true;
12. }

TopCoder - SRM 515 DIV 2 - RotatedClock - getEarliest

After I read the problem statement, I didn't find out what's going on :-D. I think the most important part of the problem for me was these two sentences : "The clock has a scale marked in 30 degree increments ... She measured the angles of hands from a certain mark". Before I pay attention to these two sentences, I was confused of test case 3, I was thinking why 19 19 is impossible? Then I found that measured degrees are from a certain mark, so both of them can not be 19 19, but of course both of them can be 0 0, 30 30, 60 60, 90 90 ...
At first I was trying to solve the problem in this way : Which mark has she chosen to measure the degrees? 0? 30? 60? 90? 120? 150? 180? 210? 240? 270? 300? 330? I thought that I could map one of the degrees to one of these 12 origins, then map the other one, and check whether the resulted degrees show a true time? then I figured out that it's a little hard to implement. I tried to reverse my approach. I iterated h = 0 to 12 and m = 0 to 60 and each time I made mDegree and hDegree, at this moment I have to verify whether mDegree and hDegree is an answer or not? So I shifted both of them 0 degrees, 30 degrees, 90 degrees, 120 degrees, ... 330 degrees and checked whether they matched input or not, if yes I had found the answer. But at this time I checked though my approach seems true but test case 2 gave me time 07:01 that's 210 degrees and 6 degrees that if I add 30 to both of them it becomes 240 and 36 that matches test case 2, I read the problem statement again and I found that her measurement device supports integer degrees not real numbers, because 07:01 is not 210 degrees and 6 degrees, it is 210.5 and 6. So I added another condition to my program that if minute was odd it is not my answer. And Finally Accepted :-).

TopCoder - SRM 515 DIV 2 - FortunateNumbers - getFortunate

As you can see in the problem statement just a simple brute force is enough to pass the time limit. I produce all combinations of a[i] + b[j] + c[k] for all i, j, k and check whether it is a fortunate number or not, if yes I insert the number in a set and finally I return the size of the set.