ashish1610's blog

By ashish1610, history, 6 years ago, In English

Little Red Riding Hood and Candy Factory

The problem basically asks to check if the integer is even or odd. As integer is very large you can check if last digit is even or odd to decide the ans. If the integer is even than the ans is YES else ans is NO

Little Red Riding Hood and Convolutions


Convolution(L) = L1*L2*L3*L4 + L2*L3*L4*L5 + ........
Since only allowed values for L[i] is 1 or -1, we can say that the number of terms (Li*Lj*Lk*Ll) which evaluates to -1 are equal to number of terms which evaluates to 1. So, if we negate the given list the number of terms which evaluates to -1 or 1 doesn't change and we get another list L' whose Convolution(L') = 0

An Unfair Fair Game


Greedy, O(k):
Lets start with simple greedy solution. Given n, subtract k, k-1, k-2 from n till the residue of number is between 0 to k. If the residue is non-zero, add the remaining number to the answer set, and report (k — the cardinality of the answer set).
Optimizing greedy to just count the cardinality, O(log(k)):
Observe that the numbers we are subtracting form a simple AP, {k, k-1, …, k-x}. The sum of this is S(x): k*(k+1)/2 — (k-x-1)*(k-x)/2. This is a strictly decreasing function in the range x = [1, k]. We can do binary search to find the first non-negative value of S(x). Let this value occur at x = z, answer is (k — (z + (s(z) == 0))).
Expected complexity : O(log(k))

Graph Sum


We have to support two queries, add a value to a vertex and print the subtree sum.
Finding the value:
  • if m is odd then no. of ways to form m by 2 and 4 is zero.
  • if m is even then no. of ways is equal to the no. of ways of forming m/2(let say R = m/2) by 1 and 2.
    which is actually SIGMA(i = 0 to R-1) ((R-i-1) Choose (i)) which is fibonacci number Fib(R)

Taking last 5 digits is nothing but mod operation with 105. Fib(R) repeats after 150000 when we take mod with 105.
Now add the (no. of ways) * m to every vertex in path from v to vertex 1(root). Use HLD to perform the query.
Expected Complexity : O(N*log2(N))
HLD Tutorial : Tutorial
Alternate way to solve the problem : grikukan's solution

Code Land


The problem statement reduces to this:
Given an undirected weighted graph and information of weights of every edge. Remove one bridge and add another such that the weight of the graph is maximized.
Lets see what the brute force solution for this will be. Lets try adding every edge and removing minimum weight bridge corresponding to that edge. The complexity of this solution will be O(n3).
Lets see how we can optimize this code.
Claim 1: Every bridge of the graph will be in ST.
Proof : Let say tree T is a ST of graph but there is an edge e (x, y) which is not in this ST. Now, as e is not in ST than there is no way to go from x to y (By definition of bridge. The bridge is the only way to reach y from x). That means ST is not connected and hence is not ST, Therefore every bridge of the graph has to be in the ST.
Now, we have a ST which contains all the nodes and all the bridges. Lets find the minimum weight bridge between every pair of nodes (n1, n2). Since, now we have a tree there is only one path from any one node to another, we can find this minimum weight bridge between every pair of nodes by doing n dfs.
Now, lets try out our original solution. Since, now we know the minimum weight bridge for every pair of node we can do the same solution in O(n2).
Final running time : O(n2)

Range Query


To solve this problem we will use MO's algorithm. If we have sorted our queries with MO's. We can than use range query and range update data structures to solve the problem. For any add or remove we need to update [A[i] — k, A[i] + K] and correspondingly we will add and subtract cnt of range [A[i] — k, A[i] + k] from our ans.
We need to use BIT rather than Segment tree (I tried with both and there was a huge difference between time taken to generate ans by both codes. I think the reason for this was recursion but not sure. If anyone know the exact reason please comment.).
Expected complexity : O(n*sqrt(n)*log(n))
Sources for MO's algorithm : Tutorial

If you find any issues with the editorials let us know. Thanks for participating. :)

Read more »

 
 
 
 
  • Vote: I like it
  • +29
  • Vote: I do not like it

By ashish1610, history, 6 years ago, In English

Hello Codeforces Community!

IIITD invites you to Procon 2015, the annual programming contest conducted as a part of our technical fest. We, the problem setters have tried our best to make problems of varying difficulty levels so that there is something interesting for every participant.

Time: The contest will be held on 8th August, 18:00 IST. See the time in your timezone here: link

Contest Details: The contest will be held on the codechef platform here: link

Problem Setting and Testing Team: Ashish Khatkar (ashish1610), Mohit Wadhwa (lifecodemohit), Ambar Pal (AmbarPal), Priyanshu Singh (tgamerz), Anmol Singh (kzanmos), Gaurav Rathee (garyclay08).
Special thanks to Kshitij Jain (kshitij_jain) and Rohan Garg (rohangarg) for their guidance and reviewing the problems.

Prizes: Only for Indian students
Cash prizes: INR 15000
Total Prizes: INR 25000

Hope to see a lot of participation!

UPD: Reminder, contest starts in less than 1.5 hrs.
UPD: Contest has already started less than 2 hrs to go.
UPD: Contest is over. Editorials will be published soon.
UPD: Editorials for all problems except Graph Sum is published. You can find them here
UPD: Editorial for Graph Sum is added.

Read more »

 
 
 
 
  • Vote: I like it
  • +52
  • Vote: I do not like it