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

Автор ajs97, история, 7 месяцев назад, ,

Techkriti 2017 and samsung research India brings forward International Online Programing Contest (IOPC) with a chance to grab your pile from INR 1,20,000. This is a rated contest of 3 hrs and will start at 15:00 IST on the 21st of April,2017. There is a little under 12 hours left till the contest starts.
The contest is hosted on codechef.

Contest page : https://www.codechef.com/IOPC2017.

Note that the contest is an individual rated contest on Codechef.

The problem setters are utkarshl, kaushal02 and dwivedi with triveni and dopahkiin as testers.

The prize distribution is as follows:
1.The international first,second and third get 20%,17% and 13% of total money respectively.
2.The 4th and 5th positions (international) get 10% & 8% respectively. positions 6-10 get 1.6% each.
3.The first, second and third in India get 10,8 and 6 percentage of total
4. In case if someone is eligible for more than 1 prize, he gets the larger one only.

Hoping for a huge response from everyone. May the Force be with you!

•
• +32
•

 » 7 месяцев назад, # |   0 Auto comment: topic has been updated by ajs97 (previous revision, new revision, compare).
 » 7 месяцев назад, # |   +126 We have not received the prize money from IOPC 2015.
 » 7 месяцев назад, # |   0 The codechef contest drop down list says Techkranti — IOPC 2017. xD
 » 7 месяцев назад, # | ← Rev. 2 →   -35 Where does this fail for this problem ? I just simulated everything using segment tree.
•  » » 7 месяцев назад, # ^ |   0 segment tree is not required.Its just basic recursion. Its a variant of standard version of Josephus problem. Code``````ll compute(ll n,ll k,ll orig,ll sign){ if(n==1) return 1; if(sign==1){ ll val=compute(n-1,k+orig,orig,0); val-=1; if(val==0) k--; else k+=val; k%=n; k+=n; k%=n; val=k; //cout<>t; while(t--){ ll n,k; ll sign=0; cin>>n>>k; if(k>0){ sign=1; } if(k<0){ k*=-1; sign=0; } cout<
•  » » 7 месяцев назад, # ^ |   0 get_ac function takes int k, while it overflows in main — various similar mistakes like this. I just simulated everything using BIT and it worked fine.
•  » » » 7 месяцев назад, # ^ |   0 Nothing would overflow. i have #define int long long in the code.
 » 7 месяцев назад, # |   +5 How to solve Christmas Time?
•  » » 7 месяцев назад, # ^ | ← Rev. 3 →   0 Read up on [Partition Function](https://en.wikipedia.org/wiki/Partition_(number_theory)#/Generating_function). You can calculate P(n) in O(sqrtN) using generalized pentagonal numbers. Then query for N, M reduces to range product of P(i), for i over the range [M, M+N-1] which you can do in O(1). Overall time complexity is O(NsqrtN + Q).
•  » » 7 месяцев назад, # ^ |   0 Let A(n) be the number of ways to distribute n sweets . Then A(n) = A(n - 1) + A(n - 2) - A(n - 5) - A(n - 7).... i.e where X(i) is the ith pentagonal number. Rest is just building prefix product of this array.
•  » » 7 месяцев назад, # ^ | ← Rev. 2 →   0 My solution with space complexity passed in Java. Was this expected or the time limit was bit too relaxed for Java?
 » 7 месяцев назад, # |   +3 Can someone please explain the approach for https://www.codechef.com/problems/IOPC17G/
•  » » 7 месяцев назад, # ^ | ← Rev. 4 →   +3 See this code — https://www.codechef.com/viewsolution/13376017 If the intervals intersect, it is the right end point of the interval that ends first. Else, let [a,b] be the first interval and [l,r] the second with b (a-1)/x=(a-1)/x, so there is no need to check x'. So from a given x we need to check only next smaller number x' such that b/x' or r/x' is different. This is a major optimization since there are only O(sqrt(r)) different r/x. So, from a given x next x' = max(r/(r/x+1),b/(b/x+1)). Complexity = O(sqrt(r)) for a test case.
•  » » » 7 месяцев назад, # ^ |   0 Thanks.