Vladosiya's blog

By Vladosiya, history, 3 years ago, translation, In English

1650A - Deletions of Two Adjacent Letters

Idea: MikeMirzayanov

Tutorial
Solution

1650B - DIV + MOD

Idea: Vladosiya

Tutorial
Solution

1650C - Weight of the System of Nested Segments

Idea: myav

Tutorial
Solution

1650D - Twist the Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1650E - Rescheduling the Exam

Idea: senjougaharin

Tutorial
Solution

1650F - Vitaly and Advanced Useless Algorithms

Idea: Aris

Tutorial
Solution

1650G - Counting Shortcuts

Idea: MikeMirzayanov

Tutorial
Solution
  • Vote: I like it
  • +73
  • Vote: I do not like it

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

Thank you codeforces for this contest!

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

my solution for problem D using deque: https://codeforces.net/contest/1650/submission/148940490 I think it's easier, if you know data structure.

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

    Yeah+

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

    please explain your solution

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

      First, The problem is he performed n operations sequentially. At the i-th operation, Petya chose the first i elements of the array and cyclically shifted them to the right number of times.

      we have the final array ! and before operations we know that the array is sorted

      so how can we do this operations reversely to sort the array ? _we will start from n instead of 1 _and shift left instead of shift right

      first we want to make the last number in the array equal n , how many times of shift left we can do to make that ? just loop make shiftes untill it happen and then now we will search for n-1 to put it in position n-1 in the array so to make the same thing easier we will remove n from the array, we won't need it again.

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

    Thank you!

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

E has an answer binary search.

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

    Can you please explain your approach ?

    Thanking you in advance

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get a small counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

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

Ok

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

Resolved

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

in the following statement

numbers from r−rmoda to r that have an incomplete quotient when divided by a equal to ⌊r/a⌋

1) can someone expain me the meaning of the incomplete quotient(does it mean that it will give remainder?)

2) How did we arrive at this conclusion?

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

    Can anyone plese explain this.

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

      I find the editorial difficult to understand. Here is my way of explaining a solution to problem B:

      Imagine a 5x7 monthly calendar where the rows represent work week and the columns represent Sunday, Monday, ... to Saturday. Suppose the upper left hand corner of the has the day start with 0. So, the first row are days 0 ~ 6, second row are days 7 ~ 13, and so on.

      Day / 7 represents the work week, the row on the calendar. Day % 7 represents the week day (Sunday=0, ..., Saturday=6), the column on the calendar. Suppose the question is to ask you which day from L (eg 20) to R (eg 29) has the Manhattan distance largest from the origin of the calendar.

      My approach is to check if the L and R are on the same row. If so, then R is the answer. Otherwise, I tried to move R to the closest Saturday on the previous row.

      Hope you get what I mean.

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

      We want to prove that for every number $$$x$$$ in range $$$[r - r \ mod \ a; r] \ x \ mod \ a \le r \ mod \ a$$$; $$$r - r \ mod \ a$$$ is divided by $$$a$$$, because $$$r = a \cdot r \ div \ a \ + r \ mod \ a$$$, it means $$$r - r \ mod \ a = a \cdot r \ div \ a$$$, and $$$a$$$ multiply something always is divided by $$$a$$$. OK, we know that $$$r - r \ mod \ a$$$ is divided by $$$a$$$ and every number in range $$$[r - r \ mod \ a + 1; r]$$$ is not divided by $$$a$$$. That means every $$$x$$$ from range $$$[r - r \mod \ a + 1; r]$$$ has incomplete quotient $$$\lfloor\frac{r}{a}\rfloor$$$. For example, $$$r = 11$$$, $$$a = 4$$$. $$$11 - 11 \ mod \ 4$$$ = $$$8$$$. $$$8$$$ is divided by $$$4$$$ and every num in range $$$[8 + 1; 11]$$$ is not divided by $$$4$$$. $$$\frac{8}{4} = 2$$$, $$$\frac{9}{4} = 2,25$$$, $$$\lfloor(2,25)\rfloor = 2$$$. Maximum in range $$$[8 + 1; 11]$$$ is $$$11$$$, and for maximum value we still get result $$$\lfloor \frac{r}{a} \rfloor = 2$$$ ; $$$\frac{11}{4} = 2,75$$$, $$$\lfloor(2,75)\rfloor = 2$$$.

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

        We want to prove that for every number x in range [r−r mod a;r] x mod a≤r mod a is it because of this fact:- fact that [x/a] is maximum at x=r so if xmoda<=rmoda ,we can put x=r and make both [x/a] and xmoda maximum simultaneously

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

          Yes, but if $$$x = r - r \ mod \ a - 1$$$ we get maximum $$$r \ mod \ a$$$, so we just need to check $$$x = r - r \mod \ a - 1$$$ and $$$x = r$$$.

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

            the more number of times i read the expainations, the more queries i am having( maybe because i am new to advance number theory concepts or it is the wording of the editorial)

            1)how did you arrive at the conclusion that every number in range [r−rmoda + 1;r] is not divided by a.

            i can observe it but i am not able to prove it mathematically

            2) what do we exactly mean by incomplete quotient

            3)why does the editoral say the statement (and are guaranteed to have a value fa less than fa(r)) if we find a x such that x%a > r%a, can't we get a fax>far ( i know that is what we are trying to prove but i want to know if i am interpreting this editorial statement correctly .

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

              Let's have an example: $$$a=7$$$. $$$21$$$ is divided by $$$7$$$, next number that can be divided is $$$21+7=28$$$. Every number in range $$$[21 + 1; 28 - 1]$$$ is not divided by $$$7$$$. So, if number $$$x$$$ divided by $$$a$$$ then $$$x + a$$$ also divided by $$$a$$$ and every number in range $$$[x + 1, x + a - 1]$$$ is not divided by $$$a$$$. $$$r - r \ mod \ a$$$ is divided by $$$a$$$, every number in range $$$[r - r \ mod \ a + 1; r - r \ mod \ a + a - 1]$$$ is not divided by $$$a$$$, we sure that $$$r < r - r \ mod \ a + a$$$, because number $$$a - r \ mod \ a > 0$$$, $$$r \ mod \ a < a$$$.

              2) $$$a \ div \ b$$$ is incomplete quotient or $$$\lfloor\frac{a}{b} \rfloor$$$.

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

finally a div3 contest after 2 month break^^

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

Why havn't the rating changed yet?

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

Why are the ratings not updated yet?

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

Hello there, and thanks for the enjoyable problems.

I liked the last two problems since they can have much to teach for people who are new to DP and graph algorithms.

Problem F was a combination of two merely classic ideas that are good to know for beginners, and the last problem introduces a useful property of the BFS algorithm and the BFS tree.

Thanks to both authors for their cool problems, and I would suggest everyone to upsolve these two problems since they may help you in the future :)

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

Problem statement could be more clearer as I wasted a lot of time in the 3rd question to understand just what I need to print.

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

Can anyone explain G, I'm having a little trouble in understanding editorial.

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

Can the problem D be solved in O(n) time complexity?

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

    I wasted whole time trying that, would be helpful if some did solve it using O(n)

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

Why I used memory search on G and got a TLE :(

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

In problem E is it possible to reschedule one of exams to day one?

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

    yes but that would never help bc the time between the start of the session and the first exam is counted in the answer.

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

where can i found similar problems to G-Counting shortcuts ? i suck at dp on trees/graphs :(

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

Could somebody, please, explain how do we use dp in G-problem?

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

    You store the number of ways to reach a node from source by following a path of min distance and (min distance + 1). Like whenever you're reaching a node from some other node, just ask if the depth of the curr node is equal to min depth or (min depth + 1), based on the ans you get, update your dp values.

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

In problem E , I just used a multiset which stores the difference between every two consecutive exams dates and update it for each element (try to put it in the best place) I think its easier. here it is 148865257

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

    yea my sol was very similar haha, multiset is a lot more intuitive isnt it :p

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

Problem 1650G - Counting Shortcuts can be solved in another way. Calculate for each vertex: distance and number of shortest paths from $$$s$$$ and $$$t$$$ (with 2 bfs). Then we can iterate over all edges $$$\left(u,v\right)$$$. Firstly, vertices $$$u$$$ and $$$v$$$ should be included in same level (same distance from $$$s$$$). Secondly, $$$\text{dist}(s,u)+\text{dist}(v,t)=\text{dist}(s,t)$$$. If both conditions are held, then we can build path $$$s \rightarrow ... \rightarrow u \rightarrow v \rightarrow ... \rightarrow t$$$ with length equal to $$$\text{dist}(s,t)+1$$$. We need to add $$$\text{cntShortestWays}(s,u) \cdot \text{cntShortestWays}(t,v)$$$ to answer. Solution: 150206150

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

    can you explain why vertices u and v should be included in same level?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It prevents us from counting a path multiple times, because any path of length (minimum path length + 1) will have exactly one edge in which two points are at the same level of distance from s.