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:

- 74TrAkToR, for a long-term, tough and perfect coordination.
- qzhwlzy, for writing and polishing statements and tutorials, and sparky ideas.
- jiangtaizhe001, for helping me a lot in preparation.
- 275307894a and A_zjzj, for providing wonderful problems and solutions.
- carnation13, willy108, NemanjaSo2005 and Iridescent2020 for great suggestions to the problems.
- NemanjaSo2005, Iridescent2020, 1000--7, WGYHMFkZyA02, xiongyushun, dorijanlendvaj, AlexLuchianov, Gary2005, SSerxhs, RUSH_D_CAT, Lavine, Kieray, Alice114514, Atziluth, Depth_First_Search, OdtreePrincess, A_zjzj, _WD_, 275307894a, Electric_Field, carnation13, Hanriver, some_idiot, willy108, gamegame, Pointy, Huah, ShmilyTY, njupt_lyy, E_huan, p_b_p_b, jjjjssss6, HolyK, -skyline- and Isla81920, for testing the contest and providing useful feedback.
- MikeMirzayanov, for the great systems Codeforces and Polygon.

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

**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:

**UPD1:** Editorial

**UPD2:** Congratulations to the winners:

omg cyan round

GL to everyone

profile picture stealer :D

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.

maybe

I think you are lier

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

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

The announcement post redirects to a draft (not visible to general audience), not a blog.

Another 500 Euros to tourist.

or benq!

or tibinyte!

tibinyte will earn -500 Euro

the tourist caught up with the bank in the ratings

or jiangly (◠‿◠)

or you too(◠‿◠)

or God Um_nik!

NOoBODy thinking about maroonrk or Radewoosh

the prizes are incredible!

Again 500 Euros to tourist.

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

Or ko_osaga ._.

omg recruitment round

omg recruitment round

One more NP task with 74TrAkToR ?))

Wow! 9 problems with 0 subtasks

500 euros? yall are broke :clown:

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

Are you from future?

they have a vision of the future

maybe

Problem F is also somewhat copied from Xenia and Tree, you can ask query 2 v just after querying 1 v.

How did you get to E as a specialist? I only solved ABC

He is referring to this Div3 contest held yesterday https://codeforces.com/contest/1790

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

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

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

Of course it's with a prize t-shirt and stickers, 100, 250, 500 Euros

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

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

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

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

E_huan orz

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

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

Knock-knock!

Who?

Knapsack.

Knock-knock!

Who?

DP!

Haha.

Actually I am Enthusiastic for this round hope the best for everyone :D

it will be going between tourist VS Benq

Ez 500 Bucks for me

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

whoever gets 500 euros is lucky

Being awarded gives coders motivation .Hope we will enjoy it)

omg unrated round!!!

Rated

nooooo, it's unrated round

Ok. Provide evidence for your opinion

I anticipate that this will be a trash chinese round.

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

Score distribution looks scary

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

Mathematics is the queen of the sciences.

Mathspeedforces,GOD!

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

it should be tough for 1200 to solve C anyways..

IsaacMoris wants to participate can you delay the round 15 minutes

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

My Prediction: The round will be pretty hard.

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

How bad will this affect for participants from division 3, 4?

lmao it's completely a Mathforces Round.

OMG，Math Round! I can't do it at all.Go to bed. Good night...qwq

Math contest is the most boring contest.

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

Math forces

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

Possibly a great decision

problem B and C are horrible imo, very annoying

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

Math_is_NOT_Good

How can someone do problem

Hin 14 minutes.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.

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

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.

arpandesai0 sir tell us

Confuse about Problem B's time limit. There is no guaranteed statement.

LMAO Classic Mathforces

Disappointing contest

Pairforces indeed.

more like Painforces (T＿T)

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

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

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

I love Maths. Because (my_username).

Watching the GODS chasing is interesting!

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

I hope C is a 1800+ problem

Same man

Come one you can do it. I am the same colour you are.

It's atmost 1700.

I'll try just one more time... Wish me luck.

Wish you luck.

I failed man!

No problem. You never fail. Either you win or you learn.

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

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

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

Are you going to upload solution video ?

If no, then please atleast upload for C. It was one hell of a problem..

YES.

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

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

SpoilerYou can see that for every $$$i$$$, either $$$x_i$$$ is minimum possible and $$$y_i$$$ is maximum possible or vice versa. And now you can dynamically program the solution.

Wait! Wouldn't greedy work, i.e if $$$x_i$$$ is minimum and $$$y_i$$$ is maximum till some point $$$k$$$, and from $$$k+1$$$, $$$x_{i+1}$$$ is maximum and $$$y_{i+1}$$$ is minimum. And the answer is minimum of all $$$k$$$ s.t $$$0<= k < n-1$$$?

Opps! got it, they need not to be in that order, $$$x_i$$$ can take any of the extreme value and $$$y_i$$$ would take the other.

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.

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.

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)

Another Great Rated round! ^_^

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

yea, i agree too many math

is B supposed to factorize prime?

yes

tourist will not able to sleep tonight.

lol truee he'll upsolve second last problem

Oh fuck, not again...

Worst C problem I have ever seen

how to solve c?

I did it with prime factorization

update: sry mistake prblem B, not that

HintDynamic Programming

how to solve D?

Cyclic counting (Brent's algorithm)

SpoilerLet $$$s_x$$$ be the number of nodes that can reach $$$x$$$ (including $$$x$$$) and $$$c$$$ be the number of nodes that doesn't end up in a cycle. Iterate through graph starting from node 1. Let $$$i$$$ be the current node.

Finally if path starting from $$$0$$$ doesn't end up in cycle then all the nodes that are not reachable from $$$0$$$ can take $$$(2*n+1)$$$ values.

solutionYou have a functional graph, and for each vertex

`v`

you want to ask for a number of vertices`u`

, that if can connect`u`

with`v`

, the vertex`1`

will not be on cycle. You can compute by dfs which vertices are not on any cycle, and just connect all vertices on path from '1' to those. However, there are some edgecases i.e. you can't connect a vertex that is on path from '1', to another vertex that was before on path from '1', or vertex that leads to a vertex that was before on path, or you can't connect a vertex to itself, or you can't connect a vertex that is. But the main idea is just counting vertices that are not on any cycle.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

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

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

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

dynamic programming !

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

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]

basically just check if the previous one is flipped or not

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

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

use dp you have

x+y=a[i]and(x-s)*(y-s)>=0so ifa[i]>sthen it's better to choosex=s and y=a[i]-s(or vice versa). or ifa[i]<sthen it's better to choosex=0 and y=a[i]why ? obeservation. then you just simply apply dp.Theme: Dynamic programming

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":

Upd. answer is 52

DP will do the job.

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

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

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

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

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

Horrible problemset, wacky unclear statements

Hint for C please!

Dynamic Programming and Math

SpoilerDynamic Programming...

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

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

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

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

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!Wow, I actually remember this problem from polish competition (but didn't realize it during the contest ;_;) and almost all solutions (including model one) used bst.

That Prime Contest task discussion

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

how did you know?????

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

Unlock the submissions.

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.

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 ?

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.

E hint pls

hintm-1(or m-2) pairs

SpoilerLeave all the pairs with xor value $$$x$$$. What can you do with the remaining numbers?

Spoiler...their xor will be (xor of [1..n]) ^ (0 if no pairs is even else x) Aha! Gut problem

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

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?

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

Enter contest. Solve A,B,C . watch last 1 hour top standings page, well it got intense in last 15mins ...

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

Very frustrating.

how to solve B?

One day i will pass you tourist

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

Errichto vs C hehe

after 5 minutes ;-;

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.

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

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.

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:Problem C seemed more difficult to me. But the issue is very well structured

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

i thought E was cool even though it was guessable

Problem D was nice.

Going to be CM!:)

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

Thank you! And hope you to be M soon :)

Thanks, same to you! :)

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?

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.

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.

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.

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.

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

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

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.

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

Radewoosh E failed system testing. Unlucko

tourist back on top

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

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.

Can someone verify my logic? Thanks in advance

Problem CConsidering x[i] > y[i](x[i] < y[i] can be done symmetrically),

for every i from 2 to n-1(1 based indexing), we must pick the maximum x[i] and the respective y[i]

ProofLet in the optimal answer we multiply x[i] with p and y[i] with q with cost x[i]*p + y[i]*qLet p <= q(p > q can be done symmetrically)

Now, if we don't multiply the max possible x[i] with p then their exists an answer where cost will be (x[i]+1)*p + (y[i]-1)*q => x[i]*p + y[i]*q + p — q. But since p <= q, this scenario will give a lower or same answer

So we just need to work on extreme values with 4 cases which can be done with DP

Is this correct?

there are some bugs with system testing hope you fix them

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

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.

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.

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

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

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.

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

rsj

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.

How to solve G with centroids?

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

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.

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

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

To hard Contest More Like Problem Based on Math's Concept

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

Test Case:-

1

4194304

Should output 44. Outputs — 40.

Ok

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

Unlucko

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):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.Lucky I reached blue even after being ranked 1800+

is this vaticle job remote or onsite.

what will be rating of D?

0

F is just stupid implementation.

500 Euros to ko_osaga.

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

After I process cheaters. At most 1 day.

its been 4 days dude

So the rarings are back, when will we have prize distribution (for 51-250 places)?

Hi I'm new you are all suckers

Good contest.

I'm sorry

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!

C was annoying af

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

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

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.

Totally agree with your points.

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

Agreed, MikeMirzayanov please fix this issue.

Why did this contest get unrated?

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

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

Hey, I participated in this contest and made 2 successful submissions. But it is not being shown on my contests list and my ratings didn't change after this. But it is showing my submissions.

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?

same question

Is it rated?Yes, after skipping the cheaters

I'm waiting too

thx

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?

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.

Thanks a lot, this explains a possible solution.

why was my rating increased first, and then removed, and not only from me, but from everyone?

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

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

is the rating of this contest visible in your profile?

Why is it unrated?

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

your picture looks familiar,I may have seen you on bilibili :)

I just want my +63 :(

Why I am not rated for this round?

All are rated for this contest but codeforces is busy to catch the cheaters.

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.pyrandgen.cpp## TypeDB hoodie, t-shirt and stickers

## TypeDB t-shirt and stickers

Another 600 Euros to tourist.