As a celebration I ate a slice of bread with nutella: Making of nutella bread

Just gave deepseek a 1800 rated question with tutorial explaination it still couldnt generate a correct solution

To be fair, most cf users are no smarter than deepseek in this aspect.

Downvoted.

The problem D is the shitest problem I have seen.

Finally got master!

Lol, a ratist cyan

The editorial for D is made for people who have successfully solved the problem in the contest. The editorial is not clear at all !

Why guessforces???

D>>>>>>>>>>>>>>>>>>>>>E1

jeroenodb is definition of perseverance. Congrats on well-deserved LGM sir!!! orz

Bro lost on Truth or Dare :skull:

probably just me, but why did D and E both have to be tree problems

A: Answer is simply initial count of '1'

B: Answer is true if and only if a[i]>2*max(i, n-1-i) for all 0<=i<=n-1

C: Do operation 2 and pick the absolute value of sum(a[i]) at this moment, as a candidate answer. Repeat until length of a[i] become 1. The initial sum is also a candidate answer

D: Assume a[i] has been decided, then the answer is sum(max(0, a[u]-a[parent(u)])), where a[parent(u)]=0 when u is the root. Then we can find the answer simply by dp

E1: For any node u, if there's any other node v such that v is not in subtree of u, and w[v]>w[u], we call u "good node". Then any good node with maximum w[u] could be the answer.

F: Sort all pairs such that for all 0<=i<n-1, we have (a[i]-b[i]<a[i+1]-b[i+1]) or (a[i]-b[i]==a[i+1]-b[i+1] and a[i]<=a[i+1]). Then candidate answers will be:

• maximum value of b[i]+a[j]+ sum(a[t]+b[t]) (i<j, sum over several t (possibly none) with i<t<j)

• maximum value of 2*b[i]+a[j1]+a[j2] + sum(a[t]+b[t]) (i<j1<j2, sum over several t (possibly none) with i<t<j2 and t!=j1)

• maximum value of b[i1]+b[i2]+2*a[j] + sum(a[t]+b[t]) (i1<i2<j, sum over several t (possibly none) with i1<t<j and t!=i2)

• maximum value of 2*b[i1]+a[j1]+b[i2]+2*a[j2] + sum(a[t]+b[t]) (i1<j1<i2<j2, sum over several t (possibly none) with i1<t<j2 and t!=i2 and t!=j1)

We can find the answer by simple DP.

Problems on recursion always look for me like "do the exact implementation, as author did".

As a tester, I confirm that StarSilk is a cat.

wtf this is something like only green people would post ecept +1000 in rating

how to solve *2500 easily, dont say practice

Guessforces. So helpless when coding.

Thanks for the nice contest! I definitely had a good start, and I think mainly due to a fast start I got my LGM! Then I got stuck on the other problems, but they were fun to think about. My experience with the problems:

• A: funny. I think it's the first time I've had a 0:00
• B: Fun to find some conditions and see that they are necessary and sufficient.
• C: Pretty fun, felt easy to me, but maybe it is luck.
• D: I wanted to be fast, so didn't rigorously prove it. Felt quite hard, and I felt I was slow on it, although implementation was easy. Turns out I was not slow.
• E1: Ok problem, indeed a bit easier than D.
• E2: have some ideas of how to solve, but they were all quite cumbersome. I think it's mostly a DS problem, but it seems quite a nice one, it's not easily killed with some bash it seems.
• F: Nice problem, I liked my geometric interpretation a lot, and the DP was not bad to write.
• G: Maybe not a problem I would like, but there was enough other things to try. I didn't spend any time on it.
• H: Thought about it for a bit, seems neat, but didn't put too much time in. Got to the point where I was thinking about bounding boxes of the different galaxies, and tried to turn it into some bitmask DP.

I think all problems are very good (at least until F), but putting them together in a single match is somewhat strange.

The Gap between C, D/E1, and E2/F are all too big (the number of accepted participants differs by almost 10 times). I was lucky enough to notice the key to E2 immediately after solving E1 and ended up in a good position. Though many participants got stuck in a single problem (C,D,E2,F are all problems where one could easily go wrong and never come back again), which led to disastrous results.

It would be better to have an easier D and an easier F. In this case the round would be more balanced and a small mistake wouldn't cause too much damage for a single participant.

Agreed. It cost me at least 50 mins.

Over 150 people passed only A,B,C,E,F but can't pass D.(including me)

We're not beating the speedforces allegations with this one!

In all seriousness I enjoyed A-C even if they were rather guessable, but there really should have been a problem in between C and D/E1

honestly llms are gonna remain good at doing things that are already done. True creativity is gonna take a long time.

carrot extension is not working anymore?

guessforces!

said the guys who's been here for 4 years and solved + 1200 problems but still cyan

only works cuz he's orz i.e. he should be LGM anyways, he just does this for fun

Are you tired of the inconsistencies and unpredictability in competitive programming evaluations?

Not really..? Isn't that what competitive programming is? We test our code on how it performs in real life rather than like TCS people do.

specialists are not allowed to complain. Suck it up !

jeroen is just a geniosity tbh

My screencast (in Rust) will be available once it ends uploading

I think 800

What I did in the contest:

Guess A, then passed.

Guess B and passed.

Guess D and get WA.

Guess C and passed.

Guess D for another solution and passed.

Guess E1 and passed.

The contest end.

What a terrible experience!

I noticed that for P4, the difference between a set and ordered set is the difference between 105 points and 120 points. So very weirdly an ordered set would be faster than a regular set in this case. Does someone know the reason for this.

I have an impropriate analogy about today's C and D. Sorry for any insult.

And the second is like using the gravitation Newton discovered to build a big rocket.

how to do DIV 2D?

There should be a row with the average and median. ^_^;

I like the variance in predictions

The edges without cats on them form a tree with a cycle (there are n edges and any node can be reached from any other node). The edges with cats form a directed graph. You need to add some edges from the tree to the directed graph & orient them such that there is an eulerian cycle in it. The condition for a directed graph to have an eulerian cycle is for the indegree of each node to equal its' outdegree and for the graph to be connected when ignoring orientation (except for some isolated nodes).

First, remove one of the edges from the cycle so that the tree is actually a tree and solve separately for the 3 cases (omitting it, orienting u -> v, orienting v -> u). Then just process the tree in post DFS order (so, starting with the leaves) and decide what to do with the edge from this node to its' parent (if indegree == outdegree do nothing, if outdegree == indegree-1 add the edge u -> parent, etc). At the end check if the graph is connected and all the degrees match. Answer the minimum of the 3 cases.

• The operation can be rephrased as follows: choose any edge in the tree, consider the two subtrees resulting from removing that edge, choose one of those subtrees, and increment all values in it by 1.

• Consider any assignment of initial values to the nodes. For any two nodes connected by an edge, if they have different initial values, they can only become equal if we perform the operation selecting the edge between them, and incrementing the subtree of the smaller node.

• Now, consider what the value of node i will be in the end. We can find this value by rooting the tree at i. The final value after the tree becomes balanced will be val[i] + sum(max(0, val[u] — val[par[u]])). Basically if val[par[u]] < val[u], we will need to increment everything above u.

• We can prove that actually rooting at any node j != i will yield the same result as i. One way to prove this is by considering what happens to the result when we move from i to a neighbor.

• Finally, this means we can just root arbitrarily, and greedily minimize sum(max(0, val[u] — val[par[u]])).

as participant i will share you a fact for fun, if you write a number n>=100 and n<=999 and write the same number to it's exactly right, then the new 6 digit number formed will be divisible by 1001.

how to do p5 T-T

Bro now we are all GM!

As a witness, I can prove that he solved the contest himself.

Solved problem C after 10 tries, thanks to the corner case $$$2\times p$$$ when $$$p >= 3.5 \cdot 10^8$$$

(If $$$n = 2^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3} ...$$$ then my $$$m$$$ was $$$2^{a_1+2}\cdot p_2^{a_2+1} \cdot p_3^{a_3+1} ...$$$ which was greater than $$$10^{18}$$$)

Edit: this solution is a little crazy and unproved, but seems to work. I bruteforce for that $$$m$$$ to find the first $$$a$$$ such that $$$a^{nk} \equiv 1\ (mod\ m)$$$ and $$$nk$$$ is the smallest. when $$$n = 2^{a_1}\cdot p_2^{a_2}$$$ I chose $$$m = 2^{a_1+1}\cdot p_2^{a_2+1}$$$ instead of $$$m = 2^{a_1+2}\cdot p_2^{a_2+1}$$$

In Editorial of C :

Unable to parse markup [type=CF_MATHJAX]

Fixed

Considering the fact that I've lost 9,6% of my rating, I don't think this round was that good for me xd

Bad C. During the contest I used Solution 2 , and it seems that it is much harder than Solution 1. Are you palying brain teasers with us?

jeroenorz

jeroenodb OTZ OTL OFZ OLZ ORZ oz osz sto ozz oyz roz hso ost OJZ OPZ <(_ _)> O]L O[Z orx ozk OFX огz лго 口厂乙 ОГZ :weary:rz rto fTO PTO rso fSO stotz :wheelchair:rz

G and H are also great!

As a participant, I can confirm that $$$1001$$$ is a composite.

Here was my thought process:

Started with a naive solution (recursion): At each step, we can do one of three things: - Accept the current sum and stop the process - Reverse the array - Replace the array with its diff (as explained in the problem statement).

This worked, but is super slow, so let's see how we can optimise it.

First observation, since the length of the input array is 50, we can replace the array with its diff at most 49 times (specifically, at most n-1 times), after that, we can no longer make any move.

Second observation, reversing the array twice consecutively is worthless, as it will have no effect on the result.

From these observation we conclude that we are looking for a sequence of operations such that there is never 2 consecutive reversing, and no more than n-1 diff operations. So it should look something like this: [R,D,D,D,R,D,...] (R for reverse, D for diff).

Notice that an R must be followed by a D.

Now notice the following: Say we have an array [a1, a2, a3, a4], if we do diff directly, we get [a2-a1, a3-a2, a4-a3], if we do reverse followed by diff, we get [a3-a4,a2-a3,a1-a2].

What do you notice? We got the same elements, but multiplied by -1.

It means that if doing diff eventually gives us a solution X, then doing reverse then diff should give us a solution -X.

So now we can reduce the recursion complexity a lot, because we only need to discover one of the two branches, the opposite branch is just -1 * the first one.

Thus, we can simply do the following: At each step, check the current sum, then compute the diff and do recursion to get a return R. Finally, return max(sum, abs(R)).

Once a grandmaster, always a grandmaster

I have also seen the change in his recent codes. He started to solve problems without using large template. I hope his submissions won't be skipped, MikeMirzayanov support him please.

ps: i'm his fan, so i often look on his performances/codes.

I like the variance in predictions

On the contrary, I'm surprised that the variance isn't higher, I personally would have rated H < G < E2 (unfortunately, I spent most of the contest debugging my approach for E2).

As a tester, I can finally say that I TESTED. Really good contest, I hope everyone gets positive delta.

Certified Pakistani moment

Shitty blog!

The first editorial of C is like apple falling on Newton's head.

The proof for C is this: Let $$$r$$$ be reversing, $$$d$$$ be taking difference, and $$$1$$$ be the identity operation. Then it is easy to see $$$rdr = -d$$$ and $$$r^2=1$$$. So any sequence of $$$r$$$ and $$$d$$$ can be converted to a canonical form $$$r^i d^j$$$ where $$$i\in{0,1}$$$.

And for the reverse direction, any $$$d^n$$$ can be converted to $$$-d^n$$$ via either $$$rd^nr$$$ or $$$rd^{n-1}rd$$$, depending on the parity of n.

hi

Bump! Current team: jamesbamber and me.

The problems were really great!! Thanks

I got ac without stress testing. This means it is not impossible. What's wrong?

anyone solved E1 using small to large ?

The editorial for C and D is not very clear. What does fa mean in D?

5000 when?

Please don't use symbols that are hard to understand in editorials like in E1 for example: w,dfn,nfd,pre,suf,low

I am really trying to understand the solution, but I can't really fathom it due to them.

I still don't see the contest.

No need to binary search. It can be solved with simple knapsack.

Why? I love this round. My best ever, Rank 5.

and the problems had been good.

That might be a good idea (I've planned to do that before, but usually stick to the actual order, though).

Anyway, my advise: always have the number of solves in mind, and, if you can't solve a problem, check the next one.

There are cases of contests where earlier problems worth less points are harder than later ones, and you might waste time on a harder problem if you don't notice the difference in the number of solves. Also, sometimes, a problem that's hard for most people might be easy for you, especially if it's based on a topic you're good at.

Of course, you should also remember that the number of solves might be affected by other things, like in problems with subtasks.

Treeforces (and I liked it)

I feel like the editorial for B is incomplete, especially for beginners. The most crucial part of the solution is that there never exists a part of the sequence that goes: {i...i+1 ...i... i+1} without visiting both ends of the array which allows one to show that the only optimal sequence is one in which we bounce back and forth from opposite ends of the array.

With dedication, I am at 394 days in a row and I reached CM!

Sadly i was not aware that if we resubmit a accepted qestion then the time of resubmition will be considered for that problem and my rank droped by 4000.

Thanks for the excellent contest. Problems D,E and F are all intersting!

justice for hackstar!

Guys don't be shy give me a clue al least

is E Binary Search + Dp??

damn, i missed it xD

pretty coolio (too bad i only got it bc my B failed sys tests)

We have tried our best to create an amazing problemset for all of you to enjoy. Good luck to those willing to participate.

synthborne orz

Hope you won't get skipped! Vladosiya and MikeMirzayanov can u help this guy pls, seems he is fair.

thank you so much for your insights, this will definitely help me.

I think I need to work on my strategy also along with DSA, LOL

glhf xD

hack:

Quite a stupid idea to do so. I dont want to see my account vanished if i ever log in back to this website 10 years later.

C clearly had more than expected solves in the contest. shame on these cheaters.

I somehow misread the problem B and thought we need to spend an additional second if we want to reset the clock. Does anyone know if this version of the problem is solvable?

I hope there was an option to pin a comment!

This really helped. Thanks :)

Agree! I used 1 hour to solve D and don't have time to solve F! (I can solve it in at most 40min)

D is totally SHIT.

As a participant, i hope i can gain non negative delta

As a blue plant, I totally agree with you!

Cool problems! How to solve D btw?

I hope to become CM in this contest.

@arnabmanna got the 2nd position and @1_2_3_4_5_9 got the 3rd position solving the same problems. @1_2_3_4_5_9 is already known to be a cheater. I discovered @arnabmanna 's profile randomly from a comment on codeforces blog and was quite surprised to see his contest history. In the beginning he participate in 3 div2 round and 1 div3 round. He solved 1 problem in each div2 round and 2 problems in the div3 round. He was getting ranks around 8000-10000. And then in 1 week (from 29th Sept 2024 to 6th Oct 2024) he participated in one more div2 round solving 4 problems and getting a rank of 204. I don't like accusing people without evidence but I think this is good enough evidence to conclude he was cheating. In no world can someone who was solving 1 problem in div2 suddenly solve 4 problems in 1 week time and get a rank of 200 from 8000-10000.