kingofnumbers's blog

By kingofnumbers, history, 8 years ago, In English

Hello CodeForces Community!

After a series of four ICPC regionals in India (Amritapuri, Chennai, Kharagpur, Kolkata), the top teams from the respective regionals have been shortlisted and they will now compete at the final leg of the ACM ICPC Asia India regionals — ACM ICPC India Final 2016. Over 90 top teams have geared for the Final which makes it an exciting battle to watch. My best wishes to all the teams who are competing tomorrow.

Further, I would like to invite you all to the parallel mirror contest which will be take place at ACM-ICPC Asia — India Final Onsite Mirror Contest.

For those who are preparing for the ICPC onsite regionals this would serve as an ideal platform to practice as it would simulate the real onsite contest.

Contest Details

Time: 30th December 2016 (1100 hrs) to 30th December 2016 (1600 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: https://www.codechef.com/INF16MOS

Registration: You just need to register as a Team on CodeChef. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Good Luck! Hope to see you participating!!

Note: The mirror contest will run in parallel to the main contest with an hour delay.

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

»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Problem B is the same as https://www.codechef.com/problems/VALMAX. And the same bruteforce solution can pass.

  • »
    »
    8 years ago, # ^ |
    Rev. 9   Vote: I like it +18 Vote: I do not like it

    Constraints were N = 100000 and K = 1000. Are you sure brute force will pass? The expected solution was a not so trivial Tree DP in which you process nodes in increasing order of their tin values. Can you show the bruteforce code which passes?

    P.S : I don't think the problems are similar. For the problem you linked to, your own solution is O(N2), where as today's B had an O(NK) solution.

    P.P.S : I checked out your AC Code and it seems O(N * min(K2, N))) is passing. This was not intended. It is because of slightly weak test data (I am not sure what I did wrong, since I added all edge cases/ stress tests. I am not fully sure how to break your code since you're taking min of k + 1 and the current subtree size at each edge of the tree). Luckily, we got only one such hacky solution today in the actual contest in the 299th minute, by a team who was 2nd already and they remained in 2nd place, so there was no net affect in the RankList! The other accepted ones were optimal solutions.

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

      Can you elaborate on your tree dp idea? Couldnt come up with anything better than

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 3   Vote: I like it +28 Vote: I do not like it

        Sure.

        First lets' compute tin and tout for each node by doing a DFS.

        Our DP State will be DP[x][i] =  Best i sized subset we can make using all nodes y which satisfy :

        • 1 ≤ tiny ≤ toutx
        • y does not lie on the path from CEO to parentx.

        We're looking for DP[CEO][K].

        When we're at node x, we'll make a copy of the DP array we already have and pass it by reference to its children. Then we can merge the childrens' answers with x's answer because for each size k, we have only two options :-

        • Choose x and reject all of its' descendants
        • Choose descendants and reject x.

        We take maximum of both options. Its' a bit weird to explain, but this code should make things clear.

        C++ Code
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Clever :)

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            Rev. 2   Vote: I like it +13 Vote: I do not like it

            NibNalin showed me a more understandable way to explain the same solution. Here is the idea :

            So we find the tin and tout values of the nodes. Let order[x] denote the node y such that tin[y] = x. Our DP state is DP[i][x] denotes the best x sized subset we can make using all nodes having tin values in the range [i, n]. To compute DP[i][x], we have two options :-

            1) We do not take order[i]. DP[i][x] = DP[i + 1][x]

            2) We take order[i]. DP[i][x] = DP[tout[order[i]] + 1][x - 1] + val[order[i]]

            Take maximum of both. It is easy to see that this does not violate any of the constraints.

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve C? And does pass in E or is there a better solution?

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

    I solved E with an nlogn solution where n = r+g. I found for each frog the starting time when it would enter [a,b] and the finishing time when it would exit [a,b]. Sort all important timestamps and find the answer.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Oh sorry wromg problem I meant H and not E

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

        I did parallel binary search. You can see this technique here. To apply it here, we just have to add the strings to a trie one at a time, reset the trie if neccesary. You can check the offense count of each employee by traversing the trie for each word the employee say.

        Code

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 3   Vote: I like it +6 Vote: I do not like it

        I was the setter of this problem. There are various ways to solve this problem. My solution uses parallel binary search along with a trie and BIT for range updates. But this is an overkill and easier solutions exist. For example, you can use a persistent trie and normal binary search. There are even simpler solutions too but as I am not sure about them, I won't go into those.

        Another solution put forward by Baba. For each node in the trie, store in a vector the indices of the swear words ending there. Then for each query set, perform a binary search. To validate the 'mid', traverse the trie using the strings of the query set and in each node you visit, perform another binary search (eg. lower_bound()) to get the number of swear words ending at that node whose index <= 'mid'. Complexity is O(n*logn*logn).

        If you are interested, you can find my code here.

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

          easier solutions exist. For example, you can use a persistent trie

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

          Could you please explain the persistent trie + binary search approach in a little more detail?

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            Rev. 2   Vote: I like it +5 Vote: I do not like it

            Note that if you insert a string S into a trie, then it changes |S| nodes (always including head).

            So you can store for each i from 1 to N a trie made using the employees words 1... i using memory and time (see here for some idea on how to implement persistent data structure).

            Finally, for each query, to evaluate binary search predicate, run through each word in the query, and check how many words in trie are prefix of this.

            You can show that this takes (because sum of length of all strings is  ≤ 106.

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve J? I tried thinking about a solution but gave up very quickly because it felt like anything I thought would be too messy to implement.

Also, what is intended solution for C?

I made it pass by observing that the matrix of dot products had a special form in the sample test. I assumed that it would hold for all n and came up with a way to incrementally construct my solution by placing first point at (1,0,0,...,0). Then fix first co-ordinate for remaining points by my dot product observation. Then rotate remaining points s.t. 2nd point has co-ordinates (x,y,0,0,0,..,0). I know x and therefore can find y since point lies on unit circle. Keep repeating till we have our entire set.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think the answer for C is an n dimensional regular simplex

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    I formulated a recurrence. It used the fact that you can add the new point in a direction perpendicular to the plane formed by the previous points, to get the solution for the higher dimension. Other than that there were uses of Pythagoras theorem. The complete solution would be a bit difficult to explain without figure.

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

    I solved the problem in the following way. First, imagine a vector from the origin to each point. Let's first find the angle between every pair of vectors (these should all be the same).

    I'll give the explanation for this concerning 2D, but it can be extrapolated to any dimension. For 2D, consider the plane x+y+z = 0, This is in 3D, but a 2-dimensional hyperplane. Consider the points (1,1,-2), (1,-2,1), (-2,1,1) in this hyperplane. We note that they are the same distance from the origin, and are also equidistant from one another. To find the angle between two vectors, we have dot product formula involving cosine of the angle. In this manner we proceed for any dimension. The points (1,1,.,-n),(1,1,..,-n,1)...(-n,1,1,1...1,) are the points we consider.

    So, we have found the angle, but we cannot use these coordinates for our answer since they are in wrong dimension.

    Say we already have the solution for dimension n-1, Let's find solution for n. Our current points are in dimension n-1, For now, add a coordinate of 0 in the n-th dimension for each point. This creates a hyperplane as well. We must add another point to have a total of n+1 points. We will make it perpendicular to the hyperplane we have created. So the point will be (0,0,...,1). Now we have a total of n+1 points, but the angle is incorrect.

    We currently have a 90 degree angle from the last point vector (0,0,...,1) to every other one. Say the angle we calculated is theta. We need to rotate each of the first n vectors by theta — 90 degrees. (It is guaranteed that theta > 90 by the way — this is not something you need to prove, you can print values and see it's true).

    Now, to rotate by x = theta-90. It is easy to think about this going from 1D to 2D. You can easily work it out on your own. Remember we have a 0 in the last coordinate of each point. Make this equal to -sin(x) and multiply every other coordinate by cos(x). (you can convince yourselves this is true for the 1D to 2D example. This same idea holds for all other).

    We have way of going from n-1 dimensions to n dimensions. Base case is 1D, where solution is -1; 1. Therefore we are done.

    My Solution

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain the solution for A please?
More specifically, How do I do modular calculations on a/b where a%m=b%m=0 and how do I find the factorial without TLE?

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    You can break factorials mod m into chunks of size m - 1, skipping all multiples of m. Now observe how all chunks except the last one teudce to (m - 1)!

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

      Ok, so if we have to calculate (17!)/(13!) mod 11, it basically reduces to:
      (10! * 6!)/(2!). And now to calculate final answer, we just have to do regular modular operations right?

»
7 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it