SlavicG's blog

By SlavicG, history, 3 years ago, In English

Hello Codeforces!

magnus.hegdahl and I are glad to invite you to Codeforces Round 767 (Div. 1) and Codeforces Round 767 (Div. 2) which will be held on Jan/22/2022 17:35 (Moscow time)! This round is rated for both divisions.

In each division there will be 6 problems and 2 hours to solve them.

We would like to thank the following amazing people:

Score distribution:

Div. 2: $$$500$$$ — $$$750$$$ — $$$1250$$$ — $$$1500$$$ — $$$2000$$$ — ($$$1500$$$ — $$$1000$$$).

Div. 1: $$$500$$$ — $$$750$$$ — $$$1250$$$ — ($$$1000$$$ — $$$750$$$) — $$$2250$$$ — $$$3000$$$.

UPD1: ak2006 and namanbansal013 have prepared video editorials for most div. 2 problems that will be available on ak2006's channel and namanbansal013's stream

UPD2: Editorial is out!

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

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

As a tester, I am asking for your precious upvote.

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

As a tester, pls help I can't figure out a decent as a tester comment

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

As a tester, I think problems are great. I highly encourage you to participate in this contest and check out all the problems.

Tip: Having a cool profile picture like mine might help you do better :)

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

    Tip: Having a cool profile picture like mine might help you do better :)

    So that means I will AK that round?

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

As the person who has seen the tester irl for 1 time I can say that he is very great dude (vanilla confirmed)

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

As a participant, thanks for putting the contest on a weekend!

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

As a Mihai supporter I wish all the Mihai supporters to get +300

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

upvote announcement blog or negative delta

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

Time to upsolve: https://codeforces.me/contest/1537

I actually did terrible that contest on vc and wish for more luck this weekend :prayge:

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

This is a very well prepared round!!!

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

As a tester, I would like to express my appreciation for the setters and coordinators for their efforts to make this round as enjoyable as it can be, and to invite everybody to participate in this contest!

P. S. also my salary is contribution plz upvote

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

    I really liked the idea of problem D. What a clean observation!!

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

as a tester, i'm late for commenting

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

as a tester, I think the problems are great. Recommend participation.

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

As a tester, the problems are interesting and you will enjoy thinking about them and solving them.

As the video editorialist for most div 2 and some div 1 problems I have tried to make the solutions intuitive and simple to understand so do subscribe to my channel

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

Yet another Mathforces contest O_o

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

Good luck! I wish every grey become green!

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

    I am ready to sacrifice my Delta for your positive.

    We both become green after this.

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

Looking forward to this round!

Wish everyone good luck&positive delta

Btw, that's a great score distribution

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

Good score distribution! Wish everyone good luck and positive delta)

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

As in this contest, having official video editorials for every contest will be a great idea. This will motivate the content creators in terms of money and views and will be good for the whole CP community as well!!!

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

As a tester, I had found that one of the problems could be solved by Googling. But now it's substituted with another great task, mission accomplished! Also, the round is really entertaining, please participate, remember to read all the problems and stay healthy <3

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

UpvotesForces

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

Wow that's quite a list of testers! Is it documented somewhere how to volunteer for testing a round?

I'll earnestly try to participate in yours, but, like most rounds, it's 6:35am in my timezone :|

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

    In Romania, we call the process to volunteer for testing as "sa ai pile".

    In all seriousness, the problemsetter is the one that asks you first to test their round. Then, it is up to the candidate tester whether they accept or not

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

      Ah, I thought tester responsibilities were something more formal curated by Codeforces coordinators. Gotcha, thanks for clarifying!

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

glhf

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

Can't wait to see a new, well-prepared, interesting and fun cf round! GO-GO-GO SlavicG!

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

As a tester, I believe all of you will enjoy these excellent probelms.

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

    As a fellow tester, I completely agree. Good luck, have fun!

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

    I hope this.

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

mihai

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

Score distribution announced early.

Thanks

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

74TrAkToR is coordinator, so we should expect combinatoric problem which is in wrong order.

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

My gut feeling is saying that the problems in this contest gonna be very interesting, gonna get +ve delta

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

WA is certain but it doesn't have to be ugly

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

A palindrome round (767). Nice :)

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

Magnus from Norway. Sounds familiar to me...

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

Can we see Mihai in problemset?

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

    Of course, I'm sure Mihai is shadow ruler of contest

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

First Norwegian round. (I think...) Let's go!!!

magnus.hegdahl orz

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

I wish you all to get repeated TLE's and passed pretest but gets failed in system testing may your code gets skipped and you get a minimum of -100. all the worst :) . may you get down by h whole level.

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

I am a new programming learner. I have just finished the basics of C programming. Can/Should I participate in this contest?

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

I hope the server won't break down again(

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

Wish all participants enjoy tasks and get higher ratings! ^-^

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

Hope this contest completes smoothly

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

Cheaters better not cheat. Else I'll whoop your ass

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

Good Luck peeps!!

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

abacaba

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

Why can't I submit my code?

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

in div2 F1 what does "score of the optimal game" mean? average of all the possible scores? SlavicG

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

    Use clarifications section for clarifications during contest

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

I think that shuffling problems in div.1 is not a great idea.

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

Speedforces

Meme

How to solve div2E.
And is div2F1 some standard problem as some div1 participants solved that instead of div2E.

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

    Not only they
    I just looked at div1 stat and decided to solve F1 instead of E and it worked out

    Pretty simple dp

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

    2E ended up being a logic puzzle instead of a coding problem. Once you solve the logic puzzle, the implementation becomes O(n^2).

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

Ad-hoc-forces!

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

Problem A to D are too easy, especially Div1 D is much easier than usual .

And I have a O(nlog^2n) solution to E , but it got TLE . So Sad ...

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

    And problem B seems to be hard to implement . I don't like this round :(

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

Seems that Div.1 E has a way too strict TL? My $$$O(n\log^2 n)$$$ solution keeps going TLE. Or maybe the expected solution is $$$O(n\log n)$$$ then just ignore me.

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

    Yeah, O(n log n) is intended.

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

      Well, I have come up with an $$$O(n\log n)$$$ solution (requiring $$$O(1)$$$ LCA), and it seems a bit harsh to code. I guess it would be better to set both $$$O(n\log^2 n)$$$ and $$$O(n\log n)$$$ solutions as acceptable. Anyway great contest!

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

        +1

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

          My $$$O(n\log^2)$$$ solution didn't pass but after changing it to $$$O(1)$$$ LCA it passed.

          But I heard that it is not needed, since we only need to find the vertex with the smallest $$$dfn$$$ and the one with the largest $$$dfn$$$.

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

            An interesting thing is that I first read the statement wrongly . I mistakenly think we should work out the max of sum. I found it in the last 10 minutes when checking the example . So I changed some parts quickly, and have no time to make it faster.

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

              In fact, me the same, I even finished my 3k code and then found myself not passing the sample.

              But I used Kruskal and the problem become asking sum again!

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

        O(1) LCA. Never heard of that. At least now I know something like this exists. Thanks for your comment.

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

How To solve C and D of Div2 ???

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

    D was DP i guess and I solved C as I build reverseMEx array(mex till i from n) and then brute-forced from being (might get TLE in sys testing)!

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

      If any of the strings in the list is a palindrome, the answer is yes! If there is either zyx | zy for any string xyz, then the answer is yes! The trick is to check for zy because we are only storing strings in hashmap. To do this, we find for every ch in small alphabets if reverse(zy(ch)) belongs to hashmap then the answer is yes! Otherwise, the answer is no.

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

    C: The basic idea here is to keep taking elements until the mex for the current set of taken elements cannot be increased by any element present in the remaining elements.

    Now to increase the mex of the current set of elements, mex itself is required to increase itself. So, I kept all the elements in a multiset and then checked if the mex of the current set of elements is present in the remaining elements or not. If it's not present then we can start a new set of elements from here. Else, just take the current element and then increase the mex till it can be increased.

    Now to increase the mex, I have created a hash table and put the current elements in there. Now, until the next element is not present in the hash table, keep increasing the mex. This is the basic idea. Code

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

    D was mostly observation.

    Trivial Case: If the input strings are palindrome, then return True.

    Observations:

    Now the palindromes that can be created will be of length at least 4. If you break a palindrome of a given length only in segments having 2 and 3 only. Then the first and last segment will also be of length 2 or 3. I can construct a palindrome out of the first and last segment only. So I can have the following combinations of lengths:

    • 3 3
    • 2 2
    • 2 3
    • 3 2

    Now all that's left to do is check if we can create a palindrome considering the current string as the last part.

    For this purpose, I can have previous strings in a set and then reverse the current string and check if it is present in the set or not. This part is easier said than done. Have a look at my implementation to understand it better. Code

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

I regret ever making fun of line trees, I didn't pass E because I had no template for them QAQ

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

Only If I got 30 more seconds I would have submitted D,!!

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

Great contest

but feel sad for sitting there trying to solve 2E for 70min but stuck at the last step

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

Is there a formula for 1628D2 - Game on Sum (Hard Version)?

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

    $$$O(m)$$$ formula (can maybe reduce to $$$O(1)$$$)) after preprocessing:

    $$$\displaystyle k * \sum_{a = 0}^{a = m} \frac{\binom{n - a - 1}{n - m - 1}}{2^{n - a}}$$$

    if $$$m < n$$$. If $$$m = n$$$ then the answer is simply $$$k * n$$$.

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

FML

I found an $$$O(n)$$$ formula for D2 instantly, but I kept treating $$$n, m, k$$$ as queries and completely forgot that $$$O(n)$$$ would just solve the problem...

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

    Please share the formula.

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

      For $$$m > 0$$$,

      $$$ \displaystyle \frac{k}{2^{n-1}}\binom{n}{m-1} + k\sum_{i=1}^{m-1} \frac{i+3}{2^{n-i+1}} \binom{n-i}{m-1-i}$$$

      Turns out this on OEIS as A193605 if you remove $$$k$$$ and multiply by $$$2^{n-1}$$$.

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

      Here's some intuition for how to find the formula.

      Take your DP solution for D1 and formulate it as a path on grid problem: you start at $$$(0, 0)$$$, you want to reach $$$(n, m)$$$, you have a $$$\frac{1}{2}$$$ probability of moving to $$$(i + 1, j)$$$ or $$$(i + 1, j + 1)$$$ from $$$(i, j)$$$, and if you reach a cell such that $$$n - i = m - j$$$, you can only transition to $$$(i + 1, j + 1)$$$ and add $$$k$$$ points to your score. Answer is expected score over all valid paths. Now you can count grid paths with binomial coefficients and powers of $$$\frac{1}{2}$$$.

      (The exact indexing might look different depending on your DP.)

      Submission for Reference

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

      ((SUM(i=0 to m-1) (m-i)*(n choose i))/2^(n-1))*k

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

    Same, smh

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

I declare myself the dumbest person on this planet when I realized after 40 mins that string of length 1 is always a palindrome, so you only need to handle strings of length 2 and 3.

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

    I never realized it at all, so you are definitely not the dumbest :|

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

    I realized it only after reading this comment.my code had the cases (1,x,3) for all 1<=x<=3 as well(the numbers denote the length of the string)

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

Can someone tell me what is wrong with this code for D? I broke it into cases...failed pretests Code

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

Problem div2 E is my favorite problem I've seen in recent memory. :)

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

How to solve div2 promblem E?Is it should be divided into 2 * 2 grids to solve?

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

I could think out diagonal XORsum of problem E 10 minutes before contest over. that was close

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

    Unfortunately, I only got it 5 minutes after the contest (arghhh). As an aside, F1 looked pretty nice. Too bad I didn't have enough time to solve it. You don't see DP with fractions too often.

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

A-D great stuff, thanks!

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

Sometimes there are problems having very intuitive algorithms (but to prove their correctness requires time) so I'm wondering whether there are people eagerly submitting such intuitive algorithms without formally proving them. Those submissions still can get Accepted when they are lucky.

After participating in several contests at Codeforces, I realize that perhaps I have to submit things very quickly, without carefully thinking about their correctness, otherwise I will get a low rank because of late submissions.

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

    Do you think this is good? In other words, do you think it is common and acceptable to do such quick but not reliable submissions in competitive programming?

    (I don't like unreliable things, so I feel uncomfortable when I have to do such quick submissions.)

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

    -is-this-fft- mentioned his style of solving problems in this Blog

    Piece of text, Para4 in the blog

    I feel after a certain point it becomes difficult to solve problems without proving.

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

who did place hacks format before output format in 2E? WHO DID THAT?

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

loved the contest! strong pretests and amazing problems ... :)

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

Me reading Mihai as Mithai :)

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

I forgot to check if the given strings are palindrome and failed on Div 2 D

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

Peculiar Movie Preferences Video Solution.

Don't forget to like and subscribe!!

https://www.youtube.com/watch?v=xBkDyMHVTJ0

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

Does anyone realise that after a few hours there will be the first 4000+ rated user in entire history of codeforces?

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

    Looks like Mike has to think about the new name for 4000+ rated users real quick. Tourist is almost there

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

Mihai is very abnormal person, i mean look at his movie choice.

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

My Submission Div2 C it is giving tle on test 5 can someone plzz help me out ??

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

    The link is broken. Didn't understand the idea, but if it's only tle, maybe it's because of initialising of set with 200000 values for each run.

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

      yaa exactly this was the error. I changed it to n and it is accepted now. Thanks for pointing out. Dont know how can i do this blunder.

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

Could someone please point out my mistake for div. 2 D? Here is my submission

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

As the Victor from 1628C - Grid Xor, why did you, mesanu, steal my grid????

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

    As the Mihai from all the problems, if I steal your grid, I get your IOI medal.

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

      As your RMI team leader, I challenge you to get one this year and return mine, please

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

My AC submission 143728411 for Div2 C/ Div1 A gives a runtime error on this test case:

1
2
3 4

I'm not sure why this happens. Could someone perhaps explain why this happens?

Update: Nvm, this test case isn't valid.

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

accidentally put this comment not in the editorial :/

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

Hey, Div 2 Problem B i submitted the same code but in different C++ version, in C++ 17 it got accepted but in C++ 20 it gave me wrong answer and because of this i had 3 wrongs submissions, can someone please tell me why this happened, like the code work in one version but in the other newer version it gives WA?
Code:
- C++ 17 (AC) : 143715633
- C++ 20 (WA) : 143715622
Any help is appreciated!

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

    Short Answer: Never trust floating-point arithmetics. Use integer arithmetic instead to get accurate results.

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

      Oh thank you so much i will be careful next time!