k790alex's blog

By k790alex, history, 5 days ago, In English,

Hi,

The 2019 ICPC Mexico Finals starts in 30 minutes.

Let's discuss the problems after the contest.

There are some mirror contests starting 1h after the real one:

This facebook page is posting updates frequently: https://www.facebook.com/acmitesochapter

Streaming:

Good luck to all the teams.

UPDATE The contest has started.

UPDATE Live scoreboard: https://global.naquadah.com.br/boca/score/index.php (use this if the previous one doesn't work https://global.naquadah.com.br/boca/scoreglobal.php?h=AT2oE0HBeAg8eox30q5wZOdk8SY_bIZ-hGKuX9OTrY661HqiWgHRra4KBYyrxV6IDqZeTVr7yJ6EpBVje50BxzQBkGZoTKMNPwb3UZpD_G79M9PmveqUhUUrtO04BJUpMwqPvrz_7o-QWTc)

UPDATE Problems available:

UPDATE Official results are ready: http://scorelatam.naquadah.com.br/

Congrats to the winners!!!

Ranking

UPDATE These are the teams going to the world finals, there were 4 extra spots:

- UH++,CUBA
- Limitless, CUBA (new)
- Norman is Hunting, MEXICO
- E3, MEXICO
- #define TriLCI(404.0) :v, MEXICO
- pu+os, MEXICO (new)
- Guerreros de RodriGOD, COSTA RICA
- InChaVoLa, ARGENTINA
- GG Dem, ARGENTINA
- #NuevaConstitución UChile1, CHILE
- Rating MiSeRable, PERU (new)
- descomUNAL, COLOMBIA
- La bomba de tenedores, VENEZUELA
- Time com T, BRASIL
- Campinas Grande, BRASIL
- Amigos do Beto, BRASIL
- Rock Lee do Pagode Namora D+, BRASIL
- Rábalabaxúrias, BRASIL
- Triple G, BRASIL (New)
 
 
 
 
  • Vote: I like it
  • +85
  • Vote: I do not like it

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

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

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

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

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

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

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

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

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

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

»
35 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there another way to solve K problem avoiding FFT?

  • »
    »
    34 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sure, naive multiplication does the job pretty well here. Expected complexity in this problem is $$$O(n^2)$$$.

  • »
    »
    34 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We tried FFT with divide and conquer but the precision error is too big to handle up to 2^63 -1. In the end 10^4 for 0.1 seconds troll us :P

    • »
      »
      »
      21 hour(s) ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Because of the 2^63-1 constraint, the real limit is actually $$$n \le 16$$$. So you can do multiplication as slowly as you want...

»
35 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E we have to create a List with all the positions of E from 0 to n+s

Then we need to iterate the string if the position has an E, then we sum S to the ans if not we look for the closest E to this relative position and if its distance is less than S we add (s — distance from the closest E) to the answer.

Code for preview:

Code
»
33 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me why this solution for I is wrong? https://ideone.com/61vnoj

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

    If a client i is sent an email k*(1e9 + 7) times, dp[i] is zero, but that client still needs to be counted towards the "number of emails after the improvements".

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

    You should count separately the number of messages before the optimization and after the optimization because of the mod. Test case that breaks this solution was added one day before the competition.

»
15 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G and F ?

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

    Problem G could be easily solved with Suffix Automaton, you could build a Suffix Automaton of S in $$$O(n*log(n))$$$ and then for each query start at the root of the automaton and do the following:

    • If there is a transition from the current node with the current letter of the query, move through it.

    • Otherwise, if you are not on the root, go to the root and add $$$1$$$ to the answer, if you are on the root, then the answer is $$$-1$$$.

    For Problem F, you have to solve the problem recursively. Consider you'll be putting floors from bottom to top, if you have $$$s$$$ remaining blocks and the last floor you put had $$$n$$$ blocks then the number of ways to put the rest is:

    $$$ dp(s, n) = dp(s, n-1) + \sum_{x=1}^{min(s,n)} dp(s-x, x) $$$

    This is, if the next floor doesn't start in the first block of the last floor, then there are $$$dp(s, n-1)$$$ ways to put the rest, otherwise, you can pick any valid size for the next floor and you know where it will be.

    This is $$$O(n^3)$$$ if implemented naively, but it can be optimized to run in $$$O(n^2)$$$ by pre-calculating some sums.

  • »
    »
    87 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Another way to look at F is the following. First, you can ignore the first level (from the bottom upwards) of blocks. Let DP(s,b) be the number of ways to put the remaining blocks. To calculate this you look at three cases: - The first level of blocks is full - The first stack is empty - The last stack is empty

    You can calculate the first case by simply ignoring s blocks. The second and third case are analogous, and you can calculate them by ignoring one stack. However, the cases eventually overlap, since the scenario where both the first stack and the last stack are empty can be reached from both cases. This can be solved by subtracting the value for the overlap. This is the formula:

    DP(s,b) = DP(s,b-s) + 2 * DP(s-1,b) — DP(s-2, b).

»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

In general I think it was good that problem-setter name was removed from each problem (I used to check the name of the problem-setter to try to guess complexity). Although, after reading problem C I feel bad the authors are not getting any recognition, very creative statement indeed.

  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    - A {Algorithm Teaching}          {Marcelo Fornet, Cuba}
    - B {Build the Perfect House}     {Marcelo Fornet, Cuba}
    - C {Cut Inequality Down}         {Mariano Crosetti, Argentina}
    - D {Dazzling Stars}              {Mário da Silva, Brasil}
    - E {Eggfruit Cake}               {Moroni Silverio, México}
    - F {Fabricating Sculptures}      {André Amaral de Sousa, Brasil}
    - G {Gluing Pictures}             {Nicolás Álvarez, Argentina} 
    - H {Hold or Continue?}           {Pablo Zimmermann, Argentina}
    - I {Improve SPAM}                {Paulo Cezar Pereira Costa, Brasil}
    - J {Jumping Grasshopper}         {André Amaral de Sousa, Brasil}
    - K {Know your Aliens}            {Mário da Silva, Brasil}
    - L {Leverage MDT}                {Carlos Mendoza, Peru}
    - M {Mountain Ranges}             {Vinicius Santos, Brasil}
    
    • »
      »
      »
      108 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Makes sense that the same guy proposed the two most interesting and brutal problems in the contest. Kudos to him.

      • »
        »
        »
        »
        39 minutes ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        In case you are referring to the first two problems here is an outline of the solution:

        Problem A: build the graph where every possible set is a node, and there is a directed between A and B if B contains exactly one element more than A. This is of course a DAG and we need to find maximal anti chain here. Applying Dilworth to this graph is enough to find the solution. Notice that number of edges in the transitive closure is at most $$$N \cdot 3^K$$$.

        Problem B: Every point can be rotated 90 degree several times without affecting the answer. Do this until every point is in the first quadrant. Let's find where is the corner of the optimal square in the first quadrant. Binary search over the length of the diagonal (it is proportional to the perimeter) and try to find a rotation of the square such that it doesn't contain any point. Each point will give you a possible interval to rotate the square. Find if the intersection of all intervals is not empty. The time complexity was $$$O(\log(-PREC) \cdot \log n \cdot n)$$$.

        There was also a beautiful solution for this problem with expected complexity $$$O(n)$$$, similar to the algorithm that find minimal enclosing circle. Random shuffle points at the beginning, and try to find a valid square for all prefix. Suppose you have a maximal square for first $$$x$$$ points, if point $$$x+1$$$ is outside this square, no action needs to be taken, otherwise, recompute the square, but letting this point belonging to one side of the square. This solution is a little bit trickier to implement, since a pair of point can define two possible maximal (not both maximum) squares.

»
67 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
37 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Bonus: Can you solve problem D in $$$O(n \cdot log n)$$$.

Hint