We gladly invite all the programmers around the world to take part in the Pool B contests of "IPC ACM ICPC PREPARATORY SERIES"
This is a team contest (upto 3 participants in a team) of 5 hours each with ACM ICPC rules, organized on CodeChef.
You can read more about the contests, schedule, event format and rules from the previous blog post and website.
The Schedule of the Pool B contests is as follows :
| Contest by | Date and Time |
|---|---|
| Team Sataday | 31st Jan, 21:40 (IST) |
| Team Horcruxes | 3rd Feb, 21:00 (IST) |
| Team ForTheWatch | 7th Feb, 14:00 (IST) |
You can register for the contest at https://www.codechef.com/teams/register/IPC15P2A
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.
Update:
The leader board of the first contest can be found here. Congratulations Mateusz Radecki for a convincing victory, by solving one problem more than 2nd ranked team!
The second contest of the Pool B is going to start in less than 2 hours.
Update 2:
The leader board of the second contest can be found here. Congratulations Evgeny Savinov!
The third contest of the Pool B is going to start in less than 8 hours.
Update 3:
The leader board of the third contest can be found here. Congratulations kut_pioneer!
Interestingly first ranked teams of all the 3 contests solved a problem more than the 2nd rank teams. Awesome!
We will be releasing the editorials to all the problems soon and the list of teams selected to the finals will be released after the results of plagiarism tests are out.
Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).
Please, make problems submission to the system available after contest ends. I missed this option in former contests.
The fourth contest of the series has started here. I am the captain of the group who made this contest and I think that everyone should be able to find some problem they will like, so do participate.
Also, please read all the problems. It is possible that you can solve a harder problem more easily than an easier one.
Contest has ended. We will be publishing editorials gradually over the next couple of days.
All feedback on the problems, both positive and negative, is welcome.
Nice problems! How to solve Defense system ? The only idea that we could get is that if we add a new point, we translate the polygon, the new polygon will be two halves of the original and shifted polygon connected by tangents. But then, there is probability added to the problem too.
Let us ignore the probability aspect for now.
Just consider some set of points and try to find the convex hull such that all subset sums lie inside it. If you sort points by slope, then the lower half of the hull can be found by prefix sums of that sorted array. The upper half of that hull is just the same thing in reverse. If you go clockwise a point (x,y) contributes an edge (x,y) in the lower hull and (-x,-y) in the upper hull.
Now, problem reduces to finding area of polygon where each edge comes with some probability. Using linearity of expectation we can consider each edge individually. The total area can be expressed in terms of sum of triangles and rectangles.
It is easy to see an n^2 solution at that point. By storing a couple of values it easily reduces to n.
EDIT: here is my code
will you move problems to practice room?
Yes. I am trying to find out how to do that. As soon as I do I'll shift them.
please, do not forget to tell us where they will be available.
Problems have been added to the practice section. To view them simply remove the IPC15P2A part from the URL of the problem in the contest to get the link to the practice problem.
https://www.codechef.com/IPC15P2A/problems/SATA05 <--(contest problem)
changes to
https://www.codechef.com/problems/SATA05 <-- (practice problem)
Thanks a lot!
One more question though. Are you going to publish editorials? Same concerns former contests, authors always promised to publish them, but never did. Could you kindly fix this?
How to get the formula for "optimal reserve price" question?
Lets say you set some price x. The probability that you are able to sell the item is the probability that at least one person bid more than x.
pat least 1 more than x = 1.0 - pall less than x
What is the probability of one person bidding less than x? Since they pick their bid randomly it is x / 100. What is the probability of everyone bidding less than x? (x / 100)n.
pat least 1 more than x = 1.0 - (x / 100)n
Therefore, expectedprofit = x × (1 - (x / 100)n)
You need to find the maxima of that term. You can either differentiate it and get a direct formula or you can see that it is a bitonic function and ternary search for the answer.
I did not get to know of the contest.
What was the solution of the problem 'Modified Knapsack'?
Using Binary Search. For each r, we need check if there exists k items such that sum of values / sum of weighs is greater than r. We consider ci = vi — r*wi. Choose the k largest numbers and check if sum of them is greater than 0.
same idea was getting either wa(probably due to numerrical error) or tl for me. Could you show your code?
https://www.codechef.com/viewsolution/9272375 I found this solution which has implemented this idea.
On problem Lopymonials, I have an idea but can't fit in time. Multiply each l(i) with ci, then sum up. To compute ai, we just choose ci such that c1+c2x+c3x^2+...+cnx^(n-1) has n-1 roots :1,2,3,...,n excepts i.
The solution I had in mind while making the problem was as follows. If you write down the system of equations in matrix form AX = B (where X is the column matrix of coefficients) then you need to find A - 1. If you do that you can retrieve the coefficients of the lopymonial and therefore of the polynomial and then simply evaluate the polynomial at all the points.
To find the inverse required you to observe that the matrix you are trying to find an inverse of is the transpose of a matrix whose inverse you would find for polynomial interpolation. Now using Lagrange polynomials cleverly, you can find (AT) - 1 in O(n2). After that you can use the fact that (AT) - 1 = (A - 1)T to get A - 1.
However, during testing akashdeep also found a solution that used just Stirling numbers of the 2nd kind. I am not very sure what his method is so I won't comment on it.
I'll give a more detailed analysis in the editorial.
Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).
Will there be editorials for these rounds?
Yes.
When and where can I find them?
I can only say about round 2B. That is the one that took place today. Short editorials will be published within 2 days on discuss.codechef. I will share the link.
Thanks!
Still no editorials... When can we expect them?
Any update about the editorials? The problemset was very interesting, it would be a shame if people don't get to learn something new :)
Can someone explain the solution of Shil and LIS(Team Horcruxes IPC contest)?
What is assumed solution for Taxi Fare problem?
Is there any list of the teams who qualified to the final pool from the first pool? It is written in rule s that there must be 128 such teams, but I haven't managed to find the list.
We will be releasing it soon. Thanks for staying with us :)
How to solve COPSUM?
Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).
How to solve Biswa and Function in ICPC15C ?
Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).