Light OJ Hints

1000 (Greetings from LightOJ) – Simple adhoc problem.
1001 (Opposite Task) – Exact opposite of problem 1000, carefully notice testcases and read the statement clearly.
1002 (Country Roads) – Modified Dijkstra algorithm is the key. We just need to modify a single line in our regular Dijkstra algorithm as when we use,
if(a[i][j] + dist[i] < dist[j])dist[j] = a[i][j] + dist[i];
while here we should use
if (max(a[i][j], dist[i]) < dist[j]) dist[j] = max(a[i][j], dist[i]);
1003 (Drunk) – We have to find if there a cycle exist in the graph, if there is a cycle he can’t drink all.
1004 (Monkey Banana Problem) – Basic DP problem.
1005 (Rooks) – Basic recursion problem
1006 (Hex-a-bonacci) –  Replace the recursion with a for loop. Also make sure to take the modulo before storing the values in array as the values can be quite large.
1007 (Mathematically hard) – The input require very first IO method. scanf and printf would be the best choice. We need to use a modified version of the Sieve method for this problem. One approach can be-> first store the prime numbers using the sieve method and then to use a sieve like method to calculate phi of n. Take extra care to use llu while printing out the answer as the output is in the range of unsigned long long.
1008 (Fibsieve`s Fantabulous Birthday) – Observe the pattern of how the numbers are appearing.
1010 (Knights in Chessboard) –  Adhoc problem. Find the pattern.
1012 (Guilty Prince) – Basic bfs problem.
1014 (Ifter Party) – The simplified task is to find the divisors of p – l which are greater than l.
1023 (Discovering Permutations) – One simple way is too use c++’s next_permutation library function.
1033 (Generating Palindromes) – Find the LCS of the given string and the reverse string. Then subtract the LCS from the actual length of the string. Find LCS using DP.
1042 (Secret Origins) –  Adhoc problem. Don’t use brute force. See how the bits changes from input to output answer.
1065 (Number Sequence) – Basic matrix exponentiation problem.
1096 (nth Term) – Matrix exponentiation. try to implement the matrix first.
1110 (An Easy LCS) – Find LCS using DP, then backtrack the LCS string if there is any. Also remember to maintain lexicographical smaller order.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s