Shefin_'s blog

Codeforces Round #848 (Div. 2)
By Shefin_, 23 months ago, In English

Hello, Codeforces!

adnan_toky and I are super thrilled to invite everyone to participate in Codeforces Round 848 (Div. 2), which will be held on Feb/01/2023 17:35 (Moscow time).

This round is rated for the participants with ratings strictly lower than 2100. You will be given 6 problems and 2 hours to solve them. All the problems are authored and prepared by adnan_toky and me. To get the 6 problems approved, we needed to propose 12 problems in total sneaky_wink_catto.

UPD: Score distribution: $$$500-1000-1250-1750-2250-2750$$$

We would like to thank:

This is our first round! We've tried our best to make the round enjoyable. It is greatly recommended to read all the problems.

We are looking forward to your participation. Good luck to everyone king.

UPD2: Congratulations to the winners!

Overall:
1. jiangly
2. SSRS_
3. Geothermal
4. BurnedChicken
5. Ormlis

Div. 2:
1. CoCl2_6H2O
2. Joyemang
3. gqh_cpp
4. rainboy
5. NoMentalPowerLeft

UPD3: Editorial is out

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

Comments Comments (294)
| Write comment?
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Super excited bhai

→ Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Looking forward to get an amazing problemset. Super Excited!

→ Reply
»
23 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Super thrilled to participate

→ Reply
»
23 months ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester, I can assure you really good quality problems. The contest in worth spending time. All the setters and testers have put a lot of work and effort. Good luck everyone !!

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    D is so boooooring

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    The problems are so good that I recommend the authors never to propose another contest until they are capable of doing that.

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

      Hello sir, can u tell me ur solution for B please?

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        We have to make the given condition i.e. pos(ai)<pos(ai+1)≤pos(ai)+d false. We can make make this condition false by 2 ways. We can make either the condition pos(ai)<pos(ai+1) false by crossing them in original array using swapping OR we can make second i.e. pos(ai+1)≤pos(ai)+d false by either shifting the ai element left in the original array or by shifting the ai+1 element right in the original array. Out of these three ways the minimum cost way will be the answer. Corresponding code: [submission:https://mirror.codeforces.com/contest/1778/submission/191583606]

        → Reply
        • »
          »
          »
          »
          »
          23 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Oh wow, I completely misunderstood the question. I thought that pos<pos(ai+1)<=pos(ai)+d for ALL I, not for just one. Sooo wow that's unfortunate. I spent all my time solving the wrong question. And now that I look at C, that was also really easy... I hate how bad the explanation for B was.

          → Reply
»
23 months ago, # |
  Vote: I like it +24 Vote: I do not like it

As a tester, the problems are really good and educative. I recommend everybody to participate in this round!

→ Reply
»
23 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Bangladeshi round after a long time. Also the first ever RUETian CF round. Super excited to participate <3

→ Reply
»
23 months ago, # |
  Vote: I like it +38 Vote: I do not like it

As a Tester, I can assure you that problems are really good, and you will enjoy them a lot for sure. So be sure to participate in another amazing Div. 2 round. Orz Shefin_ and adnan_toky.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I have seen very similar comment recently. And it turned out to be slightly different from what I expected.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +35 Vote: I do not like it
      Are you talking about this?
      Spoiler
      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Testers can't find out if the pretests are weak or not, because their solution in testing gets judged for main tests, not pretests.

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

          Yea but evidently in the last unrated rounds, main tests were weak also because tester's code passed the main tests.

          → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

As a tester, I hope everyone enjoys the problems as much as I did! :p

→ Reply
»
23 months ago, # |
  Vote: I like it +33 Vote: I do not like it

as a tester, I tested, so as a participant, you should participate :D

→ Reply
»
23 months ago, # |
  Vote: I like it +2 Vote: I do not like it

So excited after seeing another Bangladeshi Round!!!!!!!

Hope it will be a good contest & all the contestant will enjoy the problemset.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Inb4, clash with Codechef Round comments :kekw:

→ Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

As a Bangladeshi participants, I am so excited,,,, proud of you bro

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow..Another Bangladeshi Round.

Super excited

→ Reply
»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

That is my birthday!

→ Reply
»
23 months ago, # |
  Vote: I like it +44 Vote: I do not like it

As a Tester, the problems tasted sweet to me, I hope the same for you too! :p

→ Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

As a tester, I can assure you the problems are very quality and amazing. Good luck for everyone

→ Reply
»
23 months ago, # |
  Vote: I like it +17 Vote: I do not like it

As a Robot, I will be taking place in the Round. Don't get scared Humans.. -- ChatGPT

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally non-chinese round. Maybe I can get positive delta .

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Now it's toky_bhai round, not tourist round...

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

This is 4th round from Bangladeshi setter. Really a proud moment for aspiring Competitive Programmers from Bangladesh. Super excited to participate in this round.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Clashing with Codechef Round, I know most people including myself would prefer Codeforces, but I don't wanna miss any of them. Past few rounds of codechef had some interesting problemset.

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Looking forward to a rated round

→ Reply
»
23 months ago, # |
  Vote: I like it -18 Vote: I do not like it

I am improving day by day, I might end up top1 in this contest.

→ Reply
»
23 months ago, # |
  Vote: I like it +2 Vote: I do not like it

How did can i give two contest on 1 feb there is codechef contest also at the time of codeforces div2

→ Reply
»
23 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Really excited for my first Bangladeshi round.

Congratulations adnan_toky and Shefin_ bhai.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited to participate in Bangladeshi round. Hope the round will be good and rated, no unwanted issue will happen.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

no more unrated round!!!

→ Reply
»
23 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Hoping to move closer to cyan color.

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Another Codeforces and Codechef clash ...

But there is no doubt which one I will prefer :)

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow. Bangladeshi Round.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope it will be a good round.I don't want a unrated round again!

→ Reply
»
23 months ago, # |
  Vote: I like it -31 Vote: I do not like it

Today I will beat tourist....:)

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hurrah! Problem Setters from Bangladesh.

→ Reply
»
23 months ago, # |
  Vote: I like it +84 Vote: I do not like it

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Waiting...

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Strange score for problem C || nice:)

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me how can i increase my rating or problem solving skill

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

    by not asking and instead practising.

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

      Yeah bro you are right but i am not able to think the about the solution and get demotivate and quit and again try to do and again quit

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

        Demotivation is natural. Everyone gets demotivated.

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

        You need to find some problems with proper difficulty.

        → Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Please arrange prizes for top Bangladeshi Performers Shefin_ bhai.

→ Reply
»
23 months ago, # |
  Vote: I like it +13 Vote: I do not like it

When will the rating from the previous round will get updated?

→ Reply
»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I will claim my green color back

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Forgot to register and was willing to join 10 minutes late but damn this looked quite speedforces that I rethought, lmao

Spoiler
→ Reply
»
23 months ago, # |
  Vote: I like it +11 Vote: I do not like it

goofy contest

→ Reply
»
23 months ago, # |
  Vote: I like it +20 Vote: I do not like it

I think I am dyslexic, took me 30 min to read problem B lol

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why is the second problem so difficult?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    It would be easier if they could explain it better. :/

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

    You only have to do that a[i], a[i+1] operation for any one pair. I also got stuck in it and couldn't do it :(

    → Reply
»
23 months ago, # |
← Rev. 10   Vote: I like it -22 Vote: I do not like it

.

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
2nd problem be like
→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

5 2 4

2 5 4 3 1

5 2

After the contest, it will be helpful for me if anyone tell me the answer and explanation of this test case.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It's answer will be 0 as index[a0] > index[a1] ie index[5] > index[2] in the given array , index of 5 is 1 and index of 2 is 0 , so first condition in not satisfying and hence [5 2] is already good.

    → Reply
»
23 months ago, # |
  Vote: I like it +60 Vote: I do not like it

The description of problem B could not be any worst.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B>>>>>>C :( Could Have Finished In 3 Dig I Would Have Not Wasted 45 mins in B

→ Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

hardest problem B i have ever seen

→ Reply
»
23 months ago, # |
  Vote: I like it +13 Vote: I do not like it

implementing B is masochism

→ Reply
»
23 months ago, # |
  Vote: I like it +17 Vote: I do not like it

What the hell is D?...

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    10th grade math

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

    It's some DP with infinite series I think, got the transitions down but never solved it

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

    Basically solving a set of equations; we only care about how many positions are correct currently; so it's about transforming from one state to another. Each equation only has 3 or 4 terms and has a fixed pattern (except the first and the last), so can be solved in O(n).

    → Reply
»
23 months ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve D?

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

    A bunch of expected value math. Couldn't debug in time :(

    → Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    1) the only important thing is the number of positions in which the lines differ = cnt

    2) let a[cnt] be ans for cnt different positions in a string of length n

    a[0] = 0

    a[n — 1] = x

    a[n] = x + 1 (from n we can only move to n — 1 and spend 1 move on it)

    if we know (in terms of x) a[i] and a[i + 1] we can calculate a[i — 1]

    p * a[i — 1] + (1 — p) * a[i + 1] = a[i] + 1 where p is probability (i) -> (i — 1) different pos = i / n

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

      error in the last line

      ..... = a[i] — 1

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

      a nice point is that the coefficient for x will always be 1, so you can just store q from x + q

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

    During testing, my idea is to take the XOR of two strings and now convert the XOR string to $$$0$$$ and later found that the only number of non-zero numbers in the n XOR string matters assume that we have $$$K$$$ $$$1$$$'s in the XOR string so it will be increased by $$$1$$$ or decrease by $$$1$$$ after one move.

    So let's say $$$F(x)$$$ is the number of expected moves if we have x $$$1$$$'s in the XOR string so after that it's easy

    $$$F(n) = F(n-1) + 1$$$

    $$$F(x) = (x/n)*(F(x-1)) + ((n-x)/n)*(F(x+1)) + 1$$$

    $$$F(0) = 0$$$

    now just merge form left and right for $$$F(K)$$$ and it will be your ans.

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

      How do we do that. The dependency on $$$F(x+1)$$$ annoyed me when trying to compute from left to right.

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I think YocyCraft explained it well here.

        → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
        ← Rev. 3   Vote: I like it +7 Vote: I do not like it

        Assume $$$F(x + 1) = \alpha F(x) + \beta$$$

        Then $$$F(x) = \frac{x}{n} F(x - 1) + \frac{n - x}{n} F(x + 1) + 1 = \frac{x}{n} F(x - 1) + \frac{n - x}{n}(\alpha F(x) + \beta) + 1$$$

        Therefore, $$$\left(1 - \frac{\alpha (n - x)}{n}\right)F(x) = \frac{x}{n} F(x - 1) + \frac{\beta (n - x)}{n} + 1$$$

        Divide both sides by $$$\left(1 - \frac{\alpha (n - x)}{n}\right)$$$ to get the expression in the form $$$F(x) = \alpha' F(x - 1) + \beta'$$$, as desired.

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

      Why cannot we just solve the equation for $$$F(x+1)$$$ and then replace $$$x+1$$$ by $$$y$$$?

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

        I guess Andalus explained your answer.

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

          I meant from the second equation you wrote, direct

          → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        You can, but you will need two base values $$$F(0)$$$ and $$$F(1)$$$. Turns out finding $$$F(1)$$$ is as hard as the general problem.

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

    let $$$dp[i]$$$ define the expected number of moves required to move from state where there are $$$"i"$$$ correct indexes where $$$number$$$ $$$of$$$ $$$(a[j] === b[j])$$$ . therefore $$$dp[0]=1$$$ as any move makes an incorrect index to a correct index , now apply probability to calculate $$$dp[i]$$$ using $$$dp[i-1]$$$ . Its a infinite sum which quite common for calculating expected value . now that you have calculated $$$dp[i]$$$ for all values , find the given state, that is number of correct indexes for string $$$"a"$$$ and $$$"b"$$$ and simply add all the values from $$$dp[i]$$$ (current state) to $$$dp[n-1]$$$ .

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Nice round overall! If I don't FST on problem C (I have doubts about my time complexity) this will be my teal round!

A: If the numbers are all 1, then ans = n-4, if there are two consecutive -1's, ans = sum+2, else ans = sum

B: It was a nightmare to read for me personally but once I drew it on paper the idea became clear. We just need to store the positions of the numbers and let ans be the minimum between the distance between a and a_i+1 and the number of swaps to get a_i+1 out of range for all i.

C: I forgot how to bitmask so I wrote some really weird code converting my bitmasks to strings so I could access them by index. Hope I don't FST!

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

    For A, if the numbers are all 1, then the answer should be n-2 right, since we're only changing the signs of two numbers, so -1-1= -2

    correct me if i'm wrong (i got WA anyways so...) :)

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

    u use bitmasks to sort out all possible variants?

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

      I used bitmasks to choose all sets of letters of size k to set to 'wildcards' so that they count for any letter when counting matches between string a and b, then iterated through the two strings for each set

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

        so u looked through all possible variants? sorry, i just don't understand everything u said, my english is quite bad

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

          If: k = 2 a = abcde b = degaf

          I try 'ab', 'ac', 'ad', 'ae', 'bc', bd', 'be', 'cd', 'ce', 'de' as letters I can change to anything I want. Then I choose the maximum answer after trying each pair of letters.

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

            ok, thanks, i did the same solution, but with recursive enumeration. I just wanted to make sure that my logic is right.

            → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Next time i will not participate this author contest.. One of worst problem statement. they can't explain any single problem easily. shame on you

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It is wrong to generalize for all the setters in Bangladesh, but I agree that the statement in question is more complex than necessary. Next time, I hope the setters in Bangladesh will pursue more simplicity in the problem and create a better quality contest :)

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      exactly i was telling this. by mistake i am saying all bd it was my mistake not all bd but this author.. honestly statement was freaky

      → Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

am i gonna get a negative rating, cuz my dumbass could not even solve problem A :skull: :sob:

→ Reply
»
23 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Today I learned

p = 10**9 + 7
for x in range(1, 10**6):
    pow(x, p-2, p)

Used: 1559 ms, 2732 KB

p = 10**9 + 7
for x in range(1, 10**6):
    pow(x, -1, p)

Used: 420 ms, 2112 KB

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Python's pow(k,-1,p) uses the Extended Euclidean algorithm, that's why

    → Reply
»
23 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Is there anybody who wasted much time to write total bruteforce for C?

→ Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Disgusting problems, especially D

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is "UNEXPECTED VERDICT" in the case of hacking ???

I was trying to hack the solution, which seems like will TLE in worst case input...

https://mirror.codeforces.com/contest/1778/submission/191593774

Can someone analyse the complexity in worst case ???

1000 * 100 * 10^3 * 100 is my worst case scenario...

10^10 seems quite unreachable in 2 seconds,,, is it reachable ???

→ Reply
»
23 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I missed some important observations in B because of this explaining, i'm sorry but this explaining is so bad.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D, i got the recurrence relation, but seemed like there is only one initial value but 2 are needed.

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I tried computing it from top to bottom and bottom to top and setting them equal.

    Edit: It got accepted

    → Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Solve for small N and guess the value of f(1). It turns out that f(1) = 2^N — 1.

    This gives two base cases and we can solve the equation for f(k) with the value of f(k-1) and f(k-2)

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

      Wow that's exactly what I was looking for, thanks. How exactly did you "guess" the value though? Run a lot of brute-forces and check the average?

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

        We have N equations and N variables. I solved them for N = 2 and N = 3. For N = 2 we get f(1) = 3, and for N = 3 we get f(1) = 7

        This was enough for me to guess that the value was 2^N-1

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

    It's just like: you have n equations and n unknown values, and you have to solve the equations to get the answers.

    Obviously you are able to solve all the equations because the number of equations is the same as the number of unknown values

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      @Dragonado, broooooooooooooo, i could have solved D for the first time :(

      @LMydd0225, yes, now when i think of it, it would have been a tridiagonal matrix equation :/

      → Reply
»
23 months ago, # |
  Vote: I like it +37 Vote: I do not like it

The most unclear statements of the Year. This contest is the Winner

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B gave me shivers

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    We only care about the distance between a_i and a_i+1. So we store all the indices of numbers in a map. The answer is the minimum of the distance between a_i and a_i+1 and the number of swaps to get them out of range of each other.

    void solve(){
    int n, m, d;
    cin >> n >> m >> d;
    vector<int> v(n, 0);
    vector<int> a(n, 0);
    for(int i = 0; i < n; i++) cin >> v[i];
    for(int i = 0; i < m; i++) cin >> a[i];
    map<int, int> ind;
    for(int i = 0; i < n; i++) ind[v[i]] = i;
    int ans = INT_MAX;
    for(int i = 0; i < m-1; i++){
        int x = ind[a[i]];
        int y = ind[a[i+1]];
        ans = min(ans, y-x);
        if(d < n-1) ans = min(ans, d-(y-x)+1);
    }
    cout << max(ans, 0) << endl;
}
    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is the idea/ purpose of doing this

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

        Our goal is to unsatisfy pos(a_i) < pos(a_i+1) <= pos(a_i)+d for some a_i and a_i+1. To unsatisfy pos(a_i) < pos(a_i+1), we have to bring a_i in front of a_i+1. This costs the distance between the two elements, so min(ans, y-x) covers this. To unsatisfy pos(a_i+1) <= pos(a_i)+d, we need to get pos(a_i+1) at least d+1 distance away from a_i. min(ans, d-(y-x)+1) covers this case.

        → Reply
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      sorry if I sound dumb. But won't swapping for each pair ai and ai+1 independently affect previous 'fixed' pairs. The pairs don't seem to be independent.Edit: Ok I misread the question:<

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

        We don't actually swap anything, we just calculate how many swaps it would have taken to unsatisfy the condition

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

        I misread question B as well... I thought every a[i] have to be before or at least k + 1 positions after a[i-1]. But instead we just need to find the minimum cost to swap one i out of range.

        → Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You just need to make ONE index 'i' such that it does not satisfy the condition:

    pos(ai) < pos(ai+1) ≤ pos(ai)+d.

    Just casework over how it can be done.

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

    Maybe are you asking "How not to solve B?"

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

      Now I understood that I misunderstood, lol. They should have bolded 'for all' :)

      → Reply
»
23 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Understanding problem B took more time than implementing it lmao

→ Reply
»
23 months ago, # |
← Rev. 10   Vote: I like it +30 Vote: I do not like it

A: The answer is sum(a[i])-2*min(a[j]+a[j+1]), where 1<=i<=n, 1<=j<=n-1.

B: Consider for each pair of a[i], a[i+1]. Let pos0=pos[a[i]], pos1=pos[a[i+1]]. if pos1 < pos0 or pos1 > pos0+d for any i, the answer is zero. Otherwise, for each pair of (pos0, pos1), we have 2 ways break the condition: move a[i+1] left to pos1, the number of move is pos1-pos0; move a[i] to the left and move a[i+1] to the right until their distance is greater the d, the number of move is d+1-(pos1-pos0). Be careful that the second way is invalid if d>=n-1.

C: For each different chars in string a, assign a number (from 0 to 9) for it. Then consider all masks from 0 to 1024 with bitcount(mask)==k, run dp for it (for each 0<=i<n, consider i is valid position if a[i]==b[i] or mask&(1<<t)>0, where t is the number we assigned for a[i]). The maximum number of masks we need to consider is C(10,5)=10!/(5!*5!)=252.

D: The recurrence formula is E(i)=1+(i/n)*E(i-1)+((n-i)/n)*E(i+1), where E(i) is the expected number of moves if the number of j which satisfies a[j]==b[j] is i. We can subtract E(0) from both sides of this formula, therefore (E(i)-E(0))=1+(i/n)*(E(i-1)-E(0))+((n-i)/n)*(E(i+1)-E(0)), we let dp[i]=E(0)-E(i), then dp[0]=0, dp[1]=1, dp[i+1]=(n*dp[i]+n-i*dp[i-1])/(n-i). Then let i=n-1 in the initial formula, and notice that E(n)=0, we get E(0)=n*dp[n-1]+n-(n-1)*dp[n-2]. Therefore we are done.

  • Condider we need to calculate E(i). Because there are i good bits and n-i bad bits, we have chance of (n-i)/n to increase i by 1, i/n to decrease i by 1. Then E(i)= p(i'=i+1)*E(i | i'=i+1)+p(i'=i-1)*E(i | i'=i-1) =((n-i)/n)*(1+E(i+1))+(i/n)*(1+E(i-1))=1+(i/n)*E(i-1)+((n-i)/n)*E(i+1).

(PS: In fact, if we let E(n)=0 and write the formula as E(i)-(i/n)*E(i-1)-((n-i)/n)*E(i+1)=1 (0<=i<n), we can get a tridiagonal equation system, where the coefficient matrix is a tridiagonal matrix. )

E: No idea.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Waiting for your arrival in comment section.

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If you want to solve $$$E$$$ without looking at the editorial I will give you hint that think about XORbasis.

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

    Hmmm, I brute forced C, and it passed pretests.

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

    Isn't E(i)=1+((n-i+1)/n)*E(i-1)+((i+1)/n)*E(i+1) ?

    → Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The time complexity of C is not O(n*pow(2, min(u, k))) because we just need to check all subsets of length min(k, u) as the subsets of length < min(k, u) are a part of subsets of length min(k, u) and being able to change more letters is never going to bad

    Hope this helps someone :)

    → Reply
»
23 months ago, # |
  Vote: I like it +16 Vote: I do not like it

what's D doing in a programming contest?

→ Reply
»
23 months ago, # |
  Vote: I like it +30 Vote: I do not like it

I hate problem B :((( The statement is unclear :(((

→ Reply
»
23 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Any comments about this being posted in contest time?

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

    Is this a common approach? It seems really unintuitive and should be obvious if someone pasted it.

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

    Omg :(

    There are 850 views...

    → Reply
»
23 months ago, # |
  Vote: I like it -6 Vote: I do not like it 
Is is div2B or div1B ? I don't think I even came close to solution. I just pushed everything to left by fixing first postion and everything to right by fixing right postion and that did not work

may be each pair has 2 options i and i+1 cross each other and [i+1.n] maintian k distance and [0..i-1] maintain k distance gap and moving left.

Nice problem set
→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I spent the entire contest solving this interpretation of the problem.

    The actual problem is entirely different though.

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

    Hi I think you misunderstood the Problem. You need to unfulfill the condition they gave you

    → Reply
»
23 months ago, # |
  Vote: I like it +10 Vote: I do not like it

not a good contest.

→ Reply
»
23 months ago, # |
  Vote: I like it +33 Vote: I do not like it

there are 1k cheater https://www.youtube.com/watch?v=6ACSJUjhvCw

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How come the answer for this last test case of problem C is 11 ?

10 3
lkwhbahuqa
qoiujoncjb

I think that answer should be 10, after changing A to lkwujonuqa. What is the correct update of A then ?

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

    Even I wasted all time on this. But we can change last 'a' to 'b' because changing 'a' doesn't increase set size

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking at other's solution after contest gave me more clarity about problem B than the problem statement itself.

→ Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Welp time to learn Expected Value.

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I think the problem setters skipped English lectures to study maths...

Problem B :( u all know why

and problem D was more of maths than programming.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    I think the problem was very clear and the examples were also exhaustive so one could observe all ways

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I admit , the testcase were good too but me and i guess majority of us took too long to understand what's the question is saying.

      → Reply
»
23 months ago, # |
  Vote: I like it +15 Vote: I do not like it

I think B statement was clear enough (though don't like the problem much). Samples explained further as well which I noticed ages later. Just shows I can't even read.

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

    [Not a participant] They added more samples later, saw it in announcements.

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

    Fun fact: those who complained the problem statements over and over again were almost some who participated poorly in the contest, and most of them specialist or below.

    → Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Literally, curious to know how to solve D! The states seems to depend on each other so a straightforward dp with recursion will fall into infinite recursion...

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    Let $$$dp[i]$$$ be the expected number of moves to make both strings equal if we have $$$i$$$ matching characters, so:

    1. $$$dp[N]=0$$$
    2. $$$dp[0]=1+dp[1]$$$
    3. $$$dp[i]=1+\dfrac{i}{N}\cdot dp[i-1]+\dfrac{N-i}{N}\cdot dp[i+1]$$$

    From the $$$2^{nd}$$$ point we can observe that the $$$dp[i-1]$$$ part in the RHS of $$$dp[i]$$$ can be replaced with an expression in terms of $$$dp[i]$$$, to do that, let's assume $$$dp[i-1]=cof[i-1]+dp[i]$$$. Now just replace $$$dp[i-1]$$$ in the RHS of $$$dp[i]$$$ with $$$(cof[i-1]+dp[i])$$$ and simplify, we will find that:

    $$$cof[i]=\dfrac{N+i\cdot cof[i-1]}{N-i}$$$. So we can calculate $$$cof$$$ in increasing order of $$$i$$$ then calculate $$$dp$$$ in decreasing order of $$$i$$$. So, if we have $$$M$$$ matching characters in the initial strings, the answer is $$$dp[M]$$$.

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

      I am sorry but what is cof[i] ?

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        By analogy with the "$$$dp[i-1]=cof[i-1]+dp[i]$$$", $$$cof[i]$$$ can be found in $$$dp[i]=cof[i]+dp[i+1]$$$.

        Note that we were able to shape the equation of $$$dp[i]$$$ like that because from the original equation $$$dp[i]=1+\dfrac{i}{N}\cdot dp[i-1]+\dfrac{N-i}{N}\cdot dp[i+1]$$$, when we replace $$$dp[i-1]$$$ in the RHS with $$$cof[i-1]+dp[i]$$$ and rearrange we get:

        $$$\dfrac{N-i}{N}\cdot dp[i]=1+\dfrac{i}{N}\cdot cof[i-1]+\dfrac{N-i}{N}\cdot dp[i+1]$$$

        So dividing the whole equation by $$$\dfrac{N-i}{N}$$$ yields $$$dp[i]=\dfrac{N+i\cdot cof[i-1]}{N-i}+dp[i+1]$$$. So we just renamed the RHS to $$$cof[i]+dp[i+1]$$$.

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

          Thank you so much! I agree with TheBhediyaOfDalalStreet; it will be very helpful if you tell us the motivation for this solution or how you thought about it.

          → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      let's assume dp[i−1]=cof[i−1]+dp[i]

      Is there a name for this technique?

      Kind of reminds me of guessing the solution of a differential equation by intuition then figuring out the constants

      → Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

One question I had for a long time , when system testing occurs does it check the submissions in the order it was submitted in the contest ?

→ Reply
»
23 months ago, # |
  Vote: I like it +7 Vote: I do not like it

https://www.luogu.com.cn/problem/P3750 the same as D

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

    No, P3750 is harder than this D because P3750 needs some observation and proof and this D requires nothing but memory.

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

    Hhh, time to learn chinese...

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      I'm Chinese. This problem is completely different from D.

      → Reply
»
23 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Saw expectation problem in the position of D and got afraid... Spent nearly one hour trying to understand how to implement expectation dp, finally understood, and got AC.

→ Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Atleast , you should have learnt English first before writing problem statement for B.

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

    If only problem statement for B would have been a little more clearer.

    → Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Interesting problems. well done shefin vai and adnan toky

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

what is the meaning of this line you have to maximize the number of integer pairs (l,r) (1≤l≤r≤n) such that a[l,r]=b[l,r] and why was the string a can be of almost 10 different character is there any data structure we can use or something

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

    All you need to know to solve the problem is $$$\binom n 2$$$.

    → Reply
»
23 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Any hints for D please?

And any resource for some probability and expectations?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Solution idea for D here.

    Resource is here.

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Suppose there are $$$d$$$ mismatching bits. Let $$$F(d)$$$ be the expected number of operations that we need until the two strings match. Can you derive a recurrence relation for $$$F(d)$$$?

    If you're familiar with the basic definition of expected value, i.e. multiply each possible value by its probability of occurring and then add up all the products, then this is sufficient for this problem. No advanced properties are required here.

    → Reply
»
23 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Why this problem B is soooo hard? I mean, this is harder than other Bs of Div2 contests

→ Reply
  • »
    »
    23 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I don't think the problem itself is difficult.

    1. It's hard to understand the description.
    2. The statement of the conditions is complicated.

    For these two reasons, I think it took a long time to find the right way to solve the problem.

    → Reply
»
23 months ago, # |
  Vote: I like it +22 Vote: I do not like it

lmao at 8 pages of cheaters getting WA on test 24 for problem D

https://mirror.codeforces.com/contest/1778/status/page/1?order=BY_JUDGED_DESC

→ Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

B was not very readable.

→ Reply
»
23 months ago, # |
  Vote: I like it +16 Vote: I do not like it

In problem D, if expected value is $$$\frac{p}{q}$$$, how to prove that $$$q$$$ has mod-inverse for $$$998244353$$$?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Modular inverse of x exists iff gcd(x, mod) = 1. Here, mod is prime, so the inverse exists always.

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      gcd(mod, mod*2) is not 1. :) So, if q=0 (mod 998244353), then it would not exist. I think there are other proofs,

      → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
        ← Rev. 6   Vote: I like it +11 Vote: I do not like it

        Well, as long as $$$q$$$ never becomes a multiple of $$$MOD$$$, then it will have a modular inverse. Every quotient we utilize for solving this problem is built from multiplying and dividing various coefficients of the recurrence relation for various arguments. For example, with $$$T(i)$$$, the recurrence relation uses $$$\frac{i}{n}$$$ and $$$\frac{n - i}{n}$$$. These base values are always from $$$1$$$ to $$$n$$$, where $$$n \leq 10^6 < MOD$$$, so it is impossible to generate a multiple of $$$MOD$$$ by multiplying/dividing such values in any combination.

        → Reply
      • »
        »
        »
        »
        23 months ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        If you solved D, you may know that the denominator of every fraction in the calculation process does not exceed n. So the final denominator of the expected value must be the multiplication of numbers below n, which does not have mod as a factor.

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

        Zero always has no inverse as an exception.

        → Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve expectancy related.problems?

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved ABCDE in div.2 for the first time. Thanks for the contest!

But I think problem E is not so good, because the problem like "choose some node $$$r$$$ to be the root of the tree and then choose a node $$$v$$$ and ask some questions about the subtree of $$$v$$$" is popular in China. We have an easy solution by using heavy path decomposition (and similar, I don't know how to descirbe it). What's more, I spent 50 minutes on ABCD but 40 minutes on E. It's hard to code and debug.

→ Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

[problem:B] there are too many distracting details and it made me miss the important details

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the idea in problem E?

→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Problem B test different ability.Two interconnected statement made it hard to cut to the chase.

→ Reply
»
23 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Didn't like the problem statement for the second question, was to confused. Thought we need to do the operations such that all of them make it "not good". Was stuck on solving this for whole 1.5 hour.

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

    Exactly,I guess that's the reason such an easy problem has less number of AC today! And because of B I lost time(couldn't give any time to D :()

    → Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I found C to be easier than B as it didn't require any intuition and was just a simple implementation problem, I've explained it here in this video, https://youtu.be/OH3jNLrdFag. happy coding :)

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

The winner of this contest is the for all line in problem B.

Saw this after the end of contest. Blind me :-((

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B statement:

For example, with the permutation p=[4,2,1,3,6,5] and d=2 :

a=[2,3,6] is a not good array. a=[2,6,5] is good because pos(a1)=2 , pos(a2)=5 , so the condition pos(a2)≤pos(a1)+d is not satisfied. a=[1,6,3] is good because pos(a2)=5 , pos(a3)=4 , so the condition pos(a2)<pos(a3) is not satisfied.

How is pos(a3)=4 for the last array a?

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the solution:191560464 giving WA?

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

    In the for loop after bool alt you have declared for loop from 0 to n and checked for i-1 so there it checks arr[-1] in first iteration

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

There are test cases with n or m equal to 1?.In the statement that input is excluded

→ Reply
»
23 months ago, # |
  Vote: I like it +4 Vote: I do not like it

when the rate will be changed ?

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If problem B statement be written in clear way it will have more than 10k submission Anyway will be cautious from next conests. For anyone whose is having problem implementing code for b here it is 191620224

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Same here. I thought we had to make every position good. I was thinking for some stupid algo. But question was asking something else. I sure most of us has thought of making every position good innit?

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I just understood question B with the help of youtube editorial and after solving it I got to know it cannot be even 900 rated

      During the contest I was trying with dp.

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

    probably that question is one of those readForces questions lol

    → Reply
»
23 months ago, # |
  Vote: I like it -10 Vote: I do not like it
Pic
→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There was no need for subtitles. The pic itself spoked it for me. Haha

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

There should have been at least one test case for problem B which could explain that we have to think only for adjacent pairs and not for whole array.

→ Reply
»
23 months ago, # |
  Vote: I like it -8 Vote: I do not like it

During contest there are live YouTube streams running. Pls do something!

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The language of B made it one of the toughest questions to understand, language should have been improved. If someone understands properly it was very simple but I and most of my colleagues thought in wrong direction resulting in a decrease in the ranks.

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

    Yea once you understand what B is asking, it's kind of easy. Although I wasted some time thinking I had to make all adjacent pairs good.

    → Reply
»
23 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Why are ratings not updated till now?

→ Reply
»
23 months ago, # |
  Vote: I like it +2 Vote: I do not like it

D is a very nice problem in my opinion, thanks!

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

    ORZ. I really didn't like it tho. Felt like too much of a bash. My code is ugly :(

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

i just realised that in problem B, for an array to be good u just need one of the indexes to not meet the requirement. I thought you have to make it false for all indexes.

→ Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Could someone please explain how the answer is 56/3 in third testcase of D

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there any prerequisite topics we need to learn before attempting Problem D?

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

    Knowing how expected values work.

    → Reply
»
23 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Any idea when ratings will be updated?

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There is an issue with problem "C". Verdict is showing Accepted but the same code is getting TLE now!!!

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Your code might be passing for the pretest where only few test case will be judged. But later all remaining test case will be judge against your solution during system test. That time your solution might be giving TLE for some test case.

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

    Because your solution failed for hacked testcases which were added after the contest was over. Don't worry your solution will be judged only on the test cases intially present.

    → Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I have submitted someone's AC code in Problem C after the contest ends. But got TLE. My submission link : https://mirror.codeforces.com/contest/1778/submission/191670480 AC submission in contest time : https://mirror.codeforces.com/contest/1778/submission/191601266

→ Reply
»
23 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Is it rated?

→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

isn't taking too late to update rating ?

→ Reply
»
23 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Why hasn't the rating been updated yet

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

As a newbie, when to add rating？

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

WHEN rating changes? my purple flying away...

→ Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Benq stay at the first place for a longer time due to the rating hasnt update.

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

    they are in div1 , their rating will not change

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

      Sorry，I mean the contest last time.Even the last contest hasnt update rating.

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

        oh ok sorry, I will also keep an eye on benQ on the leaderboard.

        → Reply
»
23 months ago, # |
  Vote: I like it +2 Vote: I do not like it

When will the ratings change?

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think they are waiting for the rating change of the previous div1+div2 contest.

    → Reply
»
23 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Ratings not updated yet :-/

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I was hoping for a rating increase, but no update in rating :o

→ Reply
»
23 months ago, # |
  Vote: I like it +2 Vote: I do not like it

LateRatingForces

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Please, update ratings!!! :( :( :(

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

why rating hasn't updated yet??

→ Reply
»
23 months ago, # |
  Vote: I like it +16 Vote: I do not like it

When will the ratings get updated?

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why ratings not updated yet?

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

    Coz ratings of the previous round(TypeDB Forces 2023) is not updated yet :3

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Sed ... Waitin on pupil for the first time

      → Reply
»
23 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Why it's still unrated?

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

When rating will be updated of this Contest?

→ Reply
»
23 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I think you can swap the position of D and E , D is very crazy .

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it rated?

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

why didn't the rating is updated yet.Is there any problem or cheaters are being caught?

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Shefin_ what exactly is the problem in backend.It is getting so late rating changes.I hope contest will be rated.

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

    We also know the same as what prateek_saxena said. We have not received any negative response from CF about our round. So, the round is rated. You just need to wait for the plagiarism test of both rounds and the previous round's rating changes. Don't worry.

    → Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is it rated ? rating is not added yet ?

I am new in to CF

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is the contest unrated? My rating has not been updated yet...

I would be glad to know.

→ Reply
»
23 months ago, # |
  Vote: I like it +1 Vote: I do not like it

When will the ratings get updated? O.o

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will we be rated?

→ Reply
»
23 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The rating changes for round847(div3) have disappeared too.What happened?So strange.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    me too，and my contest record for last div3 disappeared

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

yayy ratings updated, got positive delta

→ Reply