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

Автор Vladithur, история, 22 месяца назад, По-английски

Hope you liked the problems!

(from thanhchauns2) Before the round starts

1768A - Кратные факториалу

Author: thanhchauns2

Hints
Tutorial
Solution
Feedback

1768B - Быстрая сортировка

Author: Vladithur Preparation: Vladithur and Alexdat2000

Hints
Tutorial
Solution
Feedback

1768C - Поэлементное ограничение

Author: thanhchauns2

Hints
Tutorial
Solution
Yet another better solution
Feedback

1768D - Удачная перестановка

Author: Vladithur Preparation: Vladithur and Alexdat2000

Hints
Tutorial
Solution
Feedback

1768E - Частичная сортировка

Author: thanhchauns2

Hints
Tutorial
Solution
Feedback

1768F - Великолепный прыжок

Author: Vladithur Preparation: Vladithur and Alexdat2000

Hints
Tutorial
Solution
Shorter solution (tfg)
Feedback
Разбор задач Codeforces Round 842 (Div. 2)
  • Проголосовать: нравится
  • +237
  • Проголосовать: не нравится

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

From SPyofgame during the contest:

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

First time ranked top100 in div2. Hope for no FST!

Update: It's frustrating that I always get downvoted and don't know the reason

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

Permutation Forces !

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

Delivered so fast..

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

2023 should not be a permutation

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

love the fast editorial

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

I got the idea for C but not able to implement it. :-)..

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

Can anybody help me to figure why this code is not accepted??? https://codeforces.me/contest/1768/submission/188117185

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

You know what it feels like when you finish E when there're only 10 sec left but fail to submit the code before the last second?

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

Amazing , was very curious for fast tutorial especially for Problem C.

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

Hi guys! although the editorial they've provided is great! still if you want a video format editorial you can find it here

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

PermutationForces?)

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

"it took me 2 minutes to actually prove the solution"

and it took me probably a minute and a half (may be inaccurate) to find out that $$$k! + (k-1)! = (k-1)!(k+1)$$$ and the rest of the proof is just factoradic blah blah

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

i submitted 6 unsuccessful attempts so i lost 300 points in the contest? if there is a maximum amount u can lose, how much is it?

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

    No matter how many times you submit for a problem, you get at least 30% of points if you solved it finally.

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

    If you have wrong submission for problem $$$X$$$ you will get 50 points less then you usually would on that problem.

    If you have few wrong submissions on a problem you didn't solve, you won't lose any points.

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

Why so tight TL on E.

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

Actually there's O(n) solution for C. We don't need to do any sorting. We can just count the occurence of 1-n and let occ[i]= the times i appeared in array a[]. if there's some occ[i]>2 there's no answer. Then we build two list more[] and less[]. We iterate for i from 1 to n, if occ[i]==0 we add it to less[], if occ[i]==2 we add it to more[]. since 0<=occ[i]<=2, the size of more[] and less[] will be equal. then we iterate for more[i] and less[i] reversely, if some more[i]<less[i] there's no answer. If there's no such i, we can construct p and q: for each pair of more[i] and less[i], let's call they M and L, and j = the smaller index where a[j]==M, k = the larger index where a[k]==M, we let p[j]=q[k]=M, q[j]=p[k]=L. For those j which a[j] appear only once, we just let p[j]=q[j]=a[j].

My submission:188076704

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

It's a well know fact that n — cycles is the minimum number of swaps to get 1, 2, ..., n.

Can someone explains me this ? and where is this well know ?

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

    each cycle of length $$$l$$$ needs $$$l-1$$$ swaps to be sorted, you can try it yourself

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

nice E...stuck in case f=2 too longgg...

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

codeforces!

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

F is so fantastic! It's hard to solve, but not hard to understand the solution.

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

Can we see pretest after the contest. This submission failed pretest 2: Link

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

    Pretest 2 is every combination possible for $$$n \leq 5$$$, you can write a code then generate pretest 2 yourself.

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

I'm looking for problem like today problem D and C. Specially problems on arrays that can be transformed into problems on graph.

Example 1 : You want to obtains array b from array a with some specific operation

Example 2 : You want to obtains array a and b from array c with some specific operation

Example 3 : optimizing or computing something on an array after some operation (This turns out to be somewhat related to paths on a graph ...)

In almost all the solutions we need to build some graph with specific edges. I don't know how to tackle that kind of problems.

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

F let me feel :F

D let me feel :D

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

I got o(n) for C lolol. 188093045

nvm its o(nlogn)

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

Since I didn't implement, please point out if I did anything wrong on F, or if my approach would TLE.

After the monotonic stack observation, it should be possible to use a kinetic tournament on quadratics to handle cases with $$$min(a_i,\ldots, a_j)=a_i$$$ and li-chao tree or another kinetic tournament otherwise. The time complexity would be $$$O(n2^{\alpha(n)}\log^2(n))$$$.

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

I cannot understand the editorial of Problem C, which says there are (i — 2)*2 + 2 numbers. (there can be a repetition of numbers in p and q) also, why is this a contradiction?

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

    What do you mean by "there can be a repetition of numbers in p and q"? $$$p$$$ and $$$q$$$ are permutations, they can't have any repeated numbers (although the same numbers that appear in $$$p$$$ also appear in $$$q$$$ since they are both permutations from $$$1$$$ to $$$n$$$).

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

In the editorial of problem E, when calculating the intersection for f(p)<=2, the sum should be sum(i=0...n) instead of sum(i=1...n). Please fix it

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

I had a slightly different $$$O(n)$$$ 188071468 from the one given for Problem C.

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

No CHT solution for F? That's very interesting.

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

    It is possible to use it to solve the second case, but you'll have to squeeze it into the tight ML.

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

It is a well know fact that n−cycles is the minimum number of swaps needed to get the permutation 1,2,3,…,n from our initial one (in other words, to sort it).

Can anyone Please provide me the material where i can see this tutorial and learn . Thank You!!.

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

Can anyone explain E in a simpler way ? I am having a hard time understanding the editorial..

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

Ugh my solution to C FST'd due to TLE can someone tell me why :(( https://codeforces.me/contest/1768/submission/188118022

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

Is it possible for you to make a report on the channels that download solutions on YouTube during the contest? Very thanks.<3

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

Maybe I missed something, but why there is O(n*sqrt(n)) with [n, n-1, n-2, ..., 1] array? Or any similar.

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

    In this subcase, $$$a_j < \sqrt{A}$$$.

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

    I think this time aj is smaller than sqrtA, consider all the cases of such j, the total compexity of the j with same value will not exceed n, so the overall complexity will not exceed..nsqrtA sorry my poor english

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

⌊n−w+k−1⌋/k
could you please eplain me why we add K-1 with n-w ? .

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

    so as to do the ceil operation otherwise it's by default floor operation as the integer division truncates anything after the decimal point

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

I'm having a hard time trying to understand the intersection formula for $$$f(p) \le 2$$$ from E's editorial. Can you please proofread the 'sketch and calculation' spoiler and fix some mistakes/typos?

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

    I modified it a little bit, maybe you'll find it easier to read.

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

      I mean I read for example this sentence:

      In the last $$$n$$$ numbers there are $$$n$$$ numbers in range $$$[n+1,2n]$$$, we have used $$$1$$$ numbers for the first $$$n$$$ numbers. There are $$$C^n_{2n-1} \cdot n!$$$ cases.

      I think you wanted to write:

      In the last $$$2n$$$ numbers there are $$$n-1$$$ numbers in range $$$[n+1,2n]$$$, we have used $$$1$$$ numbers for the first $$$n$$$ numbers.

      And if this is the case, then I don't really understand the $$$C^n_{2n-1} \cdot n!$$$ formula.

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

        No, there are $$$n$$$ numbers, not $$$n - 1$$$. Since we used $$$1$$$ number to fill in the first $$$n$$$ numbers, there are only $$$2n-1$$$ options to choose for the last $$$n$$$ numbers, since they must be in range $$$[n + 1, 3n]$$$. I think the $$$n!$$$ part is easy to understand.

        Edit: okay I think I spotted the wrong thing, it is fixed.

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

          Ok, I see the interval in the third case was fixed. Now I get it. Thanks!

          I still want to add something, maybe someone finds it helpful. I don't find the $$$n!$$$ parts easy to understand as they are right now in the editorial, I find them a bit unnatural if not just 'wrongly' explained. The third case actually counts the number of ways to fill the last $$$n$$$ positions. What are the other two cases counting exactly, including the $$$n!$$$ 's, explained with words?

          This is how I would split it, each part counting one third of the positions:

          • Take $$$n-i$$$ elements from $$$[1, n]$$$ and $$$i$$$ from $$$[n+1, 2n]$$$. This makes $$$n$$$ elements for first $$$n$$$ positions, and we take all the rearrangements. This is $$$C^{n-i}_n \cdot C^i_n \cdot n!$$$
          • As you explained, we need $$$n$$$ numbers in the range $$$[n+1, 3n]$$$ for the last $$$n$$$ positions, but $$$i$$$ of them were already used in the first $$$n$$$ positions, so we only have $$$2n-i$$$ left to choose from. Also, we can rearrange them. This is $$$C^n_{2n-i} \cdot n!$$$
          • The first $$$n$$$ and last $$$n$$$ positions are filled. The rest are the center $$$n$$$ positions. Rearrange them freely. This is just $$$n!$$$
          • »
            »
            »
            »
            »
            »
            22 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            This is much clearer, thanks a lot.

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

            Kudo for lbm364dl, great explanation that help me a lot, take a long time to understand the editorial before found your comment.

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

            Sorry for late reply, suppose we have $$$n$$$ fixed indexes for the numbers in range $$$[1, n]$$$, then there are $$$n!$$$ cases for these numbers switching places with each other, the second and third $$$n!$$$ are exactly the same.

            In conclusion:

            • The combinatorics is how we choose indexes for number in a range.

            • The factorial is the number of cases after having fixed indexes.

            The third one is $$$n!$$$ because we already chose indexes for $$$n$$$ numbers out of $$$2n$$$.

            Anyway thank you for providing a much clearer explanation for this problem!

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

Hi guys I have made editorial videos on A,B,C,D and uploaded on the channel — https://www.youtube.com/@GrindCoding, you can have a look and let me know if you like the explanation or please provide your valuable feedbacks.

[D is currently being processed by youtube so might take a few mins to upload]

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

There's no reason to make the mod not fixed as something like 1e9 + 7 in problem E. Any fft solution that passes that mod will pass for any other mod that you might ask for.

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

Any idea why I got Wrong Answer instead of Runtime?

During the contest in problem C I was getting WA so I tried to modify my solutions but now that the we can see the test cases it says "wrong output format Unexpected end of file — int32 expected"

The thing is that I used an array of size $$$10^5$$$ instead of $$$2 \times 10^5$$$

WA code

AC code

So sad, with this modification I got AC with my first attempt :(

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

In problem D,

Turns out that we can easily calculate cycles′ if we know cycles:

cycles′=cycles+1 if the vertices k and k+1 were in the same cycle in the initial graph, cycles′=cycles−1 otherwise.

Can someone explain this???

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

thanks for the great round <3

finally become pupil after 82 contest !!

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

Somebody please help me with my submission of problem C . https://codeforces.me/contest/1768/submission/188118465 Can't able to detect error.

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

Can someone explain for problem Lucky Permutation:

Turns out that we can easily calculate cycles′ if we know cycles:

cycles′= cycles +1 if the vertices k and k+1 were in the same cycle in the initial graph, cycles′= cycles −1 otherwise.

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

    It's not easy to explain. I noticed this by using brute force on some small cases, but I can't prove it until the end of contest.

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

    Cycles are for sort the array, we want 1 inversion. Let's say $$$i$$$ is connected with $$$x$$$ and ($$$i$$$+1) is connected with $$$y$$$.for inversion, we break the link from $$$i$$$ to $$$x$$$ and ($$$i$$$+1) to $$$y$$$ and make a new link from $$$i$$$ to $$$y$$$ and ($$$i$$$+1) to $$$x$$$. That's it, now if we analyse breaking and making link for $$$i$$$ and $$$i$$$+1 ,

    we can see if $$$i$$$ and $$$i$$$+1 are from the same cycle they will brake the cycle and we have 2 cycles from the 1 cycle.

    If $$$i$$$ and $$$i$$$+1 in different cycle they will join together and make 1 cycle from joining 2 cycles.

    i hope it is understandable.

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

"If we iterate from the smallest value to the top, there will be scenarios where all the remaining positions i will result in max(p[i],q[i])≥a[i] because you don't have enough smaller integers." This is written in the tutorial of problem C. Can anyone pls provide me a testcase where this scenario happens?

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

    5 5 2 2 1

    In this case, there are no enough place for 3,4,5 to put in.

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

      But this test case anyways has no solution, provide a test case in which iterating from the smallest value give wrong answer.

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

Why does my submission for C give TLE although it looks nLog(n).

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

    You are using the function upper_bound(something). Instead, use setname.upper_bound(int). The one you ar eusing can run O(n) sometimes and is bad. The one I mentioned uses binary search on sets and is much faster

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

can anyone please help me in figuring out why is this code of mine giving runtime error on test 7? tried enough not able to figure out.188129954

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

F is cool!

Is "1. min(ai...aj)>=A and 2. min(ai...aj)<A" (in F's Tutorial) typo ?

I think they should be sqrt(A).

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

Got the idea for D after the contest lol

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

Video Solutions for A-E

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

Nlog(n) code giving Tle for problem C please help! here is the code 188134958

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

    You are using the function upper_bound(something). Instead, use setname.upper_bound(int). The one you ar eusing can run O(n) sometimes and is bad. The one I mentioned uses binary search on sets and is much faster

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

      In vector upper-bound is log(n) right? So why not in sets?

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

        It is not. The normal upper_bound() function works differently and at worst cases might iterate over the entire vector/set. But there is a special upper_bound() function for sets. Use setname.upper_bound(x). This is actual logn

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

A approach to Problem D using Group theory ,

Link To solution : 188139688

If Permutation is not sorted, then it will contain some cycles, using Cycle Decomposition, we can break the Cycle of length k into** k – 1 Transpose** (Two Length cycles). If Identity transpose ex (1 3) is multiplied to itself ( 1 3 ) => it will cancel the effect , i.e. Elements have been placed to their correct respective location . So to make the permutation sorted, if there are k transpose, we can multiple k identity transpose, thus canceling out the effect and make them sit on their place. Note : sorted permutation means zero Inversion. And at last, do multiple any transpose of adjacent elements ( 3 4 ) or (1 2 ) or ( 5 6 ) , etc. to get One Extra Inversion .

So, using DFS one can check for Cycles, find the length of cycles, cycle length – 1 is the transpose.

So answer = total no of transpose from all cycles + 1 [ General case ] (for last extra One Inversion that is been added on top of sorted permutation).

There is an edge case, what if one adjacent transpose is already present in one of the cycles, For example (1,2) is already present, and this contributes to only one Inversion, so we can take help of already present good transpose for this case note: we only need any One good transpose (adject transpose) . Let’s say good transpose is T , so first , in general case , we will multiply T with T to cancel out T and make permutation sorted, then again multiply T to add extra one inversion . So we can skip multiplication of T two(x2 ) times , because at last we want to use T as good transpose .

T x T x T = T

( extra multiplication of T two times ) so we can subtract 2 operation from the general case answer .

Ans = ( transpose + 1 ) – 2 [ when good transpose is already present in any of the cycles

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

Fucking shit I have been associated with a psychopath

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

Isn't a case possible in D where number of cycles will remain same?

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

Why does my solution for C work when using stack but not unordered_map? Solution using unordered_map: Solution Solution using stack: Solution I am doing the same thing in both of them, except it works when I use stack instead of unordered_map. I see it gives wrong answer on test case 2, but I can't see the test case. Can someone give a test case that doesn't work for unordered_map? Thanks.

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

    When you do it=extra.begin() when extra is an unordered_map, It's not guaranteed which element you will get, so probably it->second==true for both it you get for a certain i, which cause i appear 2 times in q.

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

      But I'm taking the iterator, then erasing it before I get the next element. Shouldn't it delete the one I just used?

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

        It's not "getting the one just used". It's "There might be multiple entries where it->second==true and you get 2 such entries for one x, then you put two x in q"

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

The problemset should should have a tag for permutations, to practice for these kinds of problems.

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

Can someone explain why there is a +k in the final result of problem B, and not just (n-w)/k??

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

    The reason is because we want to using ceiling division. If we used (n — w) / k, we would round down.

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

Yet another $$$O(n)$$$ solution for C, but can be implemented more easily. Without the headers, it's only 700 B long with two for loops.

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

Is $$$O(n)$$$ solution for C too hard to think? Why not hack $$$O(n \log n)$$$ solutions?

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

Can someone help me to find the reason for TLE in Problem C for the submission 188102874

But an AC for the submission 188105380

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

The Submission 188119572 is Successfully Hacked but the Participant got points for the problem. How is This possible?

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

Concise solution for D:


#include <bits/stdc++.h> using namespace std; typedef long long ll; void solve() { ll n; cin >> n; vector<ll>v(n); for (int i = 0; i < n; i++) cin >> v[i]; vector<ll>col(n); ll c = 1, comp = 0, pos = 0; for (int i = 0; i < n; i++) { if (col[i]) continue; pos = i; while (col[pos] == 0) { col[pos] = c; pos = v[pos] - 1; } comp++; c++; } ll ans = n - comp; for (int i = 0; i < n - 1; i++) { if (col[i] == col[i + 1]) { ans--; break; } } if (ans == n - comp) ans++; cout << ans << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { solve(); } return 0; }

~~~~~

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

I'm still curious about that "the minimum number of swaps" theory in problem D, is there any prove of that theory (blog or something)?

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

About D, How they know the way to solve this problem during the contest? I mean is this a classical question ? Or they just figure out?

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

    i'm interesting of how could they just know whatever what is swaping in a cycle it will only minus 1,and whatever what is swaping between two cycle ,it must cost one movement to change it to the answer Do they prove it or just consider it should work

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

Though my rating falls drastically in this contest. I love both the contest and the editorial. Keep organizing such contests Vladithur ❤️.

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

Loved the contest, amazing problems, amazing editorial!!

By the way,
for problem C: 1768C — Elemental Decompress

"There is also another way that you can skip testing if max(p[i],q[i])=a[i]) is correct."

Another Way Here

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

Can anyone explain or tell about resources where i can learn about counting the number of cycles in a directed graph. as a can't find it online. thanks

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

I am just really glad this contest happened and would like to thank the authors of this round, as finally I could reach expert after this round.

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

I love F!I think it is a quite good problem!

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

In F tutorial,Is the "Just maintain the leftmost occurences" for the 2.1 cases a typo?Seems that it needs to maintain the rightmost occurences<j from 1 to √A

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

Problem F is awesome. Couldn't solve it during the contest. After the contest, I looked at the "$$$a_i \le n$$$" hint from the editorial and solved it from there :) Sometimes just stressing a part of the statement can help you solve a problem :)

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

F is a really good problem, I thought $$$O(n\sqrt n)$$$ solution for a long time during the contest but still did not know how to solve it. But later I was amazed by the tutorial of problem F :)

The facts to solve this problem are easy to understand and easy to prove, but it's really hard to find them :)

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

Video solutions for A,B,C

https://youtu.be/erOqAwknRJU

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

Need some help with a failed test case in problem C. 193152726

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

return (38912738912739811 & 1) return __factorial(n * __number_of_sides_of_a_triangle) wtf lol

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

Easy O(n) solution for problem C : 285672450