**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.

# Light OJ Hints

Advertisements