darkkcyan's blog

By darkkcyan, history, 3 years ago, In English

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

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +199 Vote: I do not like it

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

»
3 years ago, # |
Rev. 3   Vote: I like it -17 Vote: I do not like it

Scoring Distribution?

UPD: Why downvote?

UPD2: Now it's updated.

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

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

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

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

Classic cuban granny postcard
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

darkkcyan orz

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

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

»
3 years ago, # |
  Vote: I like it -73 Vote: I do not like it

hi

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

love :3

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

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

»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Wow tourist is a tester

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

Oops wrong announcement Thanks @below

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

    I think you have commented on the wrong announcement.

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

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

»
3 years ago, # |
  Vote: I like it -45 Vote: I do not like it

Is this contest rated for Div 2 ?

»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

They will WA until they die !

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

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

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

Rating Distribution ???

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it
    Rating Distribution
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think he meant points for tasks

      sometimes they are written in the announcement

      like: 500-1000-1500-2000-2500

»
3 years ago, # |
  Vote: I like it +62 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

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

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

two div 2 contest on 2 days, problemsetters are wonderful

hope i got positive delta tdy

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

Any interactive questions in the contest?

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

    No, there will not be an interactive problem in the contest.

»
3 years ago, # |
  Vote: I like it -35 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

hope will have great time and not to lose expert.

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

Updated

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

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

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Is CF running slow?

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it
  • Problem A is hard :+)
  • many contestant said good Bye after seeing problem A (like me ) :p
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +39 Vote: I do not like it

The Gif in problem A made me so nervous

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

good job

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Cool gifs in A

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

Nice contest
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes

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

      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 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

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

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

        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 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it -61 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

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

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

        Agree I think E is just too easy for div2E.

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

      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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      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 years ago, # |
  Vote: I like it +18 Vote: I do not like it
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      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 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

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

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 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

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

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

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
    Rev. 4   Vote: I like it +16 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

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

        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 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Well, I guarantee it to be simple. My Pascal code is only 50+ lines.

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

        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 years ago, # ^ |
      Rev. 3   Vote: I like it +11 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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 years ago, # |
Rev. 2   Vote: I like it +73 Vote: I do not like it
  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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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 years ago, # |
  Vote: I like it +7 Vote: I do not like it

speed forces again and again and again :(

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

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do a binary search on the answer.

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

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was wondering if moving forward from 3 to n while checking for possibility feasible?

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

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    10 10 9 1 8 10 try this

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

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

    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 years ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      Yes, i got it.... I implemented my approach only and got it after contest....Ughhh... I wish i did this earlier ;((((((((( Thanks by the way your solution is quite good and understandable! Nice

      here is my solution

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

// ignore — a wrong test case example

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

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

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 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

      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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

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

      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 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Its missing this tc: 1 2

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

why B is easier than Problem A

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

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

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

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I had problems distinguishing dr and rd, as well as dc and cd from each other.

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

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

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

Video editorial for anyone looking (Problems A to C)

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

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 years ago, # |
Rev. 2   Vote: I like it +38 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Wow! Thank you for participating and feedback! I really appreciate it. <3

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

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 years ago, # ^ |
    Rev. 3   Vote: I like it +21 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Ah yes, I complicated it unnecessarily yet again! Thanks!

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

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      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 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      thanks!! I hope that more problemsetters will do the same kind of animations in the future

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

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

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

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 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Will the first to solve every problem be published? darkkcyan

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

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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 years ago, # |
  Vote: I like it +8 Vote: I do not like it

When will rating be updated?

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

blease giv problems with shorter statement O_o

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

I hope rating will be updated before today's contest

»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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

    Lmaooo

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

      And did you know, there is also animated editorial :catthink:

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

unrated?

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

    It seems to be unrated, cause I opened my unrated contest section at my profile and I found it at there

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

      It's not, Any new contest you join will be found in unrated till rating changes occur (i.e : we still don't know) (but it will possibly be rated)

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

The start time is unusual

The Update time is unusual, too :(.

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

was this rated?

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

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

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

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

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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