Recent actions

..

Created or updated the text

Makes sense, Thanks !

Consider splitting 100 into three slices.

When you take a cut of size 33, you split it into 3 '33' length cuts and 1 length '1' cut.

33 33 33 1, and hence you say this is suboptimal and you proceed to 34, which results in this splitting: 34 34 32 which you falsely claim optimal. (Your answer will print sigma square of this array)

However, you could have split it as 33 33 34, which is a case your code doesn't test. (Turns out this is the most optimal split)

i.e it is not optimal to always take arr[i]/mid portions along with arr[i]%mid extra. sometimes merging arr[i]%mid with another is more optimal.

Who's this cutie pie muah muah

I'd highly recommend watching this tutorial https://www.twitch.tv/errichto by errichto until they make the tutorial accessible.

Help wanted :
For problem E, I binary searched on the length and found out the maximum possible length in which the carrots may be divided. It'll be great if someone can explain me why its wrong.

https://codeforces.com/contest/1428/submission/95793574

It is still not accessible.

errorgorn I guess there is a glitch with the editorial, It says the editorial is not accessable. Please check once

It is still not accessible.

Please make the editoriala public.

It is not accessible again, can you please check?

Then tell a platform better than codeforces.

You can create a brute-force solution and Random test generate. Then you can try to give the same input for both and check their output.

I agree that problem G was less standard than E, F; I mentioned it because if G had been very original it would have made the whole contest original. Regarding "no tester solved G during contest time". I am not claiming that G is easy, in fact it is not. But originality and difficulty are almost orthogonal properties.

Regarding your proposals and comments on how to solve the issue... I simply have no opinion. I don't know whether combined rounds should be capped, or if separated rounds should be capped (or if the capping should be independent of the type of round) or if the threshold for div1 should be raised.

it wasnt public for some reason. shld be fixed now!

Is anybody able to access the editorial right now? It was available an hour ago but now when I click on the link to editorial, it says "You are not allowed to view the requested page" and redirects me to the last opened page on codeforces. Please confirm if you are facing the same problem.

Upd: Fixed Now, Thanks

Hi, thanks for the feedback!

I'm not exactly a strong contestant but I do agree largely with your comments. I'd say the problems E and F are kind of classic at higher levels, and that the contest is easier than what you'd expect from a normal div1.

About problem G, I didn't think that it was that standard when I set it. That's probably because I found the observation about 0,3,6,9 the hardest part of the question. So while the knapsack part is classic, I found the hardest part of the question the ad hoc observation at the start. Also interestingly no tester solved G during contest time (although some almost solved it).

About differentiating "original" and "classic" contests, I think it'll be a good idea. However, I'm not sure about the feasibility since usually problem setters don't have much flexibility in choosing the type of problems since we don't have enough good problems to play around with the style of the contest.

An idea is to look at the problems after they're proposed and then decide which category it falls under? Random thought I had: what if combined rounds are more of the classic type and have a rating cap. Rounds which are div1 + div2 (5/6 problems each) be more of the original type (at least for div1), and possibly harder now.

okay,thank you!!

In a week or two you will be contacted by System or someone with bold black handle to check your address and they'll provide you further info.

When will we receive the gifts?

Thank You Sir!!

Microsoft UI Automation can certainly do some nasty stuff.

The contest was very well prepared and I actually had fun competing, so thanks to the organizer. But I have a doubt.

I am not sure this kind of contests should be rated for "strong contestants" (let's say IGM). Problems E and F were quite standard, and also G was just a variation on the knapsack-problem (it was not easy to understand the details of the associated knapsack-problem, but it was pretty clear that it shall be stated as a knapsack). I think this kind of problems are a bit too standard to play a role in the rating of high-rated contestants. Once again, I am not saying that this contest was not good, I am sure it was interesting and pleasant for 99,9% of the participants and therefore it was a very good contest (clear statements, nice problems, good pretests and good tests... high-quality overall). I am wondering whether it would be better to make it clear in some way (before the round) how original the problems are (adjusting accordingly the rating range).

I am implicitly suggesting that a system similar to the AtCoder one (only AGCs are rated for strong contestants) might be beneficial also for Codeforces. In general, I feel that what I consider interesting is quite different from what a contestant with rating 1910 considers interesting (and I guess that this difference is even bigger for contestants stronger than me) so it is strange that we have exactly the same set of rated contests. The main reason is that there are many nice problems (for example E and F of this round) that are incredibly cool for a candidate master but quite standard for an IGM (in the same way that sorting an array in $$$O(n\log(n))$$$ is incredibly cool for a novice, but standard for anyone who knows a bit of stuff).

I would like to hear the opinion of some strong contestants... maybe I am the only one with this opinion (and maybe noone will ever read this late comment).

Thank you.

THANK YOU!!

if there is any 'A' before 'B' that is the only time you need to reduce 'A'. on your example you not need to reduce the last (some_number_of_A). Because that is after (some_number_of_B). You can easily check it by bruteforce.:)

I'll check if it's possible.

It was 69 when I saw it :(

People just don't listen.

Lol

Ah that's sad.

Essentially I tried to find a counterexample for my WA attempt, in which I consider the input string as "(some_number_of_B)(start with A and end with B)(some_number_of_A)". The middle part (start with A and end with B) is then reduced to contain only As or Bs, so the string is further reduced to (some_number_of_B)(some_number_of_A). I know the editorial solution is correct and simpler but struggled to find the counterexample for the idea above.

Any suggestion is really appreciated!

nope..no way bro

I'm aware, not a good topic to joke about haphazardly. Just saying there was a decent involuntary joke in there.

Okay

Does someone know how to download full test cases for a problem? My C attempt gave WA at the second test set's case #92, but couldn't see what it is.

I thought for a long time the problem B was a strong coupling component :v

Wait I thought you didn't want any unnecessary stuff

Check the previous edition of the comment.

My rating has dropped by 100, but I won the T-shirt and Thermos! Should I be pleased? Or should I be sad?

How can you call this elegant?

Congrats!

nice contest

got it, thank you

Your output is

X..X
.XX.
..XX
....

which would translate to 5 3 2 1 instead of your input.

Why does this get WA in E ?

Input
Output

Nooo I'm not. Yayy

Damn it feels good when your friend is in the list...

Thanks for the contest! Can I request a power bank instead of a bumbag? :)

Nice Job ! =)))))))

I didn't say that it's a correct solution.

Not sure what you're asking. There's a one-parameter family of test cases of the form 0 (k times), 20 (k times), 40 (k times), ..., 20*ceil(100/k) (100%k times), and variants with distributions more skewed to the one end than the other.

You're randomising the order in your "move clockwise until gap" phase to avoid a quadratic blowup when k is small. When k=1, for instance, each iteration of "move clockwise until gap" creates a new gap, giving you an expected O(mn log(mn)) moves or so. When k >= 2, though, the new gaps take a while to form. In particular, the first sqrt(n)-ish iterations won't create a new gap.

Numerically, when k=2, I get a mean of 13060 steps and a standard deviation of 2500 steps just in the "move clockwise until gap" phase.

I can imagine a tight arithmetic progression being bad too. Intuitively, random jitter shouldn't change the nature of an arithmetic progression instance too much. Why does the initial randomisation step help with this dynamic?

Congratulations to the Lucky 50!

My solution was O(n)

Imagine having the results $$$0$$$ at the beginning. Wouldn't we need $$$O(n \cdot m \cdot \log(n))$$$ moves to move the arcs to the groups (even with an optimal order)?

Why does the random shifting in the first step stop very bad things from happening WHP?

Congratulations to prize winners!

Bluetooth speaker:

List place Contest Rank Name
1 1428 1 Radewoosh
2 1428 2 Um_nik
3 1428 3 kczno1

Bumbag:

List place Contest Rank Name
4 1428 4 ecnerwala
5 1428 5 littlelittlehorse
6 1428 6 300iq
7 1428 7 DmitryGrigorev
8 1428 8 ksun48
9 1428 9 neal
10 1428 10 maroonrk

Power Bank:

List place Contest Rank Name
11 1428 11 Benq
12 1428 12 Endagorion
13 1428 13 Errichto
14 1428 14 yosupo
15 1428 15 zeronumber
16 1428 16 Medeowex
17 1428 17 Muffinhead
18 1428 18 kefaa2
19 1428 19 gs18115
20 1428 20 tfg

Thermos Mugs & Raiffeisenbank t-shirt:

List place Contest Rank Name
57 1428 57 UnstoppableChillMachine
184 1428 184 Yousef_Salama
305 1428 305 LJC00118
526 1428 525 yuusanlondon
747 1428 746 reiracofage
804 1428 804 VivekUchiha
1126 1428 1126 siddhant1
1654 1428 1654 sh_mug
1841 1428 1838 sahilshelangia
1934 1428 1934 sojisan
1967 1428 1962 snowcubes
2107 1428 2105 kansal_2106
2625 1428 2625 Igorbunov
2762 1428 2757 sandeepkumar
2885 1428 2876 aniket.nsit.2000
3063 1428 3058 ab_dtu
3165 1428 3164 the_traveler_
3424 1428 3416 akash_garg
3735 1428 3732 gxy001
3894 1428 3893 adimiclaus15
4225 1428 4224 rsgt24
4226 1428 4226 agarwala2512
4418 1428 4418 Joe_Goldberg
4532 1428 4532 hritik_456
4549 1428 4548 aky121
4761 1428 4760 suresh_babu
5010 1428 5010 joker2
5176 1428 5175 avinashrao
5241 1428 5240 sauraviiitp
5311 1428 5311 pako1609
5321 1428 5321 coder_rohit_r
5431 1428 5430 FatemaKapadia
5459 1428 5459 Vishwa_02
5589 1428 5586 evilbegin
5795 1428 5794 Mohamed_El-sayed
6020 1428 6018 Park_Min_Young
6866 1428 6866 KaoYanGou007
7055 1428 7055 Moaaz-Mahmoud
7104 1428 7104 youcef
7216 1428 7216 viven0525
7410 1428 7402 1600-1700
7644 1428 7595 brytnispiers
7861 1428 7861 B1GGersnow
7898 1428 7861 Palak_8840
8055 1428 8050 Naheed28
8131 1428 8112 biswa_990
8475 1428 8466 srinidhi21
8551 1428 8533 mr.saylander
8813 1428 8813 phoenix_1402
9351 1428 9340 Liniou

Note that it is possible that some cheaters will be removed, but we will not recompute prizes unless one of them is a cheater.

Thanks!

generally it take 3/4 hour in div1/2 contest... but in recent contest it's happening in short time. btw the rating has updated already.

Mine is pretty lightweight. https://codeforces.com/contest/1428/submission/95782858

I add characters one by one and compute contribution of all substrings ending at each character. When doing that I am interested in intervals of ones of growing lengths when looking from (current) end to beginning. There can be at most $$$O(\sqrt{n})$$$ of them, so I can iterate over all of them. This solution can be easily changed into linear, but it was easier to leave it as it is and it was fast enough.

How much time does it take to update ratings?

You should always follow "True story" with "Yeah yeah"

we've had fast editorials in most recent contests. It's a great improvement for codeforces i think!

The press charges is an involuntary good joke though. Because battery.

I did a O($$$n^{\frac{3}{2}}$$$) solution but it did not pass test 48 :/ can you share your submission please?

fun fact: When code forces ran your solution during contests on systests, it gave "runtime error on test case 21" from too many queries.

In the end, it ended with 14848/15000 queries, what a clutch rng!

Here's my solution to H:

Firstly for each ring choose a random number from $$$[-20, 20]$$$ and move it by such shift to make sure that nothing very bad will happen.

Now consider the rings in random order. Let's take some ring $$$i$$$. Move it clockwise and stop and the moment when the result decreases for the first time. After this, shift this ring counter-clockwise by one.

After such a phase all arcs are grouped. By grouped I mean that every two arcs either share their exact position or don't touch each other at all and the size of each group is at least $$$2$$$.

The number of groups is ofc $$$\leq 50$$$, but it'll be a bit less in average. Now it'd be nice to discover how the indexes are grouped. To do this, initialize a set of groups, initialy empty and consider all the rings (again in random order). When we consider ring $$$i$$$, then move it by one clockwise. Nextly, loop over all the existing groups, and for each of them take its representative and move it once clockwise and once counter-clockwise. It's possible to know to which group ring $$$i$$$ belongs (or if it's in a new group). Then shift ring $$$i$$$ counter-clockwise by one to fix the situation.

So we know how the rings are grouped, but we need to know their order (and distances). Take one group and it's representative. Let's move it clockwise and stop when it bumps into another group. In this moment iterate over all other groups, for each of them take one representative, move it once counter-clockwise and once clockwise. It's possible to know if we bumped into this group (and ofc we know the travelled distance). Then move the ring back to its group.

After this we know everything.

Sad life :(

Enjoyed This Round clear problems statements !!

The most important question for many of the CF users who gave round today. xd

As a human, I'm going to die without becoming a Grandmaster :"

Please don't upvote the above comment. It is aesthetically pleasing as of now.

I did it's WA it seemed correct to me Idk why it's wrong but I'm not that good to solve E so it's not a surprise

Passing pretests during the contest does not mean it is correct. Therefore, sometimes a contestant may want to resubmit their solution which the pretests may not have caught their bug. This is why the rules are designed this way.

where we can know who is winner ?

Was log^2 with segtree intended to pass in F? I got TLE on recursive version and accepted (<500ms) on iterative one. If log^2 complexity can easily pass why not set the limit to 4s?

u can do it now

I solved F with normal segment tree though. The idea is to iterate l from high to low and maintain the lowest r such that f(l,r)>=k for each k.

Submission: 95806181

When your last attempt of saving your rating in last 10 seconds of contest got rejected by a semicolon

(It got accepted after fixing the semicolon)

check it after the testing

i have no idea how the ppl getting shirts are selected

nah it's probably wrong I won't suicide unluckily for you

Go ahead, don't hesitate.

At least you would stop crying in the comments.

My solution works (982ms), so I enjoyed the contest :)

Thanks!

errorgorn, will there be a list of t-shirt recipients?

Thanks for the contest. :)

I really liked problem D!

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

Video Editorial of all Problems

Even $$$O(n^{\frac32})$$$ works! On worst case locally it works 0.2s for me, on systests it worked in 62ms ;)

n = 2, k = 2, array = {1, 9}, your answer : 50, the real answer 82.

wrong answer on pretest 2

why kosaraju algorithm gave TLE on the 2nd question????????

You can match a 3 with a 2.

well you can match the number 3 with 3 type of things. 1) the ones who is not match with any 2(free one). 2) all of the columns with number 2 -> just put a higher mark on top of the last one and another one with the same height. 3) with another 3.

Great round!!! Fun Fun Fun!

P.S. Problem D 122+ system tests? O_o

Yes totally makes sense.. I know the other solution using priority_queue (didn't click during contest tho) but i couldn't find why this wouldn't work... bad dayyyy.. But good round!! Thanks for the help!! :D

In fact, you can set them to 0 using brute force.

It's also a $$$O(n \log n)$$$ solution, but i don't know if it will FST.

Let's consider you converted the first part into x1 part, the second one into the x2 part ...

find out how much you can reduce from the final answer if you cut the i_th part another time(convert it from x_i part to x_i + 1 part)

put the values inside a priority queue and do the best option each time

4 4 1 1 1 9 will give WA in your code...but my submission gives right value for that too

https://www.youtube.com/watch?v=g22-5e5xAGA

Watch Video Editorial of all problems

Also do watch , cp experiences of IIT Madras students

https://www.youtube.com/watch?v=8n12sCm0VUI