Блог пользователя darkkcyan

Автор darkkcyan, история, 3 года назад, По-английски

Hello, Codeforces!

I am really excited to invite you to Codeforces Round 763 (Div. 2) on Dec/28/2021 16:35 (Moscow time)! The start time is unusual, so please pay attention.

All the problems were authored and prepared by me. I would like to give special thanks to everyone who made this round possible:

The round consists of 5 problems and you have 2 hours to solve them.

Wish you good luck and high ratings!

UPD0: The score distribution 500 — 1000 — 1750 — 2500 — 2750.

UPD1: Congratulation to the winners of the round!

Div. 2
  1. wanyuezaifengli
  2. ZhuJianfeng
  3. proton1126
  4. qazsxdew
  5. Hayasaka
Div. 1 + 2
  1. heno239
  2. Geothermal
  3. Vercingetorix
  4. dorijanlendvaj
  5. wanyuezaifengli

UPD2: The Editorial is out!

Hope that you guys enjoy the rounds, and thank you again for participating! <3

  • Проголосовать: нравится
  • +643
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +199 Проголосовать: не нравится

As the first tester, and the first comment, I would like everyone to deliver contribution by clicking that green up button.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится -17 Проголосовать: не нравится

Scoring Distribution?

UPD: Why downvote?

UPD2: Now it's updated.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -17 Проголосовать: не нравится

    Usually the score distribution comes shortly before the beginning of the contest__

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +43 Проголосовать: не нравится

So many contests by the end of the year! THANK YOU people!

Classic cuban granny postcard
»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

darkkcyan orz

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Finally traditional 5 problem style. Unfortuntately, untraditional time I cannot make

»
3 года назад, # |
  Проголосовать: нравится -73 Проголосовать: не нравится

hi

»
3 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

love :3

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Back to back contests in the end of the year, thank you Codeforces and all problem setters.

»
3 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Wow tourist is a tester

»
3 года назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

Oops wrong announcement Thanks @below

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Hope everyone will get good results in this contest. Good luck ;)

»
3 года назад, # |
  Проголосовать: нравится -45 Проголосовать: не нравится

Is this contest rated for Div 2 ?

»
3 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

They will WA until they die !

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I wonder how many points for each peoblems Emmmm...5 problems make me scared

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Rating Distribution ???

»
3 года назад, # |
  Проголосовать: нравится +62 Проголосовать: не нравится

Don't downvote anyone blindly. even if someone have good idea or trick to share they will fear to post that trick or idea in comment or blog because of fear of downvotes. I was very upset to see so many downvotes in TadijaSebez his contest(codeforces round 758(Div.1+Div.2)). maybe the way YouTube removed Dislike count Codeforces would be better place if there will be No downvote button. MikeMirzayanov Thank You for building such amazing place and please take my idea into consideration!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    True, but better keep the downvote button and hide the downvote count, where comments are still hidden when they got too many downvotes.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

two div 2 contest on 2 days, problemsetters are wonderful

hope i got positive delta tdy

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any interactive questions in the contest?

»
3 года назад, # |
  Проголосовать: нравится -35 Проголосовать: не нравится

Changed my handle , red colored 3 looks awesome , hope it'll be real one day , starting the journey from this contest

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

hope will have great time and not to lose expert.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Updated

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

PS : The score distribution is not usual for problems C, D, E!

»
3 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Is CF running slow?

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Alice and bob are more than friends (-_-),

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится
  • Problem A is hard :+)
  • many contestant said good Bye after seeing problem A (like me ) :p
»
3 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Very good round for me, interesting problems. But very strange B. P.S Thanks to author for really cool illustrations for test cases

»
3 года назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

The Gif in problem A made me so nervous

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

good job

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Cool gifs in A

»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

I always believe first problem should have simpler statement and should be on easy side.

Nice contest
»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I made two submissions in A one in the minute 00:08 and one in 1:30 just in case the first one failed in the rejudge but i found that in standings my score in problem A decreased from 490 to 270. Will this be final score of my submission to A even after the rejudge?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yes

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But why? I thought that codeforces count consider the first accepted submission like ICPC rules. If I knew this I wouldn't make two submissions in A :(

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится

        but ur first soluition isn't really accepted it only passed pretests

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        If a contestant submits several times a problem's solution that passes all pretests, then the last solution is considered as the contestant's verified solution for this problem. All other solutions will be considered as unsuccessful attempts. Codeforces Contest Rules

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

The quality of problem preparation is elite, the writer has put so much effort into the pictures... Just darkkcyan appreciation comment

»
3 года назад, # |
  Проголосовать: нравится -61 Проголосовать: не нравится

I am sorry to give a negative feedback but Problem E is extremely disappointing: no thinking required at all, and standard bin lifting during implementation. I wonder how KAN accepted this problem for a rated contest.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I don't think there is any need for binlifting, it can be solved in O(N) I think (just find the next letter for each node and rest is just dfs).

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится

      okay, with Binary Lifting it was completely braindead, but probably there is a solution with a better complexity. Still a very boring problem.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +29 Проголосовать: не нравится

      Yes, it is O(n). In my opinion, the problem is hard, not because it requires something special, but because it is simple and the participants, on the other hand, know a lot.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please explain how did you solve the problem with a binary lifting ?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I thought of trying the below solution using binary lifting but ran out of time.

      Just as mentioned in the editorial, after finding the current inorder representation, we know the potential candidates eligible for doubling.

      Lets forget about the restriction k and solve the question first. i.e we can double as many nodes we want. Now for each of the eligible node from left to right, we can just traverse its ancester chain and double it if not doubled. We can stop once we find one ancestor which is already doubled. The complexity of this is O(n) as we visit each node once.

      Now if we add the restriction k, only difference is as below.

      Imagine the same process and as we double a node decrement k. Now if the number of not doubled ancestors for a eligible node is > current k, we can't double it. To check the number of undoubled ancestors we can use binary lifting (find the kth ancestor of this node and check if it is doubled). If it is already doubled, we can double the rest of the chain as it is less than k. If not we can skip the node.

      This is the initial submission I attempted where instead of using binary lifting for checking number of un doubled ancestors, I just looped through the ancestors to find them.

      https://codeforces.me/contest/1623/submission/140946673

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do you have any better proof? Those submissions look suspicious, but that's not a definitive proof.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      Codeforces Contest Rules

      1. It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work.

      MikeMirzayanov

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

        You're right. At first glance I thought it was just a commented out template, but it's actually a random code copy-pasted multiple times. Definitely breaks the obfuscation rule.

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Loved problem D. Kudos to the author(s).

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In E, did it matter that the tree was binary and that we consider the in-order traversal? I don't think my solution uses either...

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    yeah, neither of them matter, except (of course) for implementation details.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    I guess that most participants have implemented methods in $$$O(n \log n)$$$ that works on general trees...

    When I saw the particular structure of the tree, I guessed that there might be some method with better time complexity or lower implementation difficulty. But since the implementation of the generic algorithm is not complicated and can pass the constraints in time, I didn't bother to think about it anymore...

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Neither of them matters for $$$O(n)$$$ methods also, except for convenience. The only thing that would change is if $$$u$$$ comes before all the children of $$$u$$$.

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

why didn't you use $$$n*m$$$ or $$$nm$$$ instead of $$$n.m$$$ in D it looks like comma and it ruined my day TT :((

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I am sorry to hear that. Initially, I wrote it as $$$n \times m$$$ but after some advice, it was changed to $$$n \cdot m$$$. But, well, the solution is solvable in $$$O(n + m)$$$ as well, which is implemented in my model solution, so maybe you can do a pro gamer's move and implement that solution :).

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Anybody have idea on how to get the irreducible fraction in problem D?

I was able to derive an analytical form involving (p%)^i, (1-p%)^i, and O(n) constants. But if I calculate the fraction under mod P, it becomes hard to simplify the fraction. And I cannot find a way to simplify it in its analytical form...

XD

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +16 Проголосовать: не нравится

    Short version:

    You can realize the robot's pattern is cyclic, then every step can be mapped to one position of the and calculated using AGP.

    Long version:

    The state of motion of the robot can be uniquely represented by the tuple $$$(r, c, dr, dc)$$$, so a given pattern of motion will form a cycle of at most $$$4 \cdot n \cdot m$$$ steps.

    Additionally for ease of implementation we can note that due to the grid formulation this cycle will never have a tail.

    Suppose the cycle is of length $$$k$$$ and there are $$$l$$$ positions $$$x_1, x_2, \ldots x_l$$$ (0-indexed) in this cycle which share a row or column with $$$(r_d, c_d)$$$.

    Then the expected time taken to clean this cell becomes the sum of:

    $$$ \begin{array}{|c|c|c|c|} \hline p \cdot x_1 & p \cdot x_2 \cdot {(1 - p)} & \ldots & p \cdot x_l \cdot {(1 - p)}^{l - 1} \cr \hline p \cdot (x_1 + k) \cdot {(1 - p)}^{l} & p \cdot (x_2 + k) \cdot {(1 - p)}^{l + 1} & \ldots & p \cdot (x_l + k) \cdot {(1 - p)}^{2 \cdot l - 1} \cr \hline \ldots & \ldots & \ldots & \ldots \cr \hline p \cdot (x_1 + i \cdot k) \cdot {(1 - p)}^{i * l} & p \cdot (x_2 + i \cdot k) \cdot {(1 - p)}^{i * l + 1} & \ldots & p \cdot (x_l + i \cdot k) \cdot {(1 - p)}^{i \cdot l - 1} \cr \hline \ldots & \ldots & \ldots & \ldots \cr \hline \end{array} $$$

    where the probability in row $$$i$$$ and column $$$j$$$ represents the probability of the cell being cleaned from position $$$x_j$$$ during the $$$i$$$-th repetition of the cycle.

    We can notice that the $$$j$$$-th column forms an infinite AGP with $$$A_1 = x_j$$$, $$$G_1 = p \cdot {(1 - p)}^{j - 1}$$$, $$$d = k$$$, $$$r = {(1 - p)}^l$$$. This can be calculated easily using the standard formula available from Wikipedia or elsewhere.

    Submission — 140937671

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Luckily I do have another way of describing, or dare I say it, a different solution that is simpler.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I would love to hear it, I suspect I overkilled the problem since it took me 30-40 mins to implement it in contrast to the 10 mins it took me to arrive at the idea.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится -22 Проголосовать: не нравится

        The, ahh, benefit of this solution is the ability to use WolframAlpha to take away all remaining specks of brainpower needed to solve the problem.

        See: formula

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

      Well I do have something similar:

      First, observe that the timesteps that cleaning is possible are cyclic, with cycle length no more than $$$4max(m,n)$$$.

      Then, find the cycle, suppose it's $$$p_1, \cdots, p_c$$$.

      Calculate the gap between neighboring points to get $$$g_1, \cdots, g_{c-1}, g_c=L-p_c$$$.

      Then the answer is $$$[g_1 + g_2(1-p) + g_3(1-p)^2 + \cdots + g_c(1-p)^c] [1+(1-p)^c+(1-p)^{2c}+\cdots]$$$

      And the latter term equals $$$\frac{1}{1-(1-p)^c}$$$.

      That's where I stuck, cause I dont know how to simplify the fraction...

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Aww I realized that the irreducible fraction is actually irrelevant.

        Since if u calculate $$$\frac{a}{b}=\frac{tu}{tv}$$$, where $$$gcd(u,v)=1$$$, then $$$ab^{-1} = tu(tv)^{-1}=uv^{-1}$$$ mod P.

        Sad that I didn't get this during contest...

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Does Cycle always exist? I am getting MLE for Test case 10 because of the infinite loop :(

      My submission

      My bad :( , in above submission my cycle finding code is wrong,

      Here is my AC submission

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    Here is my solution. Let's build the graph where every node is a tuple (row, col, row_direction, col_direction). Obviously, this is a graph consisting of only one cycle and every node has only one outgoing edge. Each edge will have some weight indicating the probability of taking that edge. If a node is in the same row or column as the goal, its outgoing edge has weight $$$1 - p$$$, otherwise it has weight $$$1$$$.

    Now, let's say the cycle has length $$$L$$$ and the product of its edges's weights is $$$P$$$. Let's also define $$$length(u)$$$ as the length (number of edges) of the path from the starting node to the node $$$u$$$, and $$$prod(u)$$$ as the product of the edges's weights on the path from the starting node to the node $$$u$$$.

    Now, let's say our trip finishes at the node $$$u$$$, after traversing the cycle completely $$$k$$$ times. Then, the probability of such outcome is $$$P^k \cdot prod(u)$$$, and therefore the expected time to reach such outcome is $$$P^k \cdot prod(u) \cdot (L \cdot k + length(u))$$$.

    Therefore, for every node $$$u$$$ in the cycle, the expected time of finishing there is:

    $$$\displaystyle\sum_{k = 0}^\infty P^k \cdot prod(u) \cdot (L \cdot k + length(u))$$$
    $$$ = prod(u) \cdot L \cdot \displaystyle\sum_{k = 0}^\infty P^kk + prod(u) \cdot length(u) \cdot \sum_{k = 0}^\infty P^k$$$
    $$$ = prod(u) \cdot L \cdot \frac{P}{(1-P)^2} + prod(u) \cdot length(u) \cdot \frac{1}{1 - P}$$$

    Now, for every node $u$ not in the cycle, the expected time of finishing there is just $$$prod(u)\cdot length(u)$$$ — somehow, I forgot about this case when I was coding the problem, and still it passed the test cases, (it seems that the graph is always a cycle).

    UPD: Thanks to PoIar_ for sharing a simple proof of why the graph is a simple cycle.

    Now, for every node $$$u$$$ that is on the same row or column as the goal, we add the above formulas (depending if it's on the cycle or not) multiplied by $$$p$$$ (the probability of cleaning those row and column).

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      The graph is always a cycle indeed. Let $$$ u_1, u_2, ..., u_k, ... $$$ the sequence of nodes you traversed in the graph where $$$ u_1 $$$ is the node where you started and $$$ u_k $$$ the first repeated node (where you detected the cycle).

      If $$$ u_k \neq u_1 $$$ then there are at least two nodes that lead to $$$ u_k $$$. Now if you think about the graph of the reversed moves, it is also a functional graph with the reversed edges. So a node with indegree $$$ x > 1 $$$ in the original graph implies a node with outdegree $$$ x > 1 $$$ in the reversed graph, which is functional. That is a contradiction.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +73 Проголосовать: не нравится
  1. I don't think it's appropriate to prevent a lot of gifs in the statements. It took me about two minutes to load all things in problem A and D.

  2. I think E is a bit boring. Almost immediately after I saw the problems I came up with the solutions, all that remained was to implement them.

Anyway, thank you for a very well prepared contest! I enjoyed the problems, especially the cool pictures in problem A and D, just the waiting time for the statements to load is really unpleasant xD

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody share the references to calculate the irreducible fraction in general for the problems in which the answer is a fraction?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    You calculate everything modulo $$$10^9 + 7$$$ (or whatever) and if you need to divide any time in your algorithm, just use Fermat's little theorem (so to calculate $$$\frac{a}{b}$$$ you calculate instead $$$ab^{10^9 + 5}$$$). The "irreducible" part doesn't really matter.

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

speed forces again and again and again :(

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please explain to me his/her Problem C solution? I made 4-5 unsolvable equations and tried solving them for 1.5 hours only to find that they can't be solved (T~T).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do a binary search on the answer.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

    Let's do a binary search. We need to check if we can operate so that each pile of stones has at least $$$mid$$$ stones. Notice that if we traverse the pile of stones by their index, from largest to smallest, we can know how many stones can be removed from the pile at most. So we can just greedily move the stone forward.

    Note that the number of stones that can be moved forward in the $$$i$$$-th pile cannot exceed the number of stones in the initial pile, so you need to update $$$d_i \leftarrow \min(d_i, a_i)$$$. The total time complexity will be $$$O(n \log V)$$$.

    Submission: https://codeforces.me/contest/1623/submission/140945479

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Use binary search.

    Suppose you have a function f and it’s inverse f’. Suppose computing f is straightforward and easy but f’ is tough and you want to compute f’(x). Then sometimes it is easier to search for y = f’(x) such that f(y) = x.

    Let us take an example for computing cube root of x. It is straightforward and easier to search for a number y such that y^3 = x than to compute x^(1/3).

    I hope it helps.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody help me to find out a missing edge case for my first problem's solution?

code
  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    you must check for min(cd-cb, 2*(n-rb)+rb-rd)) in the case where cb<cd and likewise when rb<rd

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Each case should have some sort of min calculation. For example, in the (cb < cd) else case, you should still be checking (2*(n-rb)+rb-rd).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    10 10 9 1 8 10 try this

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You have the right idea, but you're not considering the case when the robot "bounces" on the horizontal side, and reaches the line of the dirty cell before reaching the column

    As a side note, 2*(m-cb)+cb-cd could be simplified to 2*m-cb-cd

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any readable solution for B? Please help! :))

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i simulated all the process using recursion, you can go check it out

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Consider the interval $$$[1, n]$$$, and let's say Bob broke it in point $$$d$$$. If $$$d > 1$$$, then somewhere in the process the interval $$$[1, d-1]$$$ was chosen. Let's consider all intervals that start at $$$1$$$, and let $$$x$$$ be the largest index such that $$$[1, x]$$$ was chosen. Notice that no interval other than $$$[1, n]$$$ can contain $$$[1, d-1]$$$, and thus, we have that $$$x = d-1$$$. If $$$d = 1$$$, then the only interval that starts at $$$1$$$ is $$$[1, n]$$$.

    Implementation:

    I preprocessed a vector of sets ends, such that ends[i] is the set of all $$$x$$$ such that $$$[i, x]$$$ was chosen. I then sort intervals by their respective lengths, and process them in order. When processing the interval $$$[l, r]$$$, I remove $$$r$$$ from the ends[l] set, and see if the set is empty. If the set is empty, then $$$d = l$$$. Otherwise, $$$d$$$ is the largest number in the set

    Code
»
3 года назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

// ignore — a wrong test case example

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Video Solutions for A,B,C in case you are interested.

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +69 Проголосовать: не нравится

Personally, I think 5 problems is not enough to form a contest. Since there are too few problem, it will always happen that it is unbalanced, and there is a huge difficulty gap between two problems. Codeforces will become Speedforces, if you are not fast enough, or even bad internet, you are finished.

For example, problem C is expert level problem, and problem D and E are master and grandmaster level. Solving 3 problems will make the ranking ranges from 300 to over 2000, and the rating will make very huge difference.

A balanced div 2 contest should at least have 6 problems with the following:

A: newbie level (800-1000),

B: newbie or pupil level (1000-1300),

C: specialist or expert level (1400-1700)

D: expert or candidate master level (1600-2000)

E: master or grandmaster level (2100-2500)

F: grandmaster level above. (>=2500).

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    There used to be another problem, but there was a problem with constant optimization solutions getting accepted, so it had to be scrapped.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      To be fair the intended solution is still 2-3 time faster compared to your solution with the latest constraints. But the thing is, I NEED to support JaVa, which is very painful to optimize. And, the Java solution still works pretty fast on my machine. I don't really know how come it ran a lot slower on Polygon.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Agree, as a 1900 level participant, I feel painful as I spent 1 hour getting the correct formula for problem D and realized I had no time to code it.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem B: Any idea why this test

1
2
1 1
2 2

gets Validator 'validator.exe' returns exit code 3 [FAIL The given ranges are not from a valid game (test case 1)]

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    For n=2 there must be 1 2 range since set start from (1,n)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      weird. Hm. Seems like I do not understand something in this problem. Could you please explain why this test case fails with the same error?

      1
      3
      1 3
      1 1
      2 2
      
      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Ohhh. Now I get it. We literally should work with segments and cannot split them other than by Bob's actions.

        I solved a different problem, but my solution happened to work on this one as well XD

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        instead of 1 1 or 2 2 it should contain 1 2 or 2 3. I think I misunderstood the problem as well during the contest, but now reading it back I get it clearly.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        If i simplify the problem statement then initially you have range (1,n)

        On each step take 1 number d from range and break the range into two ranges.

        1 range contains number smaller than d and other contain numbers greater than d.

        Now in your test case initially you have (1,3). If you break it at point d=1 then set will contain (2,3). On next step remove either 2 or 3. Other remaining range will be (3,3) or (2,2) respectively.

        If you break at d=2 then set will contain (1,1) and (3,3)

        If you break at d=3 the set will contain (1,2). On next step if you take d=1 the remaining range (2,2), other wise (1,1)

        But test case you made is possible in no way

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Its missing this tc: 1 2

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why B is easier than Problem A

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Both are text understanding problems in first place, so it is arbitrary which one feels more or less complecated.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      And reading the problem A statement is so much harder because of these animated pictures flashing into your face. I ended up skipping the contest exactly because of this single reason. I'm not epileptic, but it still felt very uncomfortable.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Tle in test 6 in B (BFS) Can someone help... Link:- https://codeforces.me/contest/1623/submission/140934881

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Video editorial for anyone looking (Problems A to C)

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Hello! I found some perplexing behavior with the online judge:

Problem: A

Issue:

  • the same code gets AC with pypy3/python3 and TLE with pypy3-64

  • with a small alteration (no difference logic-wise) gets AC with pypy3-64

Submission details: https://codeforces.me/contest/1623/submission/140947850

Could someone enlighten me what's going on here? Could an admin help look into it if it's some interpreter issue?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

Thanks for the contest! Here are my thoughts(as I have only recently "unlocked" unrated Div2s):

Problem A
Problem B
Problem C
Problem D
Problem E
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

For problem D, after counting the cycle with all possible step number, how to use these information to get the result of the problem(in a brilliant way)? I guess I can force each of them have same denominator and doing the mod operation to every one, but I wonder if there's some brilliant way to do these thing?

Any idea?

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится

    Here was my solution:

    We only ever have the possibility of cleaning the target, if we are at the same row or column as the target. When we start traversing the matrix as given in the statement, we end up with a graph which has a chain of vertices (possibly of size 0) followed by a cycle.

    For the chain and the cycle, let's store the number of moves we took to reach a vertex $$$v$$$, for all vertices $$$v$$$ such that $$$v$$$ is at either the same row or same column (or both) as the target. I call these vertices "potential vertices".

    Say the chain had some potential vertices $$$c_1, c_2, \dots c_k$$$ at distances(moves) $$$d_1, d_2 \dots d_k$$$.

    Also, say the cycle had potential vertices $$$C_1, C_2 \dots C_K$$$ at distances $$$D_1, D_2 \dots D_K$$$.

    Let us consider only the cycle first. Once we have entered the cycle, the expected time to clean the target is:

    $$$\begin{align} f = (\sum_{i = 1}^{K}(1 - p)^{(i-1)} *p *D_i )+ (1 - p)^K*(cycle\_size + f) \\ \implies f = g + a(b + f) \\ \implies f = \frac{(g + a*b)}{1 - a} \\ \end{align}$$$

    Now, the total expected time:

    $$$F = (\sum_{i = 1}^{k}(1-p)^{(i - 1)}*p*d_i) +(1 - p)^k*f$$$
    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      Actually, there is always no chain before the cycle. This is because after lcm(2 * n — 2, 2 * m — 2) moves you will be in the starting vertex.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +37 Проголосовать: не нравится

Thanks for this super nice round !

IMO the problems were all interesting and educative. I hope to see more rounds from Vietnam :)

Here are my thoughts about each problem

A
B
C
D
E

PS: The gif in problem A was incredible !! darkkcyan did you use the tool from 3blue1brown to make it ?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    yeah in prob C dumb me always thought of a solution preceding "3 --> n" but the key was to start from the end.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Usually when you are stuck on a problem it's a good idea to try a different approach and change the way you are viewing the problem, now you'll know that you need to try thinking backward :p

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Thank you so much for participating and feedback! Yes, the library is called Manim. I will also public the source code for animation in the editorial.

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C: Is there a way to solve this problem by following the order "3 --> n".

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hey, ive solved c with binary search but was wondering whether this would work as well:

First we find sufix that has minimum average value. Lets say that this value is some k.

Does it stand that the answer is k, k-1 or k-2? Or sth similar?

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Will the first to solve every problem be published? darkkcyan

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I saw some comment explain how to use binary search to solve the Problem C. I encounted same kind of the problem but I still cannot solve it =(

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    step 1. function "check" to answer the question, is it possible to get the minimum value M for the source array. check it in one pass of the array from last elem to first

    step 2. get a estimate for the minimum and maximum of M (minimum is min elem of source array, maximum is min(a[i] + a[i+1]/3 + a[i+2]/3*2)

    step 3. binary search — check with M=(min + max)/2. if true, move min, if false, move max

»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

An important note : When you see a problem that asks you to minimize the maximum value of something or maximize the minimum value of something then Binary Search absolutely works.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    based on latest contests, binary search will be in mediun task with 90% propability)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    More generally, if you can show the monotone of the function that you are checking (that is, before some value, the checking function returns false, and after that, it returns true), then you can always do binary searching. There are problems that ask to maximize the minimum (or minimize the maximum) that do not involve binary search, especially when the function is not monotonous.

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

When will rating be updated?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

blease giv problems with shorter statement O_o

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope rating will be updated before today's contest

»
3 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

unrated?

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

The start time is unusual

The Update time is unusual, too :(.

»
3 года назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится
Meme
»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

was this rated?

»
3 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

The time has come when "is it rated?" gets upvotes.

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Sorry for the noob question, is this a unrated contest or do the results take time to reflect in the profile?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The similarity that you found between huddai/140930801 submission and ProgrammatorZihad/140928467 submission is completely coincident. I think the similarity between his debugging template and mine causes you to suspicious about us. But I collect the template from the internet (maybe from a codeforces blog) and I think he also collects the debugging template from the same source. Would you mind considering this matter?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

the round became unrated for me because they found similarities between my solution 140930801 for the problem 1623C with ProgrammatorZihad/140928467. But I think they have done something wrong. I didn't use any third-party information(without template) for my submission.

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I just want to say that I enjoyed the C problem :)