rsj's blog

TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!)
By rsj, 22 months ago, In English

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:

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

Comments Comments (229)
| Write comment?
»
22 months ago, # |
  Vote: I like it -51 Vote: I do not like it

omg cyan round
GL to everyone

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

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.

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

    I think you are lier

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

      I am not. You are not a tester, so you do not know what problems were in there originally.

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

        Many problems have changed. This is a new set of questions for me.

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

Another 500 Euros to tourist.

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

omg recruitment round

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

One more NP task with 74TrAkToR ?))

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

Wow! 9 problems with 0 subtasks

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

interesting contest!

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

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

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

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

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

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

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

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

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

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

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

    How can you say before the contest?anybody can win it.

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

      Are you new to codeforces ?? Because everyone knows who has undefeated legacy this whole time. 

      It's The Tourist.
      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +36 Vote: I do not like it

        undefeated legacy

        indeed...
        → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        Don't you physically cringe at yourself when you sit down and type stuff like this?

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

E_huan orz

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

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

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

    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

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

Knock-knock!

Who?

Knapsack.

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

it will be going between tourist VS Benq

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

Ez 500 Bucks for me

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

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

omg unrated round!!!

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

I anticipate that this will be a trash chinese round.

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

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

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

Score distribution looks scary

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

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

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

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

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

IsaacMoris wants to participate can you delay the round 15 minutes

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

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

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

My Prediction: The round will be pretty hard.

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

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

lmao it's completely a Mathforces Round.

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

Math contest is the most boring contest.

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

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

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

Math forces

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

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

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

problem B and C are horrible imo, very annoying

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

    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.).

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

How can someone do problem H in 14 minutes.

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

    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.

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

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...

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

    They are quite fast at both typing and thinking.

    While typing i guess they were thinking too.

    The prefect combo makes them do everything within 1min.

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

    arpandesai0 sir tell us

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

LMAO Classic Mathforces

Disappointing contest

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

    Pairforces indeed.

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

    What is wrong with a contest which is "math-y"? You still need to use your brain to solve the problems

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

      It doesnt feels good to me to solve these problems which doesnt include DSA

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

      Such people don't like to actually solve problems, they like to copypaste/sligthly modify standard DSA to get AC.

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

    I love Maths. Because (my_username).

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

Watching the GODS chasing is interesting!

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

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

I hope C is a 1800+ problem

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

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

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

    Was it really bad ?? I am the only one enjoying it ??

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

      The solution Idea was good, but it could have been framed in a much better way

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

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

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

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

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 3   Vote: I like it +12 Vote: I do not like it

      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.

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

        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.

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

        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)

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

Another Great Rated round! ^_^

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

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

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

tourist will not able to sleep tonight.

→ Reply
»
22 months ago, # |
← Rev. 7   Vote: I like it -57 Vote: I do not like it 
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
→ Reply
»
22 months ago, # |
  Vote: I like it +50 Vote: I do not like it

Worst C problem I have ever seen

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

how to solve D?

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

    Cyclic counting (Brent's algorithm)

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

      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

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

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

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

    If it asks for the minimal value, it would be easier than C (just in my opinion)

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

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).

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

    dynamic programming !

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

      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)?

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

        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]

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

          basically just check if the previous one is flipped or not

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

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

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

              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

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

        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.

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

    Theme: Dynamic programming

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

    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

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

    DP will do the job.

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

    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})$$$.

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

      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

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

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

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

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

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

      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 ;-;

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

Horrible problemset, wacky unclear statements

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

Hint for C please!

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

    Dynamic Programming and Math

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

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

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

I is the same as https://ac.nowcoder.com/acm/contest/9328/B

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

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

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

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

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

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!

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

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

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

    how did you know?????

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

      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

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

Unlock the submissions.

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

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.

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

    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 ?

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

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.

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

    E hint pls

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 3   Vote: I like it -8 Vote: I do not like it
      hint
      → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Spoiler
      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it
        Spoiler
        → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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?

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

      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).

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

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

Very frustrating.

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

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

Errichto vs C hehe

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

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.

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

    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...

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

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.

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

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:
→ Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

i thought E was cool even though it was guessable

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

Problem D was nice.

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

Going to be CM!:)

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

    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

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

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?

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

    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.

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

    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.

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

    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.

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

      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.

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

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

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

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

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

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.

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

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

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

Radewoosh E failed system testing. Unlucko

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

tourist back on top

→ Reply
»
22 months ago, # |
← Rev. 5   Vote: I like it +54 Vote: I do not like it

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.

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

there are some bugs with system testing hope you fix them

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

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

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

    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.

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

    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.

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

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

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

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

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

    To get an odd $$$n$$$ such that $$$a+b = n$$$ either $$$a$$$ is even and $$$b$$$ is odd, or $$$a$$$ is odd and $$$b$$$ is even.

    So, with $$$x^y \cdot y + y^x \cdot x = n$$$ with $$$n$$$ being odd, either $$$x^y \cdot y$$$ or $$$y^x \cdot x$$$ have to be even, and if either of them is even, that means that either $$$x$$$ or $$$y$$$ are even, and if that's the case, $$$x^y \cdot y$$$ and $$$y^x \cdot x$$$ would both be even.

    So it's impossible for one of them to be even and the other to be odd at the same time.

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

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

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

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.

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

    How to solve G with centroids?

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

      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})$$$).

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

        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.

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

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

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

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

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

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

Test Case:-

1
4194304

Should output 44. Outputs — 40.

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

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).

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

    Unlucko

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

    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.

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

Lucky I reached blue even after being ranked 1800+

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

is this vaticle job remote or onsite.

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

what will be rating of D?

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

F is just stupid implementation.

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

500 Euros to ko_osaga.

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

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

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

I'm sorry

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

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!

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

    C was annoying af

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

      Thinking in general is annoying but some people like it. That's the reason we have platforms like Codeforces.

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

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

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

    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.

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

      Totally agree with your points.

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

      190535543 is one submission that I made before the contest. You can see I have been using the same template from quite a while.

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

Why did this contest get unrated?

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

    it is not unrated, it just rating roll backs for checking of cheating.

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

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

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

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?

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

Is it rated?

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

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?

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

    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.

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

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

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

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

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

is the rating of this contest visible in your profile?

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

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 ^_^)

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

I just want my +63 :(

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

Why I am not rated for this round?

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

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
→ Reply