Jugo's blog

By Jugo, history, 10 months ago, translation, In English

Hello, Codeforces!

On wednesday, 10 june 2020 y. on 17:35 (UTC + 3) will take place End of the learning — Beginning of the tour contest (Div 3).

This is my first round (mashup, because for creating trainings I haven't got rating, because I need to stop writing contests on the phone) with my tasks. Competition will be held according to the rules of ICPC. Penalty for every wrong submission is 20 minutes. 20 minutes before contest table will be freezed.

You will be given 6 tasks and 2 hours. I wish you like it. I have high hopes for E task.

Ahmad Ahmadsm2005 Said, Ahmed ahmedfouadnew Fouad, Matvey Asgio Kulinich and Maxim Xennon Karpuk helped me with testing tasks. Also thanks to Mike MikeMirzayanov Mirzayanov for systems Polygon and Codeforces!

I wish you luck!

I almost forgot about link:

https://codeforces.com/contestInvitation/4036ec99932a47484351d57a812de34c7a4fbb2c

Here is editorial

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

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

Is the time UTC+9?

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

Isn't the penalty set to 20 minutes (in the contest)?

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

    why?

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

      I'm not saying that it should be, I'm saying that it is, even though you mention the penalty is 10 minutes.

      For example, see my score:  (if it's blurry, https://imgur.com/a/JpaNEYU)

      My solve times are 1 + 3 + 5 + 7 + 13 + 18 = 47, meaning that my 3 penalties are each causing 20, not 10 as they should.

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

        It may be. I will correct it in blog

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

How to solve F?

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

    I will public solves later

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

Jugo, is it okay if I post a brief editorial here for everyone (since submissions are public now)?

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

    Okay, I will do it too) there would be 2 editorials)

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

Slight editorial (with author permission):

A

This is mostly about knowing how your language works. Division, however, gets picky. It's a good idea to not use doubles because they have precision issues (read). Instead, you can use integer division, which automatically truncates (in C++, at least), possibly having to be careful with negatives in other languages.

For the actual implementation, it seems like the test cases are designed so overflow won't happen and you won't have to mod with negative numbers, so the rest is simple.

My submission: [submission:83308763]

B

Consider all numbers that have to be odd. Because numbers are nonnegative, each odd number must be worth at least $$$1$$$. Similarly, each even number must be worth at least $$$0$$$. So the minimum possible number you can create is $$$c_o$$$ — the number of required odd numbers. You can create any $$$s \geq c_o$$$ where $$$s$$$ and $$$c_o$$$ have the same parity (just add $$$2$$$ until you get there), and you can't create any $$$s$$$ of different parity. So the final conditions to check are that $$$s \geq c_o$$$ and $$$s \mod 2 = c_o \mod 2$$$.

My submission: [submission:83309018]

C

Store any form of set (std::map in C++, java.util.TreeSet in Java, a dictionary in Python, I don't know about other languages) that supports fast insertion and checking if an element is in the set. Then the first type of query is insertion, and the second type of query is checking if an element is in the set, which is perfect.

My submission: [submission:83309210]

D

This is a direct application of segment trees. I... don't have more to say about this one.

My submission: [submission:83309468]

E

This is a problem with a simple solution, but one that may be hard to come up with.

First, we must note that this problem is exactly equivalent to finding the number of paths from $$$(1, 1)$$$ to $$$(i, j)$$$ in a rectangular grid, where you can only move down or right (read). Why is this so? It's given in the statement that each value at $$$(i, 1)$$$ and $$$(1, j)$$$ is $$$1$$$. Conveniently, there's always exactly $$$1$$$ path to each of these cells. For all other cells, to get to $$$(i, j)$$$ (in the path problem) there are two places you can come from — either $$$(i - 1, j)$$$ or $$$(i, j - 1)$$$. Thus the number of ways to get to $$$(i, j)$$$ is the sum of the number of ways to get to the two places you can come from.

This gives us a dynamic programming recurrence: $$$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$$$ where $$$dp[i][j]$$$ is the number of ways to get to $$$(i, j)$$$. Note that this is exactly the same as the one given in the problem.

Now that we've reduced the problem, let's attack the path problem a bit harder. Currently, our solution is $$$O(i \cdot j)$$$, which will certainly not pass. Let's think of the path from $$$(1, 1)$$$ to $$$(i, j)$$$ as a string of the moves we make: D for down and R for right. This string must be of length $$$(i - 1) + (j - 1) = i + j - 2$$$, have exactly $$$i - 1$$$ of D, and exactly $$$j - 1$$$ of R. And our goal is now to count the number of different strings. A bit of combinatorics tells us that there are exactly $$$\dbinom{i + j - 2}{i - 1}$$$ or $$$\dbinom{i + j - 2}{j - 1}$$$ possible strings.

Now we just have to compute the answers under the tight memory conditions. $$$\dbinom{i + j - 2}{i - 1}$$$ is equal to $$$\dfrac{(i + j - 2)!}{(i - 1)!(i + j - 2 - (i - 1))!} = \dfrac{(i + j - 2)!}{(i - 1)!(j - 1)!}$$$. Computing factorials and inverse factorials can be done iteratively with $$$O(1)$$$ space and $$$O(i + j)$$$ time (although $$$O((i + j)\log{(10^9 + 7)})$$$ time is simpler).

My submission: [submission:83310114]

F

We can maintain the probability of ending in each tunnel iteratively. Let $$$a_i$$$ be the given probabilities for each turn $$$i$$$ from the input, and $$$p_i$$$ be the probability of ending at tunnel $$$i$$$ (for $$$i$$$ from $$$1$$$ to $$$n + 1$$$). Then $$$p_1$$$ is just $$$a_1$$$ because we have exactly that chance of ending in that tunnel. Otherwise, we have a $$$100 - a_1$$$ chance of advancing to tunnel $$$2$$$. Then, at tunnel $$$2$$$ we have a $$$(100 - a_1)a_2$$$ chance of stopping in tunnel $$$2$$$, and a $$$(100 - a_1)(100 - a_2)$$$ chance of advancing to tunnel $$$3$$$. More generally, the probability of stopping at tunnel $$$i$$$ is $$$p_i = (100 - a_1)(100 - a_2) \dots (100 - a_{i - 1})a_i = a_i \cdot \prod\limits_{k = 1}^{i - 1}(100 - a_k)$$$, where $$$a_{n + 1}$$$ is just $$$1$$$ because we have to stop there.

The final answer is then just the expected value, which is $$$\sum\limits_{k = 1}^{n + 1} k \cdot p_k$$$. Be careful with output (use setprecision with a large number of digits in C++) to make sure the jury knows your answer is correct because small-number accuracy is important here.

My submission: [submission:83310636]

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

    Hello! How you did these opening triangles?

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

    You can public it in your blog, I will add link

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

    I will do editorial on russian lenguage then

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

    For F when you turn right you go to another tunnel.So for p1 shoudn't it be 100-a1 for ending in that tunnel and then advancing for 2nd tunnel you should have a1 chance for that ? Or I have misunderstood the question

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

      The statement's not the clearest, but I interpreted "turn right" from On every turn person can turn right with probability a [i] as "end at that tunnel with probability $$$a_i$$$" and "go straight" as "continue to the next tunnel"

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

        Yes, you're right!

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

        "the tunnel with n turns, which lead right, in other tunnels" This statement made me think you have to turn right to go to another tunnel

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

          I won't do such mistakes later

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

    Why did you took the path from (1,1) to (i,j) ?I mean what's the reason or intuition behind this.Thanks in advance

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

      Unfortunately, there isn't much intuition. The best I can say is "I've seen this problem before, so I recognized it quickly."

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

    Can you make it a blog?

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

I think you meant editorial here too instead of parse.

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Some suggestions:

  1. Try to use MathJax format. For example, something like 1<=n<=1e5 should be $$$1 \le n \le 10^5$$$(use single dollar sign, but not 3 dollar signs) which will be displayed as $$$1 \le n \le 10^5$$$

  2. Try to spell key words correctly. ( guaranteed but not garanted)

Hope you can make better contests next time :D