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

Div 1 :

Problem 1 : Jon snow doesn't know : implementation, STL

Code : http://ideone.com/aLDrEV
The problem requires you to find the initial position and final position of all numbers from 1 to N*N. Brute force would not work because of the constraints. N = 1000. so we need to find a better way. either you can use 'map' data structure or use a simple array to hash them. eg. a[N*N][2]. and use a[k][0] = x_k and a[k][1] = y_k. now you can query position for any number in O(1). Now when you traverse the shuffled array you can get its original position quickly getting complexity O(N*N).


Problem 2 : Tyrion and Black water : Binary search, hashing

Code : http://ideone.com/9ZCRWW
You need to find the most recent color of a node in a full infinite binary tree. Given a update = {node, color}, you can store it with update id : k and increment k at every update. Now for every query you can traverse from the node to the root. In the path you can check if a node is colored or not. It it is colored then you can check if it is the latest update, else move up. Finally print the color of the latest update.
Complexity : O(logN)

Problem 3 : Daenerys and the strange staircase : dp, recursion

Code : http://ideone.com/ZR9uLY
Given a step you need to travel from 1st step to Nth while collecting maximum number of coins.
First you need to check if you can reach the last step of not. You can run a dfs from 1st node. If last node is within reach, you need to traverse those paths.

Given you can reach node 'p' then you can reach p + k, p + k + 1, and p + k + 2. and number of coins upto p+k, p+k+1, p+k+2, is max(coins[p] + noOfCoins[p+k+j]) for all valid j.

Complexity : O(N)

Problem 4 : Valars Moghuls : Binary Search, sortings, Math

Code : http://ideone.com/4jty9Q
You need to get all the warriors to a point such that the cost of travelling to it is minimum. You can simply Binary search the answer. And since the cost in X direction in independant of Y so they can be individually searched for.
for a point(x, y): find the costs of all the warriors to reach point. Check if it is smaller than the current cost, go left, else go right.
You can see that the curve of cost is a Unimodular function so you can Solve this using Binary search.

Cute Hack : This question can be solved using Simple hack. You can find the median of both the coordinates separately as the distance independantly, simply find the distance from the median.

Complexity : O(NlogN)




Div 2:

Question 1 : Arya and magical wheels : implemetation , math

Code : http://ideone.com/OC0FDs
the cirle on top is moving around the lower one without slipping. So LCM of circumference will give the distance covered on a straight line before meeting. Now to measure the revolutions of the top circle we can get

L = LCM(a, b)
Number of rotations of the upper circles = L / a
Number of revolutions of the upper circles = L / b

so the required answer is L / b;

Div 3 :

Problem 1 : Sansa and balances : math

Code : http://ideone.com/ff79AH
You just need to balance the torque of the given weights about the pivot.

Problem 2 : Ned Stark and Numbers : sortings

Code : http://ideone.com/626rzJ
sort the given digits in descending order and print the digits to obtain the largest number.