usaxena95's blog

By usaxena95, 10 years ago, In English

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

Contest link

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

Our Fluxus 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)

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

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

We would like to have you feedback on the event: http://goo.gl/h3sHhP

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please can you publish the editorial for Shil and Suffix Palindromes ?

»
10 years ago, # |
Rev. 4   Vote: I like it +11 Vote: I do not like it

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.

»
10 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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

ans=ans+f(i)*dp[400][x][i];

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);

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add questions to practice

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They are already added. The links given are of practice only.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add editorials of contest ASAP.