We gladly invite all the programmers around the world to take part in the " IPC ACM ICPC PREPARATORY SERIES "
Yes! There is Huge cash prize at stake!
This is a team contest (upto 3 participants in a team) of 5 hours each with ACM ICPC rules, organized on CodeChef. This is a unique series of 12 contests, where there is a separate cash prize for the problem setters as well. There are 9 problem setting teams consisting of around 7 problem setters each. Problem setting teams compete among themselves to make better problem sets.
Cash Prizes
For the final winners in rest of the world category:
- 1st Prize: $1000
- 2nd Prize: $500
- 3rd Prize: $200
For the final winners in Indian category.
- 1st Prize: INR 50,000
- 2nd Prize: INR 25,000
- 3rd Prize: INR 10,000
Eligibility Criteria
The IPC programming series, though aimed at ACM ICPC aspirants, is not limited to them. Anyone who wants to try their hand at the problems from some of the finest programming minds in India can do so. Yes! It is open to all the programming enthusiasts across the globe.
Registration
You can register for the contest at https://www.codechef.com/teams/register/IPC15P1A
To know more about what IPC is, and for further details about schedule, event format and rules, please visit https://www.codechef.com/ipc/2015
UPD1:
With a lot of twists and turns in the leaderboard, the first contest of the series has concluded with the team sequoia winning! Congratulations! The complete leaderboard is available here. The problems can be seen here. The editorials are available here.
UPD2:
The second contest of the series will be starting in less than 22 hours!
Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).
Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).
dis luks awsum
Exciting.............
We are allowed to use only one computer to write code right ?
Its not mandatory to use one computer, you can use multiple computers.
I keep in mind the fact that organizers can't check that every team is using only one PC, and also I understand that it sounds fine to use multiple computers when teammates are participating online from different places, but if you mean "multiple computers at the same time" — what is the point in preparation to ICPC while practicing some contests which are completely different from ICPC? You can't use multiple PC at WF and at most of regionals/qualifiers.
Maybe removing prizes from the contests and imposing the one computer a team restriction would ensure that the teams do the contest sincerely and don't use multiple computers.
What is the estimated difficulty of those problemsets (both eliminations and finals)?
This is a hard question to answer. Though we did not put any limit on how much hard the hardest question should be, we tried to see that there is good gradient in the difficulty of the problems and that there is good variety in the topics. We also tried to ensure that the problems are genuine and not easily searchable on google.
The teams which are making the problem sets have wide variety of people ranging from green coders in CF to past ACM ICPC World Finalists.
So, you should be expecting some, if not, more challenging questions in both eliminations and finals! :)
My submision on Magical Strings getting TL. (I used DSU structure in my solution.) What is intended solution? Or how can I speed up my solution to meet TL.
You need to process all palindromes with the same center together, i.e. for each center you only need to know the maximum radius of the palindrome with that center. Our solution.
agree. For this reason I had added this piece of code.
I thought that marking just processed part of palindrome and not repeating it is enough... somehow can not get why this is not the same to what you are saying...
After removing additional log(N) factor (which appears because you are using sets instead of straightforward true/false tables) from your solution it passes in 0.7 seconds.
I don't really understand the rules. Is $1000, $500, $200 the prize for today's contest or the whole series?Nevermind, I can see now that the prize is for the whole series
The prizes $1000, $500, $200 are for the top 3 spots taking into consideration of the cumulative score of the final 3 contests, and not for the first 9 contests. The first 9 contests serve as the elimination contests to the finals. Sorry for the inconvenience.
Please check https://www.codechef.com/ipc/2015 for all the details regarding the contest series.
problems are not available in practice. I keep getting this message "Problem is not visible now. Please try again later."
They have been. Can you check again and if it still does not work, send me a snapshot of what you get?
it works now for me. Unfortunately, I do not remember the text of the message. :(
The last problem was nice, thanks. But the previous problems could have been harder, I think :)
The competition between problemsetters is an interesting challenge, I've never seen this before. I'm just curious, how do you plan to rank the problem setting teams? Will it be some voting, or maybe some criteria based on the final standings of each contest?
The last problem was supposed to be easy-medium and we expected a lot more ACs on it before the start of the contest :P Thanks for the feedback.
Yes, we are planning to use voting from a selected pool of people. Rating will consider the following in that order, most important one at top:
You can refer this, this, and this to know about how we started this initiative :)
How to solve "Max Subarray GCD" ? The editorial doesn't help much . Thanks in advance :D
I solved it using binary search + sparse table — http://ideone.com/54qCmX :)
Hi , i am the author of the problem and here is the expected solution
We can perform a binary Search on answer
Now we just need to write an efficient check function
Now suppose we want to check if any subarray of size 'X' exists which has GCD >= K , To do this , we divide the array in blocks of size 'X' and calculate the prefix and suffix GCD for each block , this will help us calculating the GCD of any block of size 'X' in O(1) time with O(N) pre processing.
The complexity of this solution is O(N * LOGN * P) where P is time taken for calculating GCD
http://ideone.com/UKdXBa
It was really helpful , i think it would be really awesome if the problem authors themselves would have written the editorials and uploaded them on codeforces too, apart from codechef as the forum here is more active :)
I am the leader of team "BlundersPride" who have set the second contest of the series. There are some nice problems which you might enjoy. A lot of effort has been put to prepare the contest and editorials.
Some trivia: the team name is derived from this certain brand of Indian whisky!
Any possibility the contest could be moved to avoid collision with COCI#3? COCI has been scheduled for that time slot for a long time now.
Oh, we didn't know this when making the schedule, else we would have definitely tried to avoid the clash. Now, we think it's too late to shift the contest to another day, and shifting it by 1 hour or more will be too late in the night for Indian participants.
So, contest has been on for around 4 hours. The problems are a little tougher than we had expected them to be. One problem is still unsolved.
Team FacelessMen and sokian and Team ptnk1316 have solved 6 each.
Team zenith_vn(ngfam_kongu, I_love_Hoang_Yen) and Team aimfund(zeliboba, yarrr, ValenKof) have solved 5 each.
Contest has been extended due to a jury mistake in a problem. It is open till 3:00AM IST.
zenith_vn = ngfam_kongu + me
What is the solution of problem KingTour?
The best I could think of was a matrix exponentiation solution with each matrix of dimension 400*400. Other people seem to have used a solution where the matrix was 100*100.
You don't need all 400 states. Since the field is symmetrical, instead of saying we are i cells from the right border, we can say we are m — 1 — i cells from the left border (0-based).
So you can do i' = min(i, m — 1 — i), j' = min(j, m — 1 — j), which brings the size of the matrix down to 100. You can also swap i' and j' if i' < j'. The size will be <= 55 then.
KingTour can be solved easily by using this awesome trick explained by misof. :)
How to solve "counting zigzag sequence" and "queries with pairs"? BTW, the problems were really great , thanks for that :)
The editorial for Queries with Pairs is available: Editorial.
For Counting Zigzag Sequences, you can maintain a Hashmap with < val, state > as keys, corresponding to last element of the sequence (and the count of all such sequences as the value for that key). States can be 0,-1 or 1 0→ odd element , 1→ even element (x+1) , -1 → even element(x-1).
You can update the Hashmap while traversing the array. The complexity of this solution would be O(NlogN)
Thanks for your reply . Sorry, i couldn't understand your approach for "Counting Zigzag Sequences" completely . Can, you please explain the state transitions in a little more detail :)
Have a look at this solution, coded by zenith_vn. It's neat and concise and you can understand the transitions easily. We'll be uploading the editorials today as well. Solution
It helped. Thanks .
I've solved three problems already, but now when I'm trying to submit next one — I am receiving "You are not allowed to take part in this contest. You may need to contact the contest admin to give your permissions." message. Something went wrong?..
Upd. Seems to be working fine now :)
That awkward moment when you can either solve a problem or simply submit some naive solution in Java and get AC — I'm really curious about motivation behind setting TL to 6 seconds for this problem (with Java and that strange non-ICPC multipliers for bad languages rule it becomes 12 seconds).
Also I like these formally correct constraints, MOD<=100000 — when it is even <=10000 in fact :)
Now I am waiting too see editorial for PSEQ, in order to know — is it fine that exhaustive search without any prunings and breaks runs in 0.2. I was a bit surprised :) I have no idea about its complexity, but it sounds risky.
"multipliers for bad languages" :( feelings have been hurt
I was the author of the problem PSEQ. The expected solution had a time complexity of around 3^7*600 . Exhaustive search was supposed to TLE but sadly it passed. Regarding the TL set in MODQ we had tested for bruteforce solutions in C++ and it was TLE'ing but had no idea that with Java even a bruteforce solution would pass .
Using the fact that number can't have more than one prime divisor larger than
and running dp where state is described by mask of primes up to 17? Thanks for a nice problem :) Sadly, most of teams used different approaches.
Moreover, some solutions are using straightforward greedy heuristic, which is obviously wrong.
A test:
Answer for it is 3, not 2 :)
Yes that was the intended solution . Unfortunately i could not take into account all the greedy approaches :( and set appropriate input . I however hope that you liked the problemset :). Is there any input for which the bruteforce solution will TLE ? If yes how to generate one ?
It depends on bruteforce you are using :)
I have no idea how easy to crack smart solutions are; however, I submitted most naive one, which doesn't stop searching even after finding perfect solution. As a result, for test consisting of two copies of every product of two primes below 150 I got
I'll not even try to wait while it will compute answer for worst possible case — for my solution it is simply set of all numbers which have more than 1 prime in factorization.
There were cases where i had used all the numbers from 2 to 300 twice. But all bruteforce solutions solved it within 1s.
Naive optimization: whenever you see a number which has only 1 prime divisor, you can take it safely (unlike more general "sort them by number of primes and pick greedily", this one should be fine — because removing this number from your answer may give you space for no more than 1 other number).
I used it, so for your test my solution picked all primes in range 2..300 first of all, and then had nothing more to do :) But if you'll remove primes (and their squares, cubes, ...) — it will make things much worse for this particular implementation.
Once again, such straightforward tests are still easy for bruteforces with at least basic optimizations, and it feels like well-optimized bruteforces may work fast on all possible cases, but I have no idea how true it is.
Bruteforce(with slight precomputations) passes even in C++ for MODQ....
Solution
I am curious why the constraints of good rectangle were set to 1<=n,m<=1e5 and then have no case with n=1e5,m=1e5,k=1.
The answer for that case will exceed 64 bit integers and should have been put in the test cases. Our solution used long doubles and was giving some small error for that case and solutions printing (ll)round(ans) will also give wrong answer.
String swap 2 was a copy of a problem C in cf round 276
In Grid Game how to check whether the xor of x, x+2, ..., x+2m-2 is 0 or not .
If x is odd, then each number above has last bit 1, so their XOR will have last bit 0 or 1 depending on m. If x is even, then each one of them is even so, last bit of their XOR will be 0.
Now, write them like y, y + 1, ..., y + m - 1, where
(integer division). Now, this is a contiguous range of numbers. Can you find xor of numbers 1, 2, ...N in 
.
How to calculate xor in O(log N) . Sorry, i'm unaware of the concept :(
You can count parity of 1's at any place/position easily. One straightforward idea is to use digit dp. I think there might be observation based recursive kind of solutions too.
when will the editorials be published of 2nd and 3rd contest ??
For the second contest, 6 out of the 9 editorials are done and you can find 4 (other two will be available by morning) of them here. The other three will be available very soon.