FLUXUS — IIT Indore & Programming Club, IIT Indore are proud to announce the third edition of Divide By Zero!
It will be an ACM-ICPC style contest with all problems visible from the start and no hacks.
Details :
Date : 29th March 2015
Time : 2130 to 0130 IST Official Time Announcement
Programming Partner : Codechef
Prizes
This time we are giving away prizes of worth ₹ 10,000/-
Indian Winners
Top 25 Indian winners will get special Limited Edition Fluxus T-Shirts
In addition to T-Shirts, Top 3 Winners will also be getting Cash Prizes & Goodies
Non-Indian Winners
CodeChef will be sponsoring 3 T-Shirts to the Top 3 winners
Finally, don't forget to register at FLUXUS as Prizes are only applicable to users with a Fluxus-ID
Also, we would like to thank our problem setters and testers:usaxena95, aditya1495, harshil, gaurav708
Do share it with your friends who are interested :D
For more details / contact details, visit:
Our Facebook Event Page
Or mail us at: [email protected]
EDIT: Due to huge response, our chefs have decided to add a few more delicious dishes and to extend duration of the feast to 4 hrs! :)
So please note our new timings:
Start: Mar 29 at 9:30pm (Remains same)
End: Mar 30 at 1:30am (Extended)
We would like to have you feedback on the event: http://goo.gl/h3sHhP
Please can you publish the editorial for Shil and Suffix Palindromes ?
We will be publishing the editorial asap.
Problems have been added to practice.
We will be be adding the editorial soon. Until then you can try joining the pieces by these short description and tags:
Utkarsh and LCM: Adhoc/cake walk/simple combinatorics
Shil and the Toy Factory:easy/ Binary Search (on time)
String Match: easy-med/ Z-Algorithm/ KMP Failure Function(String Automata)
Shil and Triplets: easy-med/ DP, Tree, Combinatorics
Utkarsh Lost in Cities: Med-hard/ Graph Theory, Maths, Matrix Exponentiation, Divide and conquer(for calculating GP of Matrix)
Complexity =O(N^3 * Log^2 K). Also O(N^4 * Log K) without Divide and Conquer by karanaggarwal
Shil and Suffix Palindromes:Hard/ Palindromic tree, Link 1, Link 2
Utkarsh and Long Roads:Hard/ Polynomial Exponentiation, Divide and Conquer.
Complexity =O(L*L*Log^2 K) by xorfire. Faster O(L*Log(L)*Log^2 K) with FFT but I thought it would have been an overkill for a short contest.
If you have different solutions you can discuss here. We would be very happy to know them.
One more way of solving Utkarsh and Long roads
let wt[i] indicate the number of occ of i
observation 1:
you can get stack size to be greater than 400 let us say x if you have atleast x-400 zeros so now let dp[i][j][k] -> using the first i values(1 to 400) , have the sum to be j and use k elements. Fill till dp[400][400][400]; can be done in O(400*400*400*log(400)) time..Runs within a sec in my vm.
Now when given a query what you need to do is add the number of ways such that size <= k that are created due to zeros let y=wt[0];
iterate i from 0 to min(k,400) -> indicates the stack size formed from elements other than 0
let n=k here f(0) = nc0*(y^n)+ n-1c0*(y^(n-1)) +.... f(1) = nc1*(y^(n-1))+n-1c1*(y^(n-2)) +.... we get f(i)=((n+1)ci*(y^(n-i+1))-f(i-1))/(y-1);
Please add questions to practice
They are already added. The links given are of practice only.
Please add editorials of contest ASAP.