Всем привет!
Сейчас проходит первый тур Открытой олимпиады школьников по программированию, а уже завтра состоится второй. Олимпиаду подготовила Московская методическая комиссия, известная вам также по Московской олимпиаде школьников по программированию, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751, 775, 802, 829, 852).
Открытая олимпиада составляется из самых интересных и сложных задач, которые были предложены многочисленным коллективом наших авторов, поэтому мы решили провести рейтинговый раунд Codeforces, который состоится 09.03.2023 12:35 (Московское время) и будет основан на задачах обоих туров олимпиады. Обратите внимание на нестандартное время начала раунда. В каждом дивизионе будет предложено 7 задач и 3 часа на их решение.
В связи с этим мы просим всех участников сообщества, участвующих в соревновании, проявить уважение к себе и другим участникам соревнования и не пытаться читерить никоим образом, в частности, выясняя задачи у участников соревнования в Москве. Если вы узнали какие-либо из задач Открытой олимпиады (участвуя в ней лично, от кого-то из участников или каким-либо иным образом), пожалуйста, не пишите раунд. Участников олимпиады мы просим воздержаться от публичного обсуждения задач. Любое нарушение правил выше будет являться поводом для дисквалификации.
Задачи соревнования были придуманы и подготовлены Mangooste, Artyom123, teraqqq, Ziware, vaaven, Tikhon228, Ormlis, Kirill22, ViktorSM, isaf27, DebNatkh и DishonoredRighteous под руководством grphil и Андреевой Елены Владимировны.
Спасибо Aleks5d за координацию раунда, перевод условий и подготовку задач для второго дивизиона, а так же MikeMirzayanov за системы codeforces и polygon, который использовался при подготовке задач этой олимпиады.
Всем удачи!
Заранее сообщаем, что из-за проведения официального соревнования исходные коды других участников будут недоступны ещё час после окончания раунда.
UPD1: Обратите внимание количество задач и длительность раунда были увеличены для каждого из дивизионов.
UPD2: Большое спасибо тестерам раунда: BucketPotato, valeriu, 4qqqq, Aaeria, FedeNQ, olya.masaeva! А также тестерам основной олимпиады: Siberian, Maksim1744, sadovan, Kapt, Pechalka, alexxela12345, Be_dos, princebelkovetz, Jatana, KiruxaLight, cute_hater!
UPD3: Разбалловка:
Div.2: 500 — 750 — 1250 — 1750 — 2000 — 2500 — 3500
Div.1: 500 — 1000 — 1250 — 1750 — 2500 — 3500 — 3500
UPD4: Разбор. Приносим извинения за задержку :(
Waiting for Div. $$$0.5$$$, Div. $$$1.5$$$ round
/
Worst Contest I Have Ever Seen!..
WORST CONTEST I HAVE EVER SEEN!..
Worst Contest I Have Ever Seen!..
WORST Contest I Have Ever Seen!..
WORST Contest I Have Ever Seen!..):):):):):):):
WORST Contest I Have Ever Seen!!!!!!
Loved it
WCIHES
That's why you're blue
that's why you're color blind
that is why weirdly enough i was at peak rank performance during this contest
That's why you're blind
Why the round is showing unrated???
I'm afraid it'll be unrated for you
why
you'll see
but what is wrong with today's round
nothing's wrong
LoL now we got more depressed because of this round!
Why the cat in Kirill22's profile is looking sad? ⚫⁔⚫
I really love the contests you hold.
Sadly, this is the second time I can't participate because of the time of the contest
Why the round is showing unrated
where?
Please, change the time. Unusual for weekdays.
Usual for weekdays, but the time is good because not 22:35 :)
(But the problems...)
make 2A easy pls, so you don't scare participants away. The timing already reduced the amount of participants, and you wouldn't want to reduce that further (
bruh!
They got scared :(
[deleted]
Timings for India are just after lunch.
Perfect.
You seem to be in Australia though.
So goooood time don't need to stay up late
hello ，lampland
Hi， Duck
What is duck , i guess you are 骂 me . QWQ
a letter for a letter lol
oo,I understand it , my english is a little poor.lol
I'll be taking this contest on a plane... Hopefully it's my highest placement ever.
good luck!
Just noticed it is 3 hours long contest.
Looking forward to my first Div.1 contest on Codeforces. Hope it be good!
Now I am back to Div.2. Thanks a lot. :(
Ouch, I was looking forward to the contest but will skip the round because of the increased duration :( We need shorter rounds, they are more fun!
Increase stamina bro xD
It would be nice if duration change is not announced last minute.
Just when did it become 3-hours-and-7-problems instead of 2-hours-and-6-problems?
Really guys,
increased duration
in a non-standard time slot
announced in the last minute
is quite some combo :( .
The announcement letter, 14 hours ago, still says "2 hours duration".
Task D1G, the very first line of the statements: "Philip is very fond of tasks on the lines."
Google translate, is it you? :D
I'm from future, this contest is FST, and I will failed main test in problem 1801C
How were you so sure that you will get FST on 1801C?
Because I'm YugiHacker
Div2B is a terrible problem
Terrible problem description.
It's nice. The statement sucks
What's nice about it?
Well not really nice, but it isn't terrible either. It's an average problem
I will never take part in div1 again.
lol
Very hard contest
div2 C is very very annoying (╯°□°)╯︵ ┻━┻
It's annoying until you reach the insight: treat columns and rows separately. You can use for example first 10 bits to encode the row and the last 10 bits to encode the column. The solution is basically 1 line
a[i][j] = ((i<<10) + j). Also, writing a checker to validate solutions was simple and very helpful for me.[spoiler] https://codeforces.net/contest/1802/submission/196648450 [/spoiler] can u please tell me error in this approach I have almost used same logica as urs
Just validate your answers. See my solution (
auto Check).196626502
D was out of mind .. don't know how it crossed 1200+ submissions
Idk, it was pretty standard. If you have two things, sort by the first one, iterate over it in ascending order and select the second in a proper way using some data structure (in this case just [multi]set).
Why fixing a maximum does not work in D?
It kinda works actually. But you need to iterate over all possible maximums (for A).
Sad u and me both got FSTed. Still a little smile to get FSTed on test 69.
I don't even have this, mine is FST 70 :(
I got an FST at 71 :( Probably the dumbest mistake I could have ever made. I don't know how the hell it passed 70 other test cases.
what was your mistake? im stuck at 71 test
In D, do we need to use binary search on answer ?
No
Oh no... I didn't receive a notification that my solution in C was hacked, and I didn't notice it until the contest ended ;(
First time solved div1 A-D (div2 C-F) in contests. I've tried a dp solution for F but got WA on pretest 15. Hoping for no FST and positive delta this time!
D1A(D2C): Let's solve a stronger version of the problem: Build a matrix A with size (1<<n)*(1<<n) where A[i][j]^A[i+1][j]^A[i][j+1]^A[i+1][j+1] = 0, for all valid pairs of (i, j). When n=0, we can let A=[0] (matrix with a single element), and if we have a solution for n, then for every a[i][j], let t=a[i][j], we can replace it with 2*2 matrix [4*t, 4*t+1; 4*t+2, 4*t+3], then we get a solution for n+1. For the original problem, we can build such a matrix for n=8, and any sub-matrix of it will be a valid solution.
D1B(D2D): Let pair[i]={a[i], b[i]}, and sort it increasingly, and let suf[i] be the suffix-maximum array of b[i]. Let s1 and s2 be the set of gifts chosen from a[] and b[]. Let's consider a maximal segment [L, R] with same value of a[i], and let m1=a[L]. Then for i>R, we must put b[i] in s2, so m2>=suf[R+1]. If suf[R+1]>=m1, then when m1=a[L], all gift combinations will have abs(m1-m2)>=suf[R+1]-m1. Otherwise, we can add some value b[i] to s2 for i<L in order to increase m2. (If R-L+1>1, we can also add b[i] for L<=i<=R) Therefore, we can use a ordered set to maintain candidate values for m2, and use binary search to find the nearest to m1.
D1C(D2E): DP. First we can remove useless elements in every albums and make them strictly-increasing. Then we can let dp[i] be the maximum length of all possible strictly-increasing coolness subsequences in which the maximum value is no more than i. By checking every albums with maximum coolness i, if there's a song with coolness j, and there are k songs with coolness >=j in this album, we can get dp[i]>=dp[j-1]+k.
D1D(D2F): First because n<=800, we can calculate dist[i][j] by dijkstra for every pairs (i, j), and assume there is direct edge (i, j) if i can reach j. Then we can solve by greedy: In any optimal solution, assume the amount of coins we get by performance is w1, w2, w3..., it must be a non-decreasing sequence. So we can sort cities by w[i] (and discard cities with w[i]<w[1] because they are useless), and assume we only go to city with higher w[i], let dp[i] = the minimum number of performances we need to reach city i, remain[i] = the amount of coins we left after reach city i, we can solve the problem.
Update: I've got FST on D1B on test 70. Perhaps I'll get another negative delta this time.
Update2: Now I've fixed my solution for D1B. The keypoint for no FST: set suf[n+1]=-inf (instead 0).
Update3: Fortunately I still got little positive delta. Maybe that's because too many FSTs.
Hey can you please tell how did you solved Div2 D ?
YocyCraft: finnaly +ve delta in a div1 contest
Div1B: hold my beer
Hi YocyCraft. I had the exact same idea as you for D1D. I have no idea why my submission 207484281 is failing testcase three. I have tried to debug it for hours and also went through your code line by line to see if there is something that I have missed. I would be grateful if you could take a look at my code and point out why it is failing.
Perhaps this line is wrong:
I've got AC by change the code like this (submission:207504840):
Thanks a lot.
Very bad statements
How to solve Div1D?
Main idea is that you can "retroactively" perform in a city that you've already been to. You should choose the one with the most profit.
Create $$$n^2$$$ nodes, label each with an ordered pair $$$(i, j)$$$, meaning "you are at node $$$i$$$, and among the nodes you've been to, the one with the most profit is node $$$j$$$". If you want to move from node $$$(i_1, j_1)$$$ to $$$(i_2, j_2)$$$, and you don't have enough money, add a performance at $$$j_1$$$ until you have enough. Then dijkstra should work, with the distance being number of performances, and ties broken by number of coins.
Hey, if possible, can you please have a look at my this submission https://codeforces.net/contest/1802/submission/196657563, I did the exact same thing which you are telling but got TLE.
The
greater<>comparator is prioritizing the least number of performances first, then the least number of coins (it should be the greatest number of coins). You can fix it by inserting negative values for coins on the priority queue.AC submission
Hi, thanks for your reply. Silly mistake :( got ac now.
But I still have a doubt: why was it giving tle, basically if I am preferring lesser number of coins (with that mistake) then why would it give TLE and when I prefer more coins then it's within the TL.
Update: got the reason that actually, after a (i,j) pair is popped out of the priorioty queue, after that if we get more number of coins possibility with the same number of performances then we will again push it into the queue and it will again be processed. So tle.
Ahh that makes so much sense. Thank you.
Why is it always optimal for a node to choose a pair with the least amount of performances?
Because in an optimal strategy, the cities you perform must have increasing profits (if you perform in a city with less profit than some city $$$C$$$ you have been, why not do the performance in $$$C$$$ instead).
So if you perform in a later city you can gain more with each performance, and you should try your best to "delay" the performances to a later city. So the least amount of performances is always optimal.
I tried to create a counterexample, but eventually it helped me to understand your reply. Thanks!
How to solve Div 2. C ?? Any hint?
Look at the test cases and observe diff between a[I][j] and a[i-2][j]
You will get a hint
make every 2*2 block xorsum equals zero
I tried this but didn't got how to do it. Can you explain your solution?
one observation is that 0^1^2^3=0
so in my solution, i tend to make a matrix like this first:
and the later code is just make them different. though the impl contains some magic number, but the idea is keep the two least siginificant bits and change the higher bits. like xxxxx[00~11]
also, if we "seperate" the origin matrix every 2 rows/cols, there are some 2*2 blocks "cross" the seperator. so this case we'd better make the modification only depends on row number(in my code
(i / 2) << cnt) or col number(in my code(j / 2) * 4).and i recommend you to see jiangly's code, much simpler
UUUnmei I tried doing this but can't think of encoding in order to make all different and also still satisfy the condition.
well, you can run my code and output the result after each step and do some obsversation.
think first two rows for a start, and modify them based on coloumn number. each result col will be like (0 2)(1 3)(4 6)(5 7)(8 10)(9 11)(12 14)... in other words, add 00000,00100,01000,01100.. to every 2 coloumn respectively. this is keep the two least siginificant bits and change the higher bits. we do so for all coloumns.
then we modify by row number. the idea is same. but we have to keep not only two least siginificant bits unchange, but more. this is exactly what code
while(t<2*m) t*2, cnt++does — count the number of bits. and finally add on a proper number like(i/2)<<cntwill be okisn't all elements of the matrix being == 0 a possible answer? or am i missing something? nope thats not it i misread
you need to maximize different colors(values in matrix). All elements must be as much different as possible. Taking all zeros make it only 1color
Nope we can't make all elements 0 as the arrays needs to have as many distinct elements as it can have to achieve all the conditions
I just fixed the 1st 2*2 box as
8192 8193 8194 8195
Then I just filled the next 2nd box as 8196 8197 8198 8199
Just like this I filled the first 2 rows and then from the 2nd row considering 0 based indexing I just did a[I][j] = a[i-2][j]+8192
generate a matrix of 256*256 and fill it with natural numbers (0,1,2,3,4,5.......). then print the the first n*m matrix for each test case. Done..
What I did is
just filled the matrix with random numbers, then for every 4x4 matrix I can adjust lower right number to make xor of all 4 numbers equal to the xor of 4 numbers in the matrix that is 1 cell above it. In the end all of 4x4 matrices will have the same xor
any hint in problem C
The solution is very simple and very very short to implement (this is a hint).
Trash round.The pretest is so weak.And there are too many hacks.
Indeed.And the example of Div2 D is so weak.
I made the following two submissions on D2D, the first one sorts a vector, and the second one set. Overall time complexity should be $$$\mathcal{O}(n \log n)$$$ acc to me.
AC: https://pastebin.com/PNZMN6LW
TLE: https://pastebin.com/ZDmtxJNm
Basically, I want to know why did the second with sets TLEd ?
How to come up with div 2C other than guesswork?
Notice that in each 4x4 matrix we use 2 rows and 2 columns. And each is used twice. Solve for row and columns separately, use non-intersecting bits (for row and columns).
Hint : Binary
For every 4 elements in a quad, try and keep the XORs for every digit of the numbers to be 0.
To be more precise -> { 1100 1101 1110 1111 }
0th digit -> 0 ^ 1 ^ 0 ^ 1 = 01st digit -> 0 ^ 0 ^ 1 ^ 1 = 02nd digit -> 1 ^ 1 ^ 1 ^ 1 = 03rd digit -> 1 ^ 1 ^ 1 ^ 1 = 0Try and build upon that
How to Solve DIV2 B
mainatain a counter variable initially 0, notice that if your a[i]==1 then it means just add 1 to your counter because if you buy a new pig then u will be needing an extra cage as you dont know the gender. when a[i]==2 assume that half of them are males and other half females (any one can be assumed to be one greater in number in case counter is odd). why half of them and why not all same? because then you would be needing just (counter+1)/2 cages which is not the maximum considering the presence of 2 genders in the distribution. further, just divide the animals and calulcate the max no of cages required considering (counter+1)/2 and counter/2 males and females resp. it will turn out to be (2*counter+5)/4. update it and store the maximum of all of them.
196612008
Very bad statements ):
Bforces
The descriptions of problem Div2 A,B are terrible.
Can't agree more, I originally thought Div2 A was asking for the max/min possible votes for each position i.
The most difficult part of this round is to understand statement
Tired of reading long and unnecessary statements
like a fish
Failed to solve C again. Expert is waiting for me:(
And you got runtime error in B. Sad noise
Pain...So much pain...
I was literally pressing "submit" on F when they showed that the contest ends. How unlucky. My solution is to precompute the minimum distance between every pari of nodes. We start now from node 1 and try to go to nodes that have strictly higher weights than the current nodes. We process the nodes in increasing order of weights. For each node we try visit we compute the minimum performances needed from the current node to reach this node. If we set the weight of node n to be infinity then this will work. I am not 100% sure but my reasoning was that in an optimal path we want to do just enough performances to get us to the next node with higher weight on the path.
C The matrix in the error report after submission starts from 0! This doesn't match the question! This took me an hour!
How to solve div1F?
Let $$$\displaystyle f[i][r] = \max\left\lbrace\prod_{j=1}^{i}(\frac{1}{a_j}\lfloor\frac{a_j}{b_j}\rfloor) : \left\lceil\frac{k}{b_1b_2\cdots b_i}\right\rceil=r\right\rbrace$$$
Then we can use $$$\displaystyle f[i][r]*\frac{1}{a_{i+1}}\lfloor\frac{a_{i+1}}{b_{i+1}}\rfloor$$$ to update $$$\displaystyle f[i+1][\left\lceil\frac{r}{b_{i+1}}\right\rceil]$$$
Take notice of: There are no more than $$$2\lfloor\sqrt{n}\rfloor$$$ different numbers in $$$\displaystyle\lbrace\left\lfloor\frac{n}{1}\right\rfloor,\left\lfloor\frac{n}{2}\right\rfloor,...,\left\lfloor\frac{n}{n}\right\rfloor\rbrace$$$
And $$$\displaystyle \left\lceil\frac{n}{i}\right\rceil=\left\lfloor\frac{n+i-1}{i}\right\rfloor =\left\lfloor\frac{n-1}{i}\right\rfloor+1$$$
So all possible $$$\displaystyle r\in R=\left\lbrace\left\lfloor\frac{k-1}{i}\right\rfloor+1 \bigm| i\geq 1 \right\rbrace$$$ and $$$|R|\leq 2\lfloor\sqrt{k-1}\rfloor+1$$$
If we want to update $$$f[i+1][t+1]$$$ with $$$f[i][T+1]$$$,
it is optimal to choose the smallest $$$b_{i+1}$$$ satisfying $$$T/b_{i+1}=t$$$.
Then we can solve the problem in $$$\displaystyle O(nk^{\frac{3}{4}})$$$ time
I suppose you mean $$$f[i][r] = \max \prod\limits_{j=1}^i$$$ instead of $$$f[i][r] = \max \sum\limits_{j=1}^i$$$?
Could you explain more on the complexity? It seems to me that you're updating $$$f[i + 1][r']$$$ with $$$f[i][r]$$$ where $$$r, r' \in R$$$, so the complexity should be $$$\mathcal{O}(n \times |R|^2) = \mathcal{O}(nk)$$$. Why is it $$$\mathcal{O}(nk^\frac{3}{4})$$$?
You might say that the complexity is $$$\mathcal{O}(n \times \sqrt{k} \times (1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{k}}))$$$, but as far as I remember $$$(1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{k}}) \approx 2\sqrt{k}$$$ (reference) so it is still $$$\mathcal{O}(nk)$$$.
Update: OK I understand where I missed. The complexity is actually $$$\mathcal{O}(n \times \sqrt{k} \times (1 + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \cdots + \frac{1}{\sqrt{2\sqrt{k}}}))$$$ because there are at most $$$2\sqrt{k}$$$ elements in $$$R$$$. So the complexity is $$$n \times \sqrt{k} \times 2\sqrt{2\sqrt{k}}$$$, that is $$$nk^{\frac{3}{4}}$$$.
OK. QwQ
If we always simply enumerate all $$$r\in R$$$, it will take $$$O(|R|^2)=O(k)$$$ and get TLE.
Again, for each $$$T$$$, the number of possibly $$$t$$$ is $$$O(\sqrt{T})$$$.
If we enumerate $$$t$$$ for $$$T$$$ by the same way as enumerate $$$r$$$, we will take
$$$\displaystyle \sum_{r\in R}\sqrt{r}\leq \sum_{i=1}^{\sqrt{k}}(\sqrt{i}+\sqrt{\frac{k}{i}}) \leq 2\sum_{i=1}^{\sqrt{k}}\sqrt{\frac{k}{i}} \leq 2\int_{0}^{\sqrt{k}} \sqrt{\frac{k}{x}}\text{d}x =4\sqrt{kx}\bigm|_0^{\sqrt{k}}=4k^{\frac{3}{4}} $$$
For each i, we need to compute $$$f(i, x)$$$ for each $$$x$$$ in the form of $$$\lfloor{k-1\over j}\rfloor$$$ with a complexity $$$O(\sqrt x)$$$. You can see that the total complexity for each stage is $$$\sum_{j\leq \sqrt{k-1}} \sqrt{k-1\over j} + \sum_{j\leq \sqrt{k-1}} \sqrt j = O(k^{3/4})$$$.
like a fish
Annoying and useless statements :(
My idea for $$$D$$$:
Let $$$dist[v][s]$$$ is the minimum number of representations if we finished in vertice $$$v$$$ and the best representation cost is in vertice $$$s$$$ which is on path. Let $$$rem[v][s]$$$ is the number of coins at the end in this answer.
I do Dijkstra, since the edges values are $$$\ge 0$$$. Fix vertice $$$v$$$ and best representation cost $$$w[s]$$$. Look at neighbour $$$to$$$. If $$$w[to] > w[s]$$$, then we go to $$$s_{new} = to$$$, otherwise $$$s_{new} = s$$$. Then if $$$rem[v][s] < cost$$$ then I add $$$ceil(\frac{cost - rev[v][s]}{w[s]})$$$ to number of representations.
Answer is $$$dist[n - 1][i]$$$ for some $$$i$$$.
However, I get $$$WA19$$$. Is this idea correct?
Maybe you should also use $$$rem[v][s]$$$ in your priority queue, as a tie breaker.
Thanks, yes, this is incorrect, as it can be, that there are two pathes to some vertice with same "best representaion cost", but different edges cost, and I will propagate less $$$rem$$$ further. (Interesting, that it got wrong answer only on 19th test)
Why is the time limit in Div1C set to 1 second? What solutions did you try to cut off? Why not set 2 seconds?
Why they should? 1 second is standart time limit and there no reasons to increase it more.
div2 B English statement make me so confused
The duration increase was a total bs, 2h -> 3h is a massive change and it only happened just before the start. This was only communicated in this post, so some people could easily not see that (myself included).
Pretests for D are so weak that I don't even know if there are any pretests
I spend 30 minutes in reading problem statment of 2a.
FST.
Pain.
R.I.P. +264 Delta and 7th
upd: why +274 with 10th
Nice pretests, excellent excercise for debugging, dry-running and hacking! Makes the contest results a rng! Lots of suspension and surprises!
I remember in the old days every second contest was like this. But tbh I do not miss those times.
Please share some more problems like Div1 D.
Recent USACO Silver Moo Route II is a bit similar http://www.usaco.org/index.php?page=viewproblem2&cpid=1304
Also maybe this? https://codeforces.net/contest/59/problem/E
Maybe you can try this. https://atcoder.jp/contests/arc073/tasks/arc073_c
Sorry I mistook Div1 D for Div1 B.
Nice pretests！
Very weak pretest for D1B and D1C. Welcome to Hackforces.
f**king pretests of B.
Inappropriate time
does case like
3
1 7
4 1
9 5
intentionaly removed? I can't imagine these case doesn't appear if case was randomly created. If it was on purpose, I can't believe power of multi-testcase any more...
For D1C they didn't add pretest like
100 1 2 3I guess there were no pretests :)
My D1B solution fails on a test
2
2 4
8 3
Like, n is 2...
One more day at Codeforces!
Today is a nice day to drop out of masters...
Second time I solve Div2ABCD. Thanks for the round!
whoa noice
very bad statement for B ):
So I guess people will be hating the round because of very weak pretests in C (and also B and maybe D I guess, I'm testing right now and more than 10% of random testcases make my solution fail, so the fact that there are $$$11$$$ pretests, each with $$$t \geq 1$$$, is very strange), but that's not the case. It isn't bad that the pretests are weak, the problem is that their strength is inconsistent between rounds.
This inconsistency actually randomizes the contest, as people have to guess between "if it passed the pretests then there's no reason to look into this problem anymore" and "pretests don't mean anything and I have to decide myself on how much extra time I should spend". It's coordinator's job to keep the things right and imo this time this job was done poorly. The fact that the problems were "ready", as they were used on some olympiad, doesn't mean that there isn't much to do. You still have to check if everything fits codeforces standards.
Also, scoring distribution totally sucks, as you can see in the standings. Idk who came up with it.
No matter what it's abnormal that over half of contestants on a single page of the scoreboard get FST.
Yeah, "abnormal" is a word connected to the word "inconsistent". Many years ago it was totally fine and people were simply using different strategy, but as cf evolved this strategy was being punished -- there's usually no need to waste time if your solution passed the pretests and that's fine, the contest became more "comfortable".
Yeah, by saying more I'd start repeating myself.
I've Just submitted 1D (not participated in the contest), and got WA on test 84 (out of 85!!!). IIRC it's my record for the largest failing test so far. The test is clearly seem to be designed specifically for the type of mistake I've made (which is: sometise user-defined infinity not infinite enough). Not sure whether it is authors' generated tests, or tests from the successful hacks are added to the final test set. But if it is authors' generated, I'd move it to pretests.
In a single page of standing there are 12 FSTs on the scoreborad. How crazy it is!
The authors should be
banned, and the round should be made unratedCan pretests be stronger?
So many FST...
weak pretests
My GM :(
ccccccccorz KOT
Really disappointed in the contest dear Sir.
Hello!
In contest I passed E with 43 pretests in 3385ms.
And now I received TLE on test 30 in final test.
After contest I submitted again and passed all tests.
Could you please deal with this Ormlis MikeMirzayanov?
Thanks!
gyh bot/cf
I got TLE in F on systests and now submitted the same code and got AC :(
This blog had the similar situation before, but got many downvote. Why this comment got so many upvote?
OMG, 2 FST
WA in D because not handle the edge case(when i==n-1) correctly
WA in E because not realize the huge memory cost when multiple test cases.
sad
Forgot to add 1 line, lost 200 ranks, thanks pretest!
Here is one solution for Div2C that does not require you to think too much (unless a probability calculation is "thinking too much")
Fill the first row and column with fully random numbers in the range of $$$[0,2^{63})$$$. After that, fill the rest of the grid as $$$arr[i][j]=arr[i-1][j] \oplus arr[i-1][j-1] \oplus arr[i][j-1]$$$. Now all submatrices with size $$$2 \times 2$$$ have a XOR of $$$0$$$. Probability of a collision will be at most $$$\frac{40000}{2^{63}} \approx 4 \times 10^{-15}$$$. I believe that there is a tighter bound of the probability but I am lazy to prove it.
I was even lazier and stress test all the cases before submitting :)).
even simpler. a = [[ j ^(i<<10) for i in range(m)] for j in range(n)]
yes that is indeed simple but I am lazy to think
Happy Newyear!
I think the pretests are constructed to make participants get FSt.
And FST on Test 69 was intentionally created to tease the participants xD
Why am I getting Runtime error https://codeforces.net/contest/1802/submission/196666198 ?
Never call
erase()method of a container while using its iterator, store elements need to be erased and callerase()after iteration instead.can anyone share an intuitive idea of div2 C ...waiting for editorial
I am guessing some property of xor of consecutive number has to be utilized, couldn't figure out :(
i made xor of all elements of each square 2 x 2 equal zero
Try to assign some bits to each row and each column such that no row's bits are same as any columm's, and to get value for an element of matrix, sum up it's corresponding row's and column's values. In each 2*2 matrix, we have we have even elements corresponding to a row and a column so their individual xor becomes 0. Reason behind separating bits is that addition doesn't make any bits to get carried further. Like: $$$a_{ij} \ = \ 512 \cdot i + j$$$
I've said this before, and I'll say it again. Aleks5d is not a good coordinator.
This contest gives GreenGrape contests vibe.
FST-forces
Probably should have chosen someone who knows English. And can coordinate rounds.
I believe that contestants should just learn russian. It is statistically proven that it increases rating (and you maybe just found out why)
upd: idk why I'm downvoted that much, my comment was obviously irronical and not serious
Div2-D had a very weak pretest. I got a WA in actual testing. It was :
Which cost me +ve delta.
I have an FST, but my place became better)
Not good! The f**king English statement in B confused me a lot. I literally spent about 30-40 minutes on it just to understand the statement and, respectfully the test cases! And in C, the test cases are hilarious! Abused the fckn time + delta! Unfair and unbalanced round!!! Please consider these problems next time!!!
Kirill asks you to help her weave a very beautiful blanket, and as colorful as possible!
He gives you two integers n and m
The system test is weak too.
My solution for Div.1 D is wrong with the following input:
My output:7 Answer:3
Can't believe that it really passed system test.
lol
Bruh moment
Luckily my solution can't be hacked by this input.
A really simple solution for Div1A / Div2C:
Round up m to the next power of 2 and start each row with that number's multiples. Then, for any 2x2 square, the high-order bits in the top two and the bottom two spots cancel. Similarly, the low-order bits in the left two and the right two spots cancel. Hence every 2x2 square has xor 0.
In the square with upper-left corner 10:
The 1's — 4's bits of 10 = 01010 and 18 = 10010 cancel.
The 1's — 4's bits of 11 = 01011 and 19 = 10011 cancel.
The 8's — 16's bits of 10 = 01010 and 11 = 01011 cancel.
The 8's and 16's bits of 18 = 10010 and 19 = 10011 cancel.
Why this got TLE? Since cmp is O(1) and swap is also O(1), I think the time complexity is correct.
this has to copy construct two vector as parameters every time.
try use
const vector<int>&Oh, thanks a lot. Another question is, does copy construction affect to the time complexity or it's just a huge constant?
It just copies every time, which takes too much time and memory to copy every time. It is not a constant if I am not mistaken.
It depends on the sorting method we are using. Suppose we have $$$n - \sqrt{n}$$$ vectors of size $$$1$$$ and $$$\sqrt{n}$$$ vectors of size $$$\sqrt{n}$$$, and we are doing quicksort on them. We randomly choose one vector and compare it with all other vectors, so there is a $$$1/\sqrt{n}$$$ probability to cost $$$O(n\sqrt{n})$$$ time on this step.
Similarly we can construct a testcase to let merge sort run in $$$O(n^2)$$$. Heap sort seems to have a correct time complexity, but I am not sure.
i think it will affect to the time complexity, because the time of memory allocation must be proportional to the size. very roughly O(n) time.
we usually neglect this because problem will guarantee "the sum of n over all test case is no more than 2e5(for example)". so we can write something like
and we will just use O(2e5) memory in total, and it is kind of inevitable.
but say if you write something like
then it will certainly TLE/MLE if there are many testcases
and copy is another part of cost which won't be less than allocation
Memory usage isn't a concern here unless you do something weird with the vector like moving it to the heap. It will be deallocated when you get to the end of the scope it's declared in, so it won't ever take up more than about MAXN*sizeof(int) bytes at any one time. TLE is definitely an issue though.
Vector by copy i guess.
Maybe sort(a, a + n, [](const std::vector &x, const std::vector &y){ return x.back() < y.back(); });
This blog is getting downvoted a lot, problem A story gonna become real kekw
if my mom saw the div2B she would be disgusted and will forbid me from ever participating in codeforces rounds.
Better educational rounds than weak pretests.
Better edu rounds than weak pretests.
I solved E as we were allowed to skip any index we want but still passed the pretests x_x
my solution was failing at this case:
1 3 3 1 2
Why not put some of the corner cases in the pretest???
Codeforces Round #857 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated, Weak Samples, Weak Pretests!)
Codeforces Round #857 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated, Weak Samples, Weak Pretests, Unclear Problem Statements!)
Maybe not the worst contest as some comments mentioned, but why is E much harder than F?
By the way, the pretest of B is too weak that I and most of my classmates got FST...
Note that I participated in Div.1.
My friendlist is basically a full of systests on d1 B :clown:
The statements made me feel dyslexic
As usual, I'll give my advice about this round here :)
It is definitely what a good div2 A should be! - simple statement that anyone can understand - no math with gcd, lcm etc - there is some idea, i.e the problem is not an A+B problem
I took infinite time to solve it but my advice ISN'T correlated to my performance
I truly think this is not a great div2 B for multiple reasons, the main one being that the statement is not extremely clear and the problem doesn't feel very natural. I put this problem in the same class of problems than this. It might be that I just have bad tastes but other people disliked the B so I guess I'm globally right.
A bunch of people disliked this problem but to be honest I found it extremely cute! I think that it's a very good constructive problem, also the large number of samples help a lot so that's another good point
I faced some weird TLE issues with this problem but ended up getting AC. The problem feels a bit standard, definitely not as cute as the C. I think it is fine as a div2 D though, maybe it's just a bit too easy (but I think it's just that usually div2 D are either a bit higher or lower than the target difficulty, and maybe it's often higher so the expected difficulty I see of a div2 D might be higher than what it should be). People are complaining about the systests but I have a question to ask them: what is the point of having hacks when pretests are extremely strong ? In my opinion, it should be expected that sometimes, the pretests aren't omnipotent and you can get systestED.
UPD: someone just told me that they got systested because they didn't see that they had to buy at least one gift for each friend. It would have been nice to include this in the samples or at least to put this information in bold in the statement...
I didn't have time to try the other problems I'll post another comment when I'll upsolve them
Anyway, thanks to the authors for this round which was pretty cool!
No one is asking for an INF amount of pretests. But there are some stupid solutions that shouldn't even pass pretests.
I mean if you get WA because you guess some random stuff and implement it without having any proof, you can't complain about getting systested...
That's not what I mean obviously, why would anyone just submit random things? I mean the pretests should be able to cover details in the problem statements. In this contest it was possible to misread the problems and still pass pretests.
Yes I updated my initial comment because I learned someone has been systested on div1 B for not seeing each friend should have at least one gift...
I thought just i screwed up D in system testing.But there are many participants whose code passed pretests but failed in main testing in D.
Hope you guys make better Pretests next time. Negative Delta coming towards me. Anyhow i enjoyed the round. xD
I thought with 11 pretests for 2D my solution would surely pass but nope
Luckily my delta is still barely positive
What's up with E's statement ? At first I though they can change the prices each year, the problem will be unsolvable then unless they pulled some Chinese data structure. This problem is easiest in last 4 problems and could've got hundreds more of submission if not for the statement.
I've misunderstood it too. If each of equality constraints are independent, the problem will be unsolvable. But if the (i+1)-th constraint is laid over previous constraints, we only need to keep components by DSU (and calculate the intersection of valid price ranges when merging 2 components).
I understood the statement and came up with a solution, but that's like an hour of coding for me. "Hundreds more submissions" seems too hopeful
why are the problems not accsesible right now?
Nice contest
Is this round gonna be unrated?
Why they write in problem C bitwise exclusive or instead of bitwise xor.I was confused.
oops, I just saw it was xor not or.
LOL
The symbol of XOR was given so i didn't even read the above part XD
Why so many downvotes ?The contest was difficult but interesting (even though I could solve only first two).The setters deserve respect
Because statements are very bad and unclear. Pretests were very weak. Many people got FST, but passed pretests.
It's ok to comment to help the setters improve but I don't think that it's fine to downvote just because you got FST on d1 B/d2 D...
That's way problem setters need to control the amount of FSTs by prepare pretests carefully.
Don't forget increasing the duration by an hour right before the contest.
not able to figure out what is wrong with my div2 D solution, here's the code
Try using a multiset
Idk if i feel happy i didn't experience this clowning or sad that i didnt capitalize on the fsts for infinite delta
I don't get the downvoting. Yea there were fsts but the tasks were nice
It's sad when one person who published a post gets a negative contribution because of mistakes by the team and the coordinator in particular.
So, is the contest going to be rated? $$$5$$$ hours have passed since the end of the contest and yet no news have been published regarding the situation.
why in the world it can be unrated?
I mean, yeah, (possibly intentionally) weak pretests shouldn't be a reason to make a contest unrated, since there have already been a few rated contests with extremely weak pretests in the last couple of years (and I have a positive delta, so I want it to be rated)0). However, the rating change hasn't happened yet and that's why I'm asking it here.
My guess is that there is no rating changes, because people who can do it are busy with on-site contest. I will be very surprised if the round is declared unrated due to weak prеtests, correct me if I am wrong, but there has never been such a precedent in the history of codeforces.
rating change has happened if you click on all contests it saying unrated contests.
it shows like that on all the contests whose ratings haven't been updated
C>D>E
is this round rated?
I think yes.
But it's taking a lot of time in giving the final rating changes.
Can someone help me find out the mistake in my solution for Div1C/Div2E ? https://codeforces.net/contest/1802/submission/196698368
1 4 1 1 3 5 1 3 1 5 2 4 5
Why is it taking so long to publish the rating changes ??
I guess the round is rated !
Me: Seeing likes of this post.
All others: Taking Div2 — A problem seriously
This doubt is related to Problem div2E I have a doubt regarding how inbuilt sort function works. I actually want to sort a vector of vectors on the basis of the last element of the vector.
First I implemented an comparator function but It gave TLE on some testcase. For more details please check my submission 196715506
Then I made a map of <int,vector<vector>> and then reconstructed the vector of vectors in a sorted fashion by simply iterating over the map. For more details check my submission 196715303
The only change between both the submission is of the way I choose to sort my required vector of vectors. Can anyone explain the TLE in first case??
In advance Thanks a lot for your help :)
You have used copy construct function in your sort part:
This copy construct funcition takes O(size) time. and
std::sortmethod will compare one element with others at most O(n) times. That's a O(n^2) method. Just modify like this:constis not least but suggested. In the implement in map, the compared method takes O(1) time, either the swap method.can anyone help me find the mistake here..
verdict is: " wrong answer 42nd numbers differ — expected: '1', found: '0' " 196716275
Find any correct solution and look in the tests for example test N36. For example you have the wrong answer on that one:)
thanks
Try testcase:
Correct answer should be 1
thanks
Totally didn’t FST on Div1B / Div2D :(
Can anyone please help me out with my submission for Div2 problem D? link-https://codeforces.net/contest/1802/submission/196720503
Good problems, shit pretests.
Either the contest time or the delta rating is good. Hardly times both is good =(
Worst contest... Problems was not clear...
Worst Contest!
FSTforces
My 7k solution to 1E seems to be of medium length.
I think every contest is meaningful.Although there were many accidents in this game,we can still learn that we should solve problems more rigorously.
And the authors can still learn that they should prepare pretests more rigorously.
I took too much time to solve A and B , and thus did not submit, I thought I will give contest only if I am able to solve C and that's what I did.
Lol what a coward
trash round
Any editorial?
Proof for c: The first observation is consecutive even and odd pair of xor of numbers is equal to 2 for example (0 2) (1 3)... So the first two rows can printed like:
We observe that the xor of every 2*2 block is 0 So we want the same thing starting from the third row, well we know that the first two rows satisfies the condition, so what we can do is use the numbers in the first two rows again but with a little modification, since we should not use duplicate numbers, we can think of adding an extra leftmost set bit to all the numbers in the 1st and 2nd row and copy them down to the 3rd and 4th row. What is that extra left set bit? The maximum number in the first two rows will be (4*(m/2) + 3).
4 because with every 2 columns we increase our number by 4, for example from 0 to 4 in the first two rows and 3 because in every 2*2 sub matrix, the 4th Number is incremented by 3.
Therefore the max value with m=200 is 403.
The nearest power of two to 403 is 512 which is (1<<9). Therefore we can add 512 after every 2 rows and the numbers won't repeat, since after adding 512 again the left most bit will now be 10th and so on. The last number in the matrix will be 512*(198/2) + (403), i guess which is within the given constraints which is (1<<63).
so weak pretest.Why it pass.
pass D in last second ---> BC fst + D hacked.
I can't understand these problem statements. Especially div2B. In the past period of time, I worked very hard to do some questions, but this result is hard for me to accept. It also shows that there's something wrong with my approach. What can I do to improve? Should I do something more difficult?
Problem A in div1 is a trash problem.
why?
There may be too many people failing system test.
it is easy to fst in this contest. however, i think this can remind you that you need to code more carefully.
Exactly! why blame weak pretests? Yes problem statements would have been more clear but it's for all participants. We just need to understand it carefully and implement accordingly. That's it
Because pretests are not meant to be weak. Especially not VERY WEAK!
you should practice writing the correct code even WITHOUT ANY tests. especially there are NOT ANY "PRETESTS" FOR YOU even something WEAK when you make a project or something else. the meaning of "competition standing list" is to show who is more capable, and who is less capable. for example, A can write the correct code once while B needs to adjust his code to pass all the pretests. you can see A is more capable than B and B may FST because his code is an adjustment from the wrong code so there may be something stronger than pretest in system test. then, this problem can distinguish these two people at different levels. for another example, A can write the correct code once while C's code can only pass the pretest but not the system tests. obviously A is more capable than C and this problem can also distinguish these two people at different levels.
i didn't have an good grade. i solved div.1 A / div.2 C in 10 minutes, then i "solved" 1C/2E (i might used set incorrectly then i could not pass the pretest of 1B/2D). after a while, i found that my program will execute an operation 2e5 times in each case (the number of cases is 2e5) so i wrote a new one. unexpectedly, it TLE on test 24(system test). guess what?
i just used cin/cout without "ios::sync_with_stdio(false)". i used to think that the computer of CodeForces is fast so i can use cin/cout without it instead of scanf/printf. this contest gave me a rude awakening.
Well, we are on Codeforces, a platform for competitions WITH TESTS. Why would we practice writing code without tests during an ongoing contest?
I apologize, but I find that statement to be illogical. Writing precise code without any testing to verify it seems counterintuitive. Even in industry practices, it is customary to adopt Test-Driven Development (TDD) by writing unit tests prior to coding. This approach is widely accepted as the norm.
Where is the editorial?
Why do so many people dislike this scene
We still don't see the Editorial for the contest we attended that day...
10/10 reference
Some solutions of the editorial is FSTs.
B is Worst problem ever
still no editorial, please add
6
No Editorial??????
For div2 d I am getting TLE, but according to me it's in nlogn. can anyone help me to find the issue? here is the code 197206553
Instead of
lower_bound(b1.begin(),b1.end(),make_pair(it->first,inf));useb1.lower_bound(). Former one is O(N), latter one is O(logN).Thanks, I got it.
what FST round!
https://codeforces.net/contest/1802/submission/197224405 D2 F 救命 HELP！I'm wrong!I'm going to die！
我快死了 快救救我 wa on 35 救救孩子吧！
I got message from codeforce that my code is coinciding with other code but i havent used any online complier or got code from other place rather i tried to write in new formate which i had learnt recently what can i do to prove i didn't took code from anywhere
Hello. Why is the content unrated for me? (I think some other participants had the same question in comments). A few days ago I got my rating updated, but now it decreased back...
I think, if you remove all the pretests of div1B, the number of participants who got FSTed will be lower.