adurysk's blog

ICPC Preparatory Series (Pool B) — Cool Prizes to be won!
By adurysk, history, 9 years ago, In English

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 byDate and Time
Team Sataday31st Jan, 21:40 (IST)
Team Horcruxes3rd Feb, 21:00 (IST)
Team ForTheWatch7th 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.

  • Vote: I like it
  • +78
  • Vote: I do not like it

Comments Comments (36)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Please, make problems submission to the system available after contest ends. I missed this option in former contests.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it +10 Vote: I do not like it

      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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    will you move problems to practice room?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes. I am trying to find out how to do that. As soon as I do I'll shift them.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        please, do not forget to tell us where they will be available.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          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)

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            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?

            → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

How to get the formula for "optimal reserve price" question?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it -23 Vote: I do not like it

I did not get to know of the contest.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the solution of the problem 'Modified Knapsack'?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Will there be editorials for these rounds?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yes.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        When and where can I find them?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks!

            → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            Still no editorials... When can we expect them?

            → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            Any update about the editorials? The problemset was very interesting, it would be a shame if people don't get to learn something new :)

            → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone explain the solution of Shil and LIS(Team Horcruxes IPC contest)?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is assumed solution for Taxi Fare problem?

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We will be releasing it soon. Thanks for staying with us :)

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve COPSUM?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Biswa and Function in ICPC15C ?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by adurysk (previous revision, new revision, compare).

→ Reply