Блог пользователя usaxena95

Автор usaxena95, 7 лет назад, По-английски

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: sainathbatthala@gmail.com

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)

 
 
 
 
  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится +11 Проголосовать: не нравится

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.

»
7 лет назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please add questions to practice

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please add editorials of contest ASAP.