In the interest of learning a bit about Codeforces' Polygon and Gym services, I have set up and made available a contest that I worked on a few years ago. The contest was created with the help of Richard Peng, Danny Sleator, Dennis Matveyev, and Krzysztof Onak.
I believe the average problem difficulty should be relatively easy for strong teams although there's at least one fairly tricky problem in the set. Good luck!
As an aside, this contest actually has a bit of a story behind it:
This was an invitational contest hosted by the University of Michigan during the 2011-2012 ICPC season. With help from the contests' sponsor, Jump Trading, we were able to invite several of the teams from around our area for a contest prior to regionals.
While I personally found the logistics of setting up such a contest a bit frustrating to manage, lucky for North America, one of the teams we invited was the University of Chicago coached by Borja Sotomayor. Running with the idea, Borja has created something much bigger and much more meaningful with the NAIPC contests (which many of us hope will become an official NA super regional) from the past three years (thank you Borja and everyone else involved!).
You can check out these past NAIPC contests at the links below
http://icpc.cs.uchicago.edu/invitational2012/
http://icpc.cs.uchicago.edu/invitational2013/
http://naipc.uchicago.edu/2014/
Anyway, enough story time. Good luck solving problems! (And see if you can spot all the Pixies references)
For NAIPC 2014, where can I see the time limits for each problem?
I cannot seem to find the time limits listed anywhere either. However, the time limits for the practice contest were all 5 seconds and I suspect it's the same here. I didn't see anything about memory limits.
It looks like the data and judges solution link was never updated. These were released and are available at http://serjudging.vanb.org/?p=666
Any hints on solving A. My current strategy is to use a Fenwick tree. For each number P in the permutation, I count the number of crossing by summing how many numbers greater than P. But I already got dozens of WA. There's something wrong in this idea ?
Looks like you aren't calculating the elements of P correctly.
The number should be calculated as: (A * i + B) % N. As it can increase a lot and causes overflows, it's necessary to check whether it resulted in an overflow, then it should be summed with N and then, the 'mod' calculated again. What is the pitfall in this calculation ?
When your calculations overflow it wraps the result modulo 2^32. It will not still be correct modulo N. Use 64 bit arithmetic.
Another solution to A. is to count inversions in the sequence
sobtained by sorting{0, 1, ..., n}using the comparatorx < y if ((a * x + b) % n) < ((a * y + b) % n). A modified mergesort finds the answer inO(n lg n).Could someone give me a hint for problem E (spies)? At the moment the best I got is a brute-force, obvious solution which is easy to make it fall on TLE and a "smarter", wrong solution, but I have no idea on how to count the number of legal arrangements in a more clever way :(
The best hint I can give is to think about the problem as a graph where cities are nodes and spies form edges. Think about what connected structures have solutions and how many solutions each has. There's a couple cases.
Thank you :)
Thanks for making this contest available in CF GYM!
Is there a way to virtually participate NAIPC contests?
i can't solve the problem "I — Yawner" with a lot of thinking. help?
There is a very detailed explanation on Petr's blog. Link!
thanks.
I was trying to solve problem D finding the smallest rectangle formed by each pair of red points, but I'm getting WA-1, can someone help me?
I can't understand why my solution fails.
I guess is a tricky test which I can't found.
You can't describe rectangle by 2 red points only. Suppose that you have points (0,0), (5,10), (5,-10), (10,0) and want to build smallest rectangle which covers all 4 points.
I noticed that.
I tried generating all possible subsets of exactly required red points size, find minimum enclosing rectangle for these points and verify it not contain blue points.
Still WA-1.
I can figure out a complete search solution trying all possible rectangles but I think is too slow.