RAD's blog

By RAD, 5 years ago, translation, In English,

Initially the order of problems was A-C-E-D-B. But we were not sure about last two.

166A - Rank List

This is simple straight-forward problem — you were asked to sort the teams with the following comparator: (p1 > p2) or (p1 = p2 and t1 < t2). After that you can split the teams into groups with equal results and find the group which shares the k-th place. Many coders for some reason used wrong comparator: they sorted teams with equal number of problems by descending of time. Such submits accidentally passed pretests but get WA #13.

166B - Polygons

Polygon A is convex, so it is sufficient to check only that every vertex of polygon B is strictly inside polygon A. In theory the simplest solution is building common convex hull of both polygons. You need to check that no vertex of polygon B belongs to this hull. But there is a tricky detail: if there are many points lying on the same side of convex hull than your convex hull must contain all these points as vertices. So this solution is harder to implement and has some corner case.

Another solution: cut polygon A into triangles (by vertex numbers): (1, 2, 3), (1, 3, 4), (1, 4, 5), ..., (1, n - 1, n). The sequences of angles 2 - 1 - 3, 2 - 1 - 4, 2 - 1 - 5, ..., 2 - 1 - n is increasing. It means that you can find for each vertex of B to which triangle of A it can belong using binsearch by angle.

Similarly you can cut polygon A into trapezoids (with vertical cuts). In this case you'll need a binsearch by x-coordinate.

166C - Median

If the initial array doesn't contain number x, than you definitely need to add it (that's +1 to answer). Than do the following. While median is strictly less than x you need to increase it. Obviously the surest way to increase the median is to add a maximal possible number (105). Similarly while the median is strictly more than x, add a number 1 to the array. Constraints are small, so you can add the numbers one by one and recalculate the median after every addition.

Also there is a solution without any cases: while the median isn't equal to x, just add one more number x to array.

166D - Shoe Store

Let's sort the people by decreasing of shoes size. Observe that when considering the i-th man we are interested in no more than 2 pairs of shoes: with size li and li + 1. It allows solving with dynamics. The state will be (the number of first unconsidered man i, is pair of shoes with size li available, is pair of shoes with size li + 1 available). You have 3 options: leave the i-th man without shoes or sell him a pair of shoes of one of suitable size (if available).

166E - Tetrahedron

Obvious solution with dynamics: you need to know only how many moves are left and where is the ant. This is 4n states, each with 3 options – most of such solution passes. Observe that the vertices A, B, C are equivalent. This allows writing such solution:

int zD = 1;
int zABC = 0;
for (int i = 1; i <= n; i++) {
	int nzD = zABC * 3LL % MOD;
	int nzABC = (zABC * 2LL + zD) % MOD;
	zD = nzD;
	zABC = nzABC;
}
cout << zD;

Also this problem could be solved by log(n) with binary exponentiation of some 2 × 2 matrix into power n.

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

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

Edited -- Fixed my code! Thanks to Igel_SK!

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

Isn't the state for D too big?

Also, I see people doing bipartite matching in a greedy way, why does this work?

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

    Bipartite matching with sorting shoes works correctly, it can be proofed (in russian). I think it should get TLE but the tests were weak :)

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

    I solved with the DP this way: you have the current person and a mask that represents if the 2 sizes of shoes that this person can use are available (costumers are sorted by shoe size), so it will be a dp[10⁵][4] table.

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

Great explainatiions:) Can you explain your second solution on Problem B in detail ? Thx How do you perform binsearch on angles to calculate whether every vertex is in Polygon A or not

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

I solved E:Tetrahedron using the problem (3^n+3*(-1)^n)/4 . Here is my solution . However it failed the system test and when I used BigInteger it passed.Here is the 2nd version. 2 question: 1.Why does the first solution fail... 2.Is there any thing I can do to avoid BigIntegers

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

    Use long

    Doubles are not accurate

    Your code with long instead of double 1403711

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

    Got the same problem.

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

    Hi , can you explain your solution for this question some better ? I mean i know the your solution is true but how did you reach this solution ? Plz answer

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how did you arrive at this formula can you please explain??

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

What 2 x 2 matrix can be used in E? I've only seen it solved with a 4 x 4 matrix with diagonal = 0 and rest = 1.

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

    See Egor's solution: 1390234

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

      Can you explain the idea behind this solution?

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

        In general, you can do matrix exponentiation (that is, raising matrix M to the N-th power) in O(logN) time, where N is the exponent. If you exploit a "matrix notation" for your dp recurrence, then you can reduce it to this problem, thus solving it in O(logN).

        For example, it is possible to find the N-th fibonacci number using this method. For a better explanation, check out the "Fibonacci log N" tutorial on e-maxx.ru

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

Sorry about that, just ignore the post.

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

from math import *

def fast_exponentiation(base, n): if n == 1: return base else: if n % 2 == 0: base1 = fast_exponentiation(base, n/2)**2 return base1%1000000007 else: return (base*fast_exponentiation(base,(n-1)/2)**2)%1000000007

t = int(raw_input()) if t%2 == 0: print ((fast_exponentiation(3,t) + 3)/4)%1000000007 else: print ((fast_exponentiation(3,t) — 3)/4)%1000000007

Why is this code in Python wrong for thetraedron?

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

    Note: you can use the built-in function pow for fast modular exponentiation:

    pow(3, t, 1000000007)
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I keep getting wrong answer...

      I get right values if I put modulus outside all the expression, so:

      print ((fast_exponentiation(3,t) + 3)/4)%1000000007 gives correct value, but slow and print ((fast_exponentiation(3,t) + 3)/4) within the fast exp with mod gives WA, why?

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

        You can't divide by 4 if you use mod before it. You should multuply pow(4, p-2, p) instead

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

        Try ((fast_exponentiation(3,t) + 3) * 250000002) % 1000000007, and take modulo on each fast_exponentiation step.

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

          ant.ermilov thank you for the tip, I have seen it in a solution as well, but can you explain to me, or point me to somewhere that can tell me, why is that particular number used?

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

            At first, let's try to understand, why your approach does not work. For example, we have
            Y = M+1, Y % M = 1,
            but (Y / 4) % M != (Y % M) / 4.

            So division can be substituted by multiplication. In general, we have modulo M, divisor D and want to find such Z that for each X: (X / D) % M = ((X % M) * Z) % M.
            After simple transformation we will get (X * Z) % M = 1.
            For particular case 250000002 * 4 = 109 + 7 + 1.
            Some extra info: Z can be found iff gcd(X, D) = 1, and simpliest way described at AlexDmitriev's comment above. From Euler's theorem we get Z = (DM - 2) % M.

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

              Thank you very much to both :D I got axcepted :)

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

              Amazing explanation! Thanks

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

What does non-degenerate mean in 166B - Polygons (Div2 B) ?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@AlexDmitriev Can you please explain In the solution to E why has nzABC been multiplied by 2 in the fifth line?

int nzABC = (zABC * 2LL + zD) % MOD;

Thanks a lot.

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

    Let Ai denote number of ways to finish near the vertex A after i moves (same for Bi, Ci, Di). Easily,

    Ai = Di - 1 + Bi - 1 + Ci - 1
    Bi = Di - 1 + Ai - 1 + Ci - 1
    Ci = Di - 1 + Ai - 1 + Bi - 1
    Di = Ai - 1 + Bi - 1 + Ci - 1

    with the initial conditions

    A0 = 0, B0 = 0, C0 = 0, D0 = 1

    Due to the symmetry $A_i=B_i=C_i=ABC_i$, so

    ABCi = Di - 1 + ABCi - 1 + ABCi - 1 = Di - 1 + 2 * ABCi - 1
    Di = ABCi - 1 + ABCi - 1 + ABCi - 1 = 3 * ABCi - 1
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

TETRAHEDRON : can this problem be think in a way that if u want to reach at D in n steps, then to travel n — 1 steps 3 ^ (n — 1) ways possible, now this case include that if u reached at D in n — 1 steps therefore to reach in n steps ans(in n steps) = 3 ^ (n — 1) — ans(in n — 1 steps); which is a DP solution

eg — to reach in 1 steps = 0 to reach in 2 steps — 3 ^ (2 — 1) — 0; to reach in 3 steps — 3 ^ (3 — 1) — 3 = 6 to reach in 4 steps — 3 ^ (4 — 1) — 6 = 21 to reach in 5 steps — 3 ^ (5 — 1) — 21 = 60

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm interested in E,whether there is a simple formula no matrix.i can't get it,anybody got it and coubld you share it?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    CAN anybody explain E in detail? Can't get it.Thanks!

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let f[A][j] is the number of ways from D to A by going j steps,as same,f[B][j], f[C][j] and f[D][j], we know f[D][0] = 1, f[A, B, C][0] = 0(because the ant starts at D).

      then you get four equations below:

      f[A][j] = f[B][j - 1] + f[C][j - 1] + f[D][j - 1]

      f[B][j] = f[A][j - 1] + f[C][j - 1] + f[D][j - 1]

      ......

      f[D][j] = ...

      you can solve this problem in O(n),the answer is .

      but it's too slow.you can express the four equations by matrix.then it's obvious to solve the problem by matrix fast power algorithm in .

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

@RAD In question B Polygons, What's the problem if we directly compute the convex hull of all points and check if any point of B is present in it ? I couldn't understand the mistake!!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi... . Could you please explain why is the output for testcase #13 of problem 166A - Rank List 1?