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

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

Greetings, CodeForces!

jiangtaizhe001, qzhwlzy and I rsj are more than excited to invite you to participate in TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!), which starts on Jan/29/2023 17:35 (Moscow time).

The round is open and rated for everyone. You are given 9 problems, no subtasks or interactive problems, and you have 3 hours to solve them. It is recommended to read all problems. The statements were made as briefly and clearly as we could. Enjoy the contest!

UPD: Score distribution: $$$500-1000-1750-2000-2250-2500-3250-3500-3750$$$

Sincere thanks to:

Thanks to Vaticle's sponsership, winners will receive awesome prizes!

TypeDB

Cash and Swag Prizes

  • 1st place: 500 Euros
  • 2nd place: 250 Euros
  • 3rd place: 100 Euros
  • Top 50: TypeDB hoodie, t-shirt and stickers
  • Random 50 of 51-250: TypeDB t-shirt and stickers

About Vaticle & TypeDB

Vaticle is a team of people driven to empower engineers to solve complex problems. We are the creators of the strongly-typed database, TypeDB, and its query language, TypeQL. You can find out more about our work from another announcement post, interview post, our website and GitHub pages. You can also apply directly to our team using the button below:

Apply →

UPD1: Editorial

UPD2: Congratulations to the winners:

  • Проголосовать: нравится
  • +209
  • Проголосовать: не нравится

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

omg cyan round
GL to everyone

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

As a tester, I hope that you will enjoy the round. The problem set seems much better than when I originally tested, which is a good thing.

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

Another 500 Euros to tourist.

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

omg recruitment round

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

One more NP task with 74TrAkToR ?))

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

Wow! 9 problems with 0 subtasks

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

interesting contest!

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

E code directly available in internet . Contest should be unrated. https://www.geeksforgeeks.org/equal-sum-xor/

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

As a tester, I think rsj has a really cool profile picture!

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

    As a not-participant (USACO :clown:) I thought you wrote this round before this comment and changed handle for new years.

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

Prizes ,goodies, direct interview chances :),tourist vs benq :),3 hours to solve that amazing for everyone to put extra efforts.everyone is excited imo.

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

Congratulations Tourist for winning yet another 500 euros in cf rounds.

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

E_huan orz

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

I can only solve 1-2 problems in div 2.. Can anyone give me some advice to improve myself... please

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

    Yeah Sure i will give you 7 most useful tips

    1 Practice

    2 Practice

    3 Practice

    4 Practice

    5 Practice

    6 Practice

    7 Practice

    If you follow these religiously then Boooomm you are performing well xD

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

Knock-knock!

Who?

Knapsack.

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

it will be going between tourist VS Benq

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

Ez 500 Bucks for me

Interesting clash for 2nd place awaits between tourist and Benq ;)

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

omg unrated round!!!

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

I anticipate that this will be a trash chinese round.

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

OMG China round. Hopefully I'll gain back my color.

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

Score distribution looks scary

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

I hope this is not a typical Chinese mathforces round ...

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

Eye charming score distribution for problems: A, B, C; I think it would be tough for <1200 to score "C".

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

IsaacMoris wants to participate can you delay the round 15 minutes

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

Hoping I can solve the preblom C. cheers! :D

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

My Prediction: The round will be pretty hard.

I will just look the standing. Competition between GODs _/_.

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

lmao it's completely a Mathforces Round.

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

Math contest is the most boring contest.

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

Classic chinese round making me realise how bad I'm at maths xD

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

Math forces

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

Solved A in 10 minutes but I will submit after the contest to preserve my rating... The round is very hard.

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

problem B and C are horrible imo, very annoying

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

    nah B was fine. Even C is nice once you figure out the actual observation needed. Rest is standard stuff you know what i mean (Can't tell contest is still ongoing.).

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

How can someone do problem H in 14 minutes.

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

    It's totally possible. They have must seen this concept or similar problem before and now just copy pasted some template from previous og chinese round.

    It's quite common . The other day i saw someone solved div2 E in 5 min.

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

How did they solve A in 1 minutes? At least, you need time to think, and then to code, right? Unless they have seen similar problems before...

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

LMAO Classic Mathforces

Disappointing contest

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

Watching the GODS chasing is interesting!

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

Scractched my head over C for 2 hours and still at 0.

I hope C is a 1800+ problem

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

Use this comment as dislike for problem C. What a mess...

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

Quite bad experience. After wasting 2 hours I still have no idea about problem C, even some useful observations...

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

    Same. However, I skipped C and solved D. Not too bad for me.

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

      Is there a proof of this?

      I wasted a lot of time on C and finally decided to guess this conclusion.

      upd: I can prove this now, just focus on $$$x_i,y_i$$$ and consider other unknowns as constants.

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

        I calculated $$$\frac{\partial F}{\partial x_i} = a_{i - 1} - x_{i + 1}$$$, so that it is always optimal to select the upper or lower bound.

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

        When $$$y_{i-1}$$$ and $$$x_{i+1}$$$ are fixed, we can see that if $$$y_{i-1}$$$ is smaller than $$$x_{i+1}$$$,$$$x_i$$$ should be maximum to lower the answer,vice versa.So we can determine $$$x_i$$$ and $$$y_i$$$ (one of them must be maximum)

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

Another Great Rated round! ^_^

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

Math round destroyed me. I was only able to get up to problem B and complete it with 3 mins left :(

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

tourist will not able to sleep tonight.

»
15 месяцев назад, # |
Rev. 7   Проголосовать: нравится -57 Проголосовать: не нравится
lets me guess what would problem set looks like ?
one Arabic question, one prune forces question, one brutally brute force question ?, one minimum of maximum of minimum of maximum of minimum of something , one reverse of reverse of reverse of reverse of something 
And then contest ends

Winner Board Tourist,Benq

Why even announce prize money lol ?
Directly give to them 


All GM's come and say problem set is awesome
After reading this comment people you are newbie you dont understand
My contribution -Infinity
and I don't give a damn about it
»
15 месяцев назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

Worst C problem I have ever seen

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

how to solve D?

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

    Cyclic counting (Brent's algorithm)

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

      i did exactly the same but my code isn't working.. I feel like i've done everything right in my solution But still thank you

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

It is so annoying that F asks for initial permutation rather than the minimal value :(

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

Any idea for C? It's always better to let the difference of xi and yi be greater, but I didn't come up with how to determine whether we let xi be the larger or the smaller one.

Update: Now I've come up the idea (right after the contest ends) (see comments below).

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

    dynamic programming !

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

      Is it's something like this: first let all of xi be the smaller value, and let dp[i][flag]= the minimum result we can get if we don't flip xj,yj for j>i, where flag= (whether we've fliped x_j-1,y_j-1)?

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

        Exactly. now to update dp[i][flag] it is really easy to update it from dp[i-1][flag] and dp[i-1][flag ^ 1]

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

          basically just check if the previous one is flipped or not

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

            OHHH it so easy that I've not some up with it for half an hour

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

              i feel u ! i was soooo frustrated with D that it took me a while too. I almost lost my mind on D coz of the numerous bugs my initial solution had

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

        use dp you have x+y=a[i] and (x-s)*(y-s)>=0 so if a[i]>s then it's better to choose x=s and y=a[i]-s(or vice versa). or if a[i]<s then it's better to choose x=0 and y=a[i] why ? obeservation. then you just simply apply dp.

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

    Theme: Dynamic programming

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

    Probably, it is possible to use dp, but I came to it after finishing of contest.

    Note, that there is a countertest for "prefix is max/min and suffix is min/max":

    1
    10 3
    6 7 10 4 3 2 9 5 1 8
    

    Upd. answer is 52

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

    DP will do the job.

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

    You can use DP to determine it. Let $$$dp_{i, 0}$$$ be the answer if we put $$$min$$$ first and then $$$max$$$ and $$$dp_{i, 1}$$$ be the answer if we put $$$max$$$ first and then $$$min$$$. Transitions are simple but hard to write. The answer is $$$min(dp_{i, 0}, dp_{i, 1})$$$.

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

      I've not come up with this idea and tried for some wrong approaches for half an hour... and I gave up and solved D instead

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

what is the actual sol to C? i tried to partition every number into s and the number minus s, but second test case in the example is a thing which i didn't see

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

    if ai >= s: (ai-s, s), else (0, ai), but I couldn't figure out which is x and y.

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

      yeah i forgot to mention that i already did that for ai < s, but i think i have the wrong sol, since everybody said that it's dp, but idk how to implement it ;-;

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

Horrible problemset, wacky unclear statements

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

Hint for C please!

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

    Dynamic Programming and Math

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

    It's dp after including possible choices. 0, s, a[i] — s, a[i]

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

    Is there a way to solve it using some sets and priority queues? I was unable to do so and used bst.

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

      Kind of, you can implement a simple segment tree. Check my comments below.

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

I can be reduced to this problem.

H can be reduced to this problem. This was in New Year Prime Contest, I guess 2017. There is a good solution using kinetic segment tree. You can find my article (Korean) here.

Anyway I enjoyed the ratings problems, thanks!

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

This youtube channel upload vedio on problem A & B solution at contest time.. report this channel..

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

    how did you know?????

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

      First of all I didn't participate the contest...After the end of the contest I was searching for solution of problem C..And Youtube suggest(As you know) some of the related vedios...after clicking the vedio I saw the uploading time was in the middle of the contest .. Note: You can Check

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

Unlock the submissions.

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

The implementation of F is so tough that I cannot finish F during the contest. Is there lighter way?
C and E are awesome, but D feels just heavy for me.

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

    For F, I was considering cases, and for one of the cases I had to find x such that , (2^k — 1) % x == (x-1). And then I had to minimize number of xs. Did you have this case as well ? How to minimize number of xs ?

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

A=B<E<D<C in my opinion.

C is really great.

D is boring and the solution is so obvious that it make me think that there are many problems similar to it.

E is really even easier. I guess many people can't solve it because it's an E.

I think after swapping C and E the ranklist will remain the same.

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

    E hint pls

    • »
      »
      »
      15 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится
      hint
    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Spoiler
      • »
        »
        »
        »
        15 месяцев назад, # ^ |
        Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится
        Spoiler
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think D is the easiest, while C and E are both hard for me :(

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

    Actually, C is quite easy to find the key observation if you have some Math skills, while D is easy but hard to implement.

    It seems easy to solve E, but I have some problem with the proof. Can anyone prove the strategy in E?

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

      Consider sequence of p-th bits of numbers 1...n, where p is position of most significant bit in x. It is basically something like that : 00001111000011.. For each subsequence that you create you need to take at least one number with "1" lit in p-th position. So this is upper bound for number of groups and at the same time you can achieve it — you can match together consecutive blocks of zeros and ones (so the sequence above you split to [00001111] + [000011] to obtain 4 + 2 = 6 subsequences and this is maximum (I find it a little bit hard to write more formally but you should see that works).

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

Welp, once again I'm obliterated by single observation/guessing problems (C and E) :(

Very frustrating.

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

Anyone who is annoyed by C, join me and watch Errichto solve it live :)

Errichto vs C hehe

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

Direct solutions are available on youtube and ideone. I hope to see restrictions on judging and this kind of malpractice. [C solution on Youtube]: https://www.youtube.com/watch?v=4sVV35vlBQQ I have found most of the solution ideas are from the above source.

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

    Imagine spending 2.5 hrs on a question trying your best and failing to solve it and then some "pro" person uploads the solution on youtube...

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

I think C can be solved using DP because whenever we partition ith number into smaller one then we can only take all the possibilities at i+1 number and we will take minimum of all possibilities of i+1th because we want minimum.

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

Immediate thoughts on the problems after the contest:

  • A: Pretty fair starting problem. Ended up over complicating my solution for a while until I remembered what 1 to the exponent anything is.

  • B: sieve of erathosenses being here intrigues me since it feels like this would be more common in C problems, but it's a pretty basic use here and I actually liked this problem, also since it had some implementation challenge without being too tedious.

  • C: Probably inted the whole contest because I could not spot what the idea behind the solution is here, thus I can't really judge this problem too accurately. I will say that the fact this felt more difficult than it normally would be compared to B means that the point scaling for the earlier questions (500-1000-1750-2000) feels accurate.

  • D: Graph based problem that don't explicitly state graphs in the problem. I liked this problem; felt around appropriate difficulty and its solution imo is pretty elegant. It did feel implementation heavy but this is more likely because I was running short on time and just went full spaghetti mode.

  • Everything else: ran out of time after solving D, didn't have time to look at

tl;dr contest is good, diff spike from B to C is reflected in scoring, I personally liked D the most.

A fitting meme for me after I inted this contest:
»
15 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Why can't I look at someone else's code yet?

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

i thought E was cool even though it was guessable

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

Problem D was nice.

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

Going to be CM!:)

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

    As someone who has also had 1899 long time before i've reached CM, I congratulate you from the bottom of my heart ^_^, you've probably felt quite a lot of pain before becoming CM, and now you will finally be able to enjoy it!! wish you all the best

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

For problem C, why is it optimal to always choose the values of $$$x_i$$$ and $$$y_i$$$ so that they have the maximum difference?

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

    assume $$$x_{i} \le y_{i}$$$, therefore it must be $$$\dots y_{i-1})(x_{i},y_{i})(x_{i+1} \dots$$$ and $$$y_{i-1} \ge x_{i+1}$$$. Therefore, if $$$x_{i}$$$ decrease and $$$y_{i}$$$ increase, the answer will be smaller.

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

    Suppose that you have an optimal solution. Let's say that in the final sum $$$x_i$$$ is mulitplied by some $$$a$$$ and $$$y_i$$$ is multiplied by some $$$b$$$.

    Suppose $$$a<b$$$. Then it's always a good idea to increase $$$x_i$$$ and decrease $$$y_i$$$ (try it : a simple inequality). There is a similar reasoning if $$$b<a$$$. So if the solution is optimal, it should be the case that either $$$x_i$$$ is maximal (and so $$$y_i$$$ minimal) or $$$x_i$$$ is minimal (and so $$$y_i$$$ is maximal).

    edit : took too much time to time but I'm leaving my answer here just in case.

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

    if y[i-1]=x[i+1], the values of x[i] and y[i] don't matter, so we can assume they have the maximun difference (which will not let the answer become worse), and if not, WLOG assume y[i-1]>x[i+1], if abs(x[i]-y[i]) is not the maximum, we can do x[i]--, y[i]++ to get a better answer.

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

      Thanks!

      I actually noticed that for $$$n=3$$$ and the intuition from there seems so simple now. But instead of getting to the final observation I filled pages with useless stuff haha.

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

the system test has finished, but my solution on C did not judge, what happened?

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

system test has finished, but I can't submit why?

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

I believe the initial statement of problem C was incorrect as usual mathematical notations, and I cannot believe that many people could read it (super brilliant people would guess it from the title so I can believe there exist such people, but...). So I felt this contest was unfair, sad.

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

I dislike A to F. They are all boring guessing or implementation problems. All of them have quite obvious solutions.

Problem G is really great. I gain lots of rating thanks to this problem :D

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

Radewoosh E failed system testing. Unlucko

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

tourist back on top

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

The problem F is a typical problem with easy idea and painful implementation. If we only need to find the minimal value it would be like about div2D.

It's obvious that the target function (sum(1/f(i))) is the number of cycles in a permutation, and on each day, an even cycle is decomposited into 2 cycles with half size, and an odd cycle is changed order (but size remain the same). Thus if there's some even cycles with size n on the last day, there must be a cycle with size 2^k*n initially, therefore if the count of n-size cycle <2^k, there's no solution. If there's any solution, we need to merge 2^j cycles with same size (for even cycles j=k, and for odd cycles j=the maximum value that j<=k and 2^j<=count of cycles with same size) into one cycle, and before merging, we need to backstep these cycles to the day their size became odd (by raising them to the mod power of k-j).

Update: Now my submission:191169251 has got AC. I can't remember how many times I've fixed a solution right after the contest ends, which didn't get AC in contest since some minor bugs.

Implementation notes: The 2 major tasks for F are "merge 2^j cycles into one" and "backstep an odd cycle to k-j days before". For the first task, we can write the cycles by rows and read them by columns, like this:

cycle #1: 1->2->3 (->1)

cycle #2: 4->5->6 (->4)

cycle #3: 7->8->9 (->7)

cycle #4: 10->11->12 (->10)

cycle merged: 1->4->7->10->2->5->8->11->3->6->9->12 (->1)

This cycle will be decomposited into cycle #1, #2, #3, #4 in 2 days. And for the second task, let the size of cycle be n, if we backstep it by one day, it will become the (n+1)/2-th power of itself, where (n+1)/2 is the inverse of 2 modulo n. So we can backstep each cycle by (k-j) days using fast power.

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

there are some bugs with system testing hope you fix them

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

I solved problem A but I cannot prove why there is no solution when $$$n$$$ is odd, what is the proof of that?

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

    Let's say any of x,y is even then y*x^y+x*y^x is also even, and if both are odd then also it's even so whatever you choose x,y the parity of y*x^y+x*y^x is even.

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

    Since $$$x$$$ and $$$y$$$ are positive integers, $$$x^y$$$ has the same parity as $$$x$$$, so $$$x^y \cdot y + x \cdot y^x$$$ has the same parity as $$$2 \cdot x \cdot y$$$, which is always even.

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

      well the logic seems quite easy now , but at the time of the contest it was very hard to decipher , had to guess it .

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

        Or you could alternatively check for all possible values of (x % 2, y % 2)

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

When can we submit and upsolve problems, like I am unable to submit even after system testing.

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

Awesome contest!

  • Can't say anything about A, common problem.

  • Greedy in B, I didn't prove, judged by the fact it's B that there wouldn't be any difficult idea. I didn't like it though.

  • Very interesting problem. The first thought when I read it was "It is real garbage, I need to guess somehow $$$x_i$$$ and $$$y_i$$$ and print the answer". I thought about it a little and went on. After solving other problems, I returned to it and suddenly understood that the idea is okish. I now have no idea why many (me too) disliked it too much. Seems like good C.

  • Good (or average) problem, has an obvious solution (when you solve it on paper), but is difficult to implement, to gather the general thoughts. Handling cornercases and doing something similar to finding SCCs is a bit tricky, but I coped with it fast enough.

  • I felt like E is too easy for its place. The idea (subsequences with length 1 or 2 are required) was probably good, but for some reason I didn't struggle with coming up with it and didn't get much excitement.

  • Problem F was the most difficult one I solved during the contest. The idea is probably a bit straightforward, the problem requires some unwrapping (the part $$$\sum\limits_{i = 1}^{n}\frac{1}{f(i)}$$$ was really fun). Maybe it's a bit technical, but I liked it.

  • It was absolutely mindbreaking that G could be handled with centroids, but it seems it does. Then it's quite easy (not to implement though), but the idea was really unexpected. I feel like I fixed the last bug 1,5 minutes after the contest end :(
    UPD: Well, ok, it didn't work. Sad :(

  • Didn't think much about H or I. Liked the H statement, though: it's very natural!

Interestingly enough, it seems I like implementation problems more that the idea ones. Wouldn't say it if asked, though. Anyway, the contest was great.

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

    How to solve G with centroids?

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

      It's nothing, just use the solution in the editorial and add centroids there)

      (Store paths not by lca of their ends, but by the lowest centroid of them and when updating a vertex, walk all the path-to-root in centroid decomposition, $$$O(n\log^2{n})$$$).

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

        Thank you for making me read the editorial, see that it made no sense only to then realize that I didn't read that a good path must have all edges of that color.

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

191126284 is still in "Pretests passed" status, is there are something wrong of the judge system?

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

i can not send a solution even though the contest is over rsj

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

B has weak test cases. https://codeforces.com/contest/1787/submission/191170706

Test Case:-

1
4194304

Should output 44. Outputs — 40.

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

Meh, with GNU C++20 (64), GNU C++17 (64) and GNU C++14 (so all other compilers) my solution gets RE on pretests, but with GNU C++17 (chosen by me during the contest) it somehow keeps working and passes (and UB shows up on systests).

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

    Unlucko

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

    The most interesting is that you get Accepted on main tests when contest was running. You are so unluckily!

    I see your code. You got RE because you visit the wyn[0] when it is empty. It is UB. Notice std::vector<T>::clear() do not free memory. So it will only get RE when it is the first case sometimes.

    So following codes can run successfully and print 2 0 (GNU G++14 6.4.0 on Custom invocation of CodeForces):

    #include<bits/stdc++.h>
    using namespace std;
    int main(){
    	vector<int> a;
    	a.push_back(1);
    	a.clear();
    	a[0]=2;
    	printf("%d %d",a[0],a.size());
    	return 0;
    }
    

    I recommend to use vector<int>().swap(a) to clear the vector a with freeing memory. However, it spends more time because it frees memory.

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

Lucky I reached blue even after being ranked 1800+

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

is this vaticle job remote or onsite.

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

what will be rating of D?

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

F is just stupid implementation.

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

500 Euros to ko_osaga.

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

When will the prize distribution for 51-250 places be published?

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

I'm sorry

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

Thanks to the authors for balanced set of interesting problems and accurate score distribution! C is my favorite one, rare combination of greedy and DP concepts in the same problem, perfect mix for casework lovers!

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

Hey, the system says my submission 191137200 matches 191132505 while that guy just used my template and nothing else. If you check the solution carefully, you'll see I wrote a 3*n state dp while that guy wrote 2*n state dp. There is no way we copied each other. How and where do I proved this? Infact, all my solutions from that round got skipped due to this. Please help me someone :'( MikeMirzayanov

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

    Moreover, the ArPiT_ErrOr is a dummy/fake handle who has just solved 6 problems and all his submissions are after mine for this contest. As you can see I use the same template for every problem which can be seen from all my submissions. Also, that user has used different templates for different contests which clearly seems suspicious. Please look in this issue and every other issues like this in general MikeMirzayanov.

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

Why did this contest get unrated?

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

Has this round become unrated?? Ratings have not been updated yet. If yes then please also tell me the reason.

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

The ratings for this round were rolled back, but there is no yellow alert which used to be there. The round hasn't been declared unrated, has it?

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

Is it rated?

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

Correct me if I am missing something.

This round is yet to release its rating. The round followed by this one was a Div. 2 exclusively. Suppose someone rated <2100 attempts this round has reaches Div 1. category. As the rating were rolled back, they will have the chance to also compete in the Div 2. round followed by it. It might even be possible that they surpass this division again, but ideally, the round should have been unrated for them.

Can someone please explain how a case like this is handled, or provide me a blog where this is already answered?

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

    This has happened in Round 829/830, except that was a kind of weird contest because 830 (for Div. 2 only) started only 15 minutes after 829 ended. The result that time is quite a few masters were rated in a contest meant for Div. 2. But I don't know if they're going to handle it the same for this.

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

Meanwhile, me waiting till eternity to see my updated rating lol :)

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

Why my rating of this contest is rolled back? :'''''( When will it come back? :''''(

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

is the rating of this contest visible in your profile?

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

Something is going on?... Is it related to those strange submission timings of H from those high ranking contestants? According to editorial, H is a original problem, and the authors "Have to declare that we built up Problem H from zero. ;)"...... Well, I never identify high-rankers with high moral standards and I can take whatever would happend next......

(Hope it is just some tech issue, and I would keep my +22 delta ^_^)

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

I just want my +63 :(

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

Why I am not rated for this round?

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

Congratulations to the hoodie and t-shirt winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_tshirts.py
randgen.cpp

TypeDB hoodie, t-shirt and stickers

List place Contest Rank Name
1 1787 1 ko_osaga
2 1787 2 tourist
3 1787 3 Radewoosh
4 1787 4 Benq
5 1787 5 ecnerwala
6 1787 6 Um_nik
7 1787 7 Rebelz
8 1787 8 orzdevinwang
9 1787 9 zihouzhong
10 1787 10 feecle6418
11 1787 11 noimi
12 1787 12 IOMO
13 1787 13 ksun48
14 1787 14 ainta
15 1787 15 inaFSTream
16 1787 16 maroonrk
17 1787 17 jiangly
18 1787 18 WYZFL
19 1787 19 SSRS_
20 1787 20 Ormlis
21 1787 21 dl720125
22 1787 22 Golovanov399
23 1787 23 skip2004
24 1787 24 ugly2333
25 1787 25 hank55663
26 1787 26 Xylenox
27 1787 27 PubabaOnO
28 1787 28 BurnedChicken
29 1787 29 hos.lyric
30 1787 30 Kubic
31 1787 31 Rubikun
32 1787 32 Vercingetorix
33 1787 33 tatyam
34 1787 34 yarik_mutltiacc
35 1787 35 PinkieRabbit
36 1787 36 blackbori
37 1787 37 Tlatoani
38 1787 38 Endagorion
39 1787 39 daubi
40 1787 40 Merkurev
41 1787 41 QAQAutoMaton
42 1787 42 NoPotato
43 1787 43 mango_lassi
44 1787 44 KaguyaH
45 1787 45 oleh1421
46 1787 46 Mr_Solution
47 1787 47 244mhq
48 1787 48 Xellos
49 1787 49 nantf
50 1787 50 kotatsugame

TypeDB t-shirt and stickers

List place Contest Rank Name
60 1787 60 A_G
61 1787 61 tute7627
63 1787 63 Pyqe
67 1787 67 Toxel
70 1787 70 alexxela12345
73 1787 73 A-SOUL_Bella
75 1787 75 Maksim1744
76 1787 76 huangzirui
77 1787 77 jdurie
85 1787 85 HollwoQ_Pelw
89 1787 89 satashun
91 1787 91 Nyaan
98 1787 98 KevinWan
100 1787 100 qiuzx
104 1787 104 SirShokoladina
106 1787 106 Hyperbolic
107 1787 107 torisasami
108 1787 108 fireskydd
109 1787 109 -14
110 1787 110 KroosTheKeenGlint
125 1787 125 Fysty
131 1787 131 w.omais
132 1787 132 zsyzsy
133 1787 133 ai_dev_master
144 1787 144 Arraiter
157 1787 157 Sulfox
162 1787 162 olmrgcsi
165 1787 165 kshitij_sodani
173 1787 173 wyzwyz
178 1787 178 Kevin114514
183 1787 183 Gheal
184 1787 184 18Michael
187 1787 187 chen_zexing
190 1787 190 duality
193 1787 193 natofp
195 1787 195 Ecrade_
196 1787 196 LipArcanjo
199 1787 199 frokaikan
209 1787 209 Amanda_LWA
212 1787 212 CJ-zhuyifan
213 1787 213 DoorhandleMahoushoujo
214 1787 214 ComPhyPark
216 1787 216 eunlin
217 1787 217 Amtek
222 1787 222 HugeWide
229 1787 229 lilvan
233 1787 233 glebustim
238 1787 238 Alexdat2000
241 1787 241 pooty
245 1787 245 zqyyy