Aparoksha is back with the flagship coding event — Alkhwarizm
2 years back, we launched the first ever External Rated Contest on Codechef — Alkhwarizm 2017.
Last year's Alkhwarizm 2018 was a great success with over 1100 people participating in the contest.
If you have the appetite for algorithmic problem solving, then don't miss it out!
Contest link is here — Alkhwarizm 2019
It will be a 5 hour individual contest with algorithmic problem-set of diverse nature, and is open for both students as well as professionals.
The contest will comprise 10 problems, and will be rated for both divisions.
The prizes include cash prizes worth INR 20,000, along with Codechef Laddus.
- For Indian participants:
- Top 10 from ranklist will receive 300 laddus.
- Additionally, they get bonus laddus (Bonus = n — contest rank) where 'n' is 11 for short contests.
- For Global participants:
- Top 10 from ranklist will receive 300 laddus.
- Additionally, they get bonus (Bonus = n — contest rank) where 'n' is 11 for short contests.
- For combined participants:
- Random Laddus to any 5 users: 200 laddus.
- First to solve each problem individually: 100 laddus.
- Country wise participation: Top 10, 20 and 30 will get 30, 40 and 50 laddus as per participation.
- Country wise performance: 200, 250, 300 laddus as per performance.
So be ready to have a nail-biting experience on April 7, 2019 at 21:00 IST
The problem have been set and tested by satylogin, blake_786, shivamg_isc, priyanshupkm, modi_aashu2 and fLUKEmASTER.
Some of our previous contests — CodeRed 2019, Alkhwarizm 2018, CodeRed 2018, Alkhwarizm 2017, and HumbleFool Cup 2016.
Register here to be eligible to sit on the Iron Throne.
Good luck everyone !
Upd 1 — The contest is about to begin in 1.5 hours.
Upd 2 — The contest is over. Thanks for the huge participation.
And we are sorry for this unbalanced contest.
The initial version of the contest was perfectly balanced. But, each problem of external rated contest has to be reviewed by few people from Codechef.
The initial version of the contest was told to be made rated just for Div 2.
The problem right now with 3rd least number of submissions was marked by them as an EASY-MEDIUM problem, and similarly were the others.
We tried to convince them to make the contest rated for all, as we felt the contest was indeed balanced.
But, finally in order to make the contest rated for all, we had to add harder elements to most of the problems.
We in a way could have agreed to keep the contest rated for just div 2, but that would remain unbalanced for them similarly.
We are sorry again, but please try to understand that the error was not on our part entirely.
Thanks !
The hints will be posted soon.
Upd 3 —
The hints are as follows —
Danny Wants To KnowProblem Setters — modi_aashu2, fLUKEmASTER
Was a Cakewalk Problem. Just sum up the values $$$(A[i]*B[i])$$$ in the range $$$[L,R]$$$.
Weirwood TreesProblem Setters — modi_aashu2, fLUKEmASTER
The track of top,bottom, left and right nodes can be kept in the start.
No of edges = $$$2^{(n + 1)} - 2$$$, Top = $$$1$$$, bottom = $$$2^n$$$, left = right = $$$n + 1$$$, Where $$$n$$$ is the depth.
In every query of “1 x” type, the variables can be updated as follows.
If it is a top query, then the no of edges = 2*no of edges + top. And newtop = bottom, newleft = 2*left, newright = 2*right.
If it is a bottom query, then the no of edges = 2*no of edges + bottom. And newbottom = top, newleft = 2*left, newright = 2*right.
If it is a left query, then the no of edges = 2*no of edges + left. And newleft = right, newtop = 2*top, newbottom = 2*bottom.
And if it is a right query, then the no of edges = 2*no of edges + right. And newright = left, newtop = 2*top, newbottom = 2*bottom.
Finally at every query of type “2”, display the no of edges stored.
They are COMINGProblem Setter — shivamg_isc
Through DFS(Single Source Shortest Path), compute the minimum distance required to reach all the N nodes using specific number of edges.
$$$dis [ i ] [ j ]$$$ = distance to reach from node 1 to node $$$i$$$ using $$$j$$$ number of edges.
Now for each node $$$i$$$, we can form linear equations of form $$$y=mx+c$$$ for each edge.
Where, $$$c=dis[i][j]$$$, and $$$m=j$$$.
Whenever in queries, the weight of all edges gets changed to a value $$$VAL$$$,
then for each equation $$$y = j*VAL+dis[i][j]$$$.
Now, we need minimum value among all equations corresponding to a node, which can be done using Convex hull trick.
Arya and the Grid of StarsProblem Setter — modi_aashu2
Can be solved by 3D $$$DP(i, j, k)$$$, Where $$$dp[i][j][k]$$$ is the number of stars collected while going from $$$(i, j)$$$ to $$$(i, j + k)$$$. Note that $$$i$$$ and $$$j$$$ range from $$$1$$$ to $$$1000$$$ and $$$k$$$ ranges from $$$1$$$ to $$$X$$$.
All the ways to go from $$$(i,j)$$$ to $$$(i,j+k)$$$ are of the following form:-
Going rightways to some point, then going down till $$$(m, n)$$$ and coming back up to some point in $$$(i+1)^{th}$$$ row, and then entering $$$i^{th}$$$ row and moving left till we reach $$$j+k$$$.
Assume the point at which you start going down as $$$(i, a)$$$ and the point when you come back to $$$i^{th}$$$ row as $$$(i, b)$$$.
Now, we can go from $$$(i,j)$$$ to $$$(i,a)$$$ then go one row down to $$$(i+1, a)$$$, now complete the journey and reach $$$(i+1, b)$$$ which is equal to $$$dp[i+1][a][b]$$$, then move back to $$$i^{th}$$$ row and return to $$$(i,k)$$$
This can be computed in the following way:-
$$$dp[i][j][k]$$$ = Max($$$dp[i + 1][a][b]$$$ + no.of stars from $$$(i,j)$$$ to $$$(i,a)$$$ and $$$(i,k)$$$ to $$$(i,b)$$$) for all $$$a$$$ in $$$j$$$ to $$$(j + x)$$$ and $$$b$$$ from $$$max(k, a)$$$ to $$$(j + x)$$$.
The final solution is stored in $$$dp[0][0][0]$$$.
Winter Is HereProblem Setter — priyanshupkm
Precompute the number of divisors of all $$$B[i]$$$’s and store it in $$$C$$$.
Now we calculate XOR of all $$$C[i]$$$ such that $$$L \leq i \leq R$$$ and $$$A[i] \leq K$$$. This can be done using Merge sort tree where we sort each node according to the value of $$$A[i]$$$ and $$$C[i]$$$ are automatically arranged along with it.
On each node we store prefix XOR of all numbers appearing before the given index and calculate the answer using merge sort tree query.
Once we have $$$X$$$ = the XOR of all $$$C[i]$$$'s corresponding to the query.
We need to find how many elements in that range have values = $$$X$$$, as removing this value will make the resultant XOR = 0 .
This can be done by storing for each node in Merge Sort Tree the index ranges that need to be answered for a value.
As total number of elements in the Merge Sort Tree is just $$$N \, log (N)$$$, we can answer all queries by traversing all nodes of the Merge Sort Tree exactly once, and finding put the contribution made by each node for any query.
Cersei and her SoldiersProblem Setter — fLUKEmASTER
This problem can be approached as a normal vertex cover problem on a binary tree with an extra restriction that nodes from all classes ($$$1$$$ to $$$k$$$) should be considered.
This extra constraint can be handled by introducing an extra state in the naive solution for vertex cover of a binary tree.
This state could be a mask for all the classes which are to be found in the subtree of a node.
Hence, the final states could be $$$dp(node)(mask)(parent)$$$.
To compute the value of a particular state, we need to divide the mask between the two children for the node.
The net complexity of the code would be lesser than $$$O(n*2^{2k})$$$.(Think why?)
Game of TheoryProblem Setter — blake_786
Consider a DS which supports following function:
Insert a pair $$$(x, y)$$$.
Given a pair $$$(x, y)$$$ , find number of pairs $$$(x_i, y_i)$$$ such that $$$x_i \leq x$$$ && $$$y_i \leq y$$$.
Given a pair $$$(x, y)$$$, find sum of all $$$y_i$$$ ’s of pair $$$(x_i, y_i)$$$ such that $$$x_i \leq x$$$ && $$$y_i \leq y$$$.
Given a pair $$$(x, y)$$$, find sum of all $$$x_i$$$ ’s of pair $$$(x_i, y_i)$$$ such that $$$x_i \leq x$$$ && $$$y_i \leq y$$$.
For every node $$$q$$$, we have to consider only the ancestor of node $$$q$$$.
While traversing using DFS, if we update the points of all ancestor in the DS then we can calculate the sum by making $$$v$$$ fixed and breaking the equation $$$min(max(A_u, A_v), max(B_u, B_v))$$$ into different cases on the basis of value of $$$A_v$$$ and $$$B_v$$$.
To maintain such DS we can compress the $$$A_i$$$ ’s and $$$B_i$$$ ’s.
Consider a BIT tree such that each index of BIT tree is itself a segment tree part.
Now to update a pair $$$(A_i, B_i)$$$, update with starting index $$$A_i$$$ of BIT and for every update index in BIT update the segment tree with $$$B_i$$$.
Our Enemy does not TireProblem Setter — shivamg_isc
This representation of bases and numbers can be changed to a simple grid of dimensions $$$(X+1)*Y$$$.
We can form a matrix $$$M$$$ of dimension $$$Y*Y$$$, such that $$$M[i][j]$$$ denotes the number of ways to go from $$$(x,i)$$$ to $$$(x+1,j)$$$, if entire row $$$(x+1)$$$ doesn’t contain any obstacle.
Let’s say we have the answer till row number $$$x$$$, then if $$$(x+1, x+2,.......x+a)$$$ are empty, we can apply Matrix Exponentiation of $$$M^a$$$ to compute the answer for row $$$(x+a)$$$ directly.
Now, for those cases where some row $$$x$$$ has certain obstacles, take the matrix obtained above from matrix exponentiation, compute DP in $$$O(Y^2)$$$ to frame new transitions for such row to obtain the new DP array for row number $$$x$$$.
Once you obtain this DP array for a non empty row x, apply matrix expo again upon this temporarily obtained matrix with a factor $$$a$$$, such that $$$(x+1…..x+a)$$$ are empty. Matrix precomputation will take $$$O(Y^3 log X)$$$.
Also, for these 200 rows, the computation has to be at max this complexity via optimisations — $$$O(200*Y^2*log(X))$$$. (observe $$$Y^2$$$ in the complexity- this has to be toned down from $$$Y^3$$$ of matrix expo. How?).
Conquer Beyond the WallProblem Setter — satylogin
The problem consist of 2 parts, $$$1^{st}$$$ is selecting the nations that have influence greater than dream influence.
For that we can use rotating calliper as the farthest points will lie on the convex hull formed by the set of points (can be proved by method of contradiction. Will add the proof in details editorial).
Ones hull is made, one can use the rotating calliper technique to calculate the max distance.
After that The convex hulls that have max distance greater than dream value, they can be transformed into lines by projecting their shadows on $$$x$$$ axis.
After that one can use sweep line and maintain the frequency of the symbols. That can be used to check whether the name can be formed or not. Among all the events, one has to choose the one with minimum set.
The sweep line will work slightly different, as we not only have to check on line edges, but between them, as even touching the line means that we have to take that, and we have to find the smallest subset.