Editorial For CODEMarathon div-1/2/3 contest 1

Problem: Largest Area (ad-hoc)

You have to find the largest area that can be formed by taking two two sticks. Simply find two largest numbers and multiply them.
My solution


Problem: Finding Dukkar (ad-hoc)

You have to find the manhattan distance between last position and origin. Just follow the directions.
My solution


Problem: Dukkar in a game (implementation)

You have to find the total sum for each player and then print the largest number. If multiple people share largest score, you have to print lexicographically smallest name.
My solution


Problem: Dukkar's triangles (brute-force)

Here you have to simply check all the possible selection of 3 distinct points and check if they can form a triangle. You can either check area of triangle formed by three points or that sum of two sides is more than the third. The first approach is easier to implement.
My solution


Problem: Dukkar the dictator (graph)

The kingdom can be thought of as a graph with individual cities as nodes of the graph. The edges of the graph are represented by the connections between different cities. Now to lighten up the whole kingdom, the whole kingdom must be connected. Suppose there are k different connected components. So to connect the whole kingdom we just need to add k-1 more connections. So, we have to find out the number of connected components in the graph. This can be done by either dfs or bfs.
My solution


Problem: Poly (Union Find data structure)

First we maintain an array for general where we maintain loyalty to either dukkar or mathur. Next we maintain two different array, one for predecessor(arr[]) of current city, and another for general(arr1[]) of the given city Whenever a city A captures another city B,  we put arr[B]=A. And whenever a general captures g captures a city A we have arr1[A]=g and arr[A]=A. Whenever the capturer of a particular city A is asked, we simply find predecessor of A till arr[A]!=A. The ans is then arr1[A]. The above thing is Union Find data structure. For better understanding, you can go through the chapter in Introduction to Algorithm or some online sites.
My solution

Problem: Super Powers (Number Theory)

First you have to find the prime factorization of both P and Q. This can be done in log(n) time by calculating primes upto approx. 40000. Now once you have prime factorization and count of all the factors, note that in the prime factorization of P^R, all prime factors are the same as prime factors of P and no. of prime factors is R times that of prime factors of P. Now a simple observation is that Q^S divides P^R only if the count of prime factors of Q^S is always less than or equal to the count of prime factors of P^R.
My solution