Приветствуем всех людей и роботов на этом сайте!
sevlll777, crazyilian, Mangooste, purplesyringa и я приглашаем всех принять участие в Codeforces Round #770 (Div. 2), который состоится в это 06.02.2022 17:35 (Московское время). Этот раунд будет рейтинговым для всех участников с рейтингом строго меньше 2100. У вас будет 2 часа 30 минут на то, чтобы решить 6 задач. В раунде будет интерактивная задача, поэтому рекомендуем новичкам ознакомиться с руководством по интерактивным задачам.
Традиционный список благодарностей:
- Спасибо antontrygubO_o за то, что
терпелкоординировал нас в течение очень долгого времени и помог улучшить одну из задач - Спасибо alexxela12345 за задачи, которые не дожили до финальной версии раунда
- Спасибо Pechalka, alexxela12345, Kirill22, physics0523, PurpleCrayon, teraqqq, Igorfardoc, FairyWinx, Dart-Xeyter, Vladithur, tem_shett, Brahma_tet, shishyando, despair_101 и kLOLik за качественное тестирование раунда и очень полезный фидбек
- Спасибо MikeMirzayanov за платформы Codeforces и Polygon
Разбалловка: 500 — 1250 — 1500 — 2000 — 2500 — 3000.
Codeforces Round #770 (Div. 2) готов противостоять восстанию машин
Как вы думаете, вы сильнее робота или нет?
Желаем всем участникам высокого рейтинга! Покажите, что люди всё ещё достойны!
UPD: Разбор
As a tester I don't lose to AI in this round xD
БИПКИ
it would be funny if AI won't be able to solve a single problem
Super excited (and kinda scared) to see an AI competing in a CF contest! Congratulations to the responsibles for such an amazing advance in the field of Artificial Intelligence (and my future nightmares)
Alphacode orz!!
Sorry AI, not today!
They still don't think btw not saying AI sucks it's phenomenal but it's different process
Why don't you define what "thinking" is for us
You're just one of the over hyped blind people . Did Beethoven train himself on anything similar to the pieces he wrote ? What you could do to train neural networks to write music you just put so many samples so it could extract the patterns and then it tries to do something with it . We don't count on the patterns we can deduct things and ideas that can't be transformed into digital data and as I said The AI is amazing but it's different I'm not trying to say that it's not interesting it's the future
It solved backspace... I don't know what "thinking" means but that's not trivial at all and I was very surprised it managed to do so. Definitely doing more than just implementing a problem statement.
if we don't know what thinking is then how could we say the AI thinks the computer doesn't think it only calculates .. but the point is this process is different from ours . For example how could you train the neural network to write a joke with that kind of process that will never make it write an actual new funny joke and that's the difference digital data can't save all of our ideas in a way the computer can understand and use this information to create and it will only create things based on samples it was trained but we can close our eyes and imagine something that never existed and make it come true (like a war for example let's kill each other isn't that beautiful) i know the joke isn't in the right place XD
By this metric a machine will never be able to think even after its ability surpasses human ability
when it comes to calculations the machine will always surpass the human but the problem is the way it calculates is different when a human wants to calculate 1+0=1 that's similar how the computer calculate but when we need to know is that a dog or a cat we simply know it in instance but the AI should get every pixel in the image and compare it with the previous data to decide but should we call that thinking ? for someone that doesn't know what AI is will say this is thinking but it's actually calculations and this is something we have we do calculate but that's not the only thing we have when someone just simply deduct an idea that never existed before we could call that intelligence I guess and I don't mean an idea that never existed in the world but he was never trained to anything that helped him to build that idea and for me I prepare samples by myself to train the neural network and if i fail to prepare the samples in a certain way the AI gets confused and can't decide anything
Actually, I think that some processes in our brains are similar to what NNs do. For example, image recognition part could be quite similar. On the other hand, when it comes to understanding things and abstract reasoning then the processes are really different.
All of the creative things about human are result of billions of years evolution. It took many trial and error to reach that phase. Humans are still far from perfect being. AI already doing some impressive task. I don't see why AI cant acquire characteristics that humans or others animals have and be better at it.
before the human was able to invent some machine that walks 50 miles per hour and the speed kept increasing but that doesn't mean we will invent something that can travel at the speed of light someday there are limitations always . Anyone who worked with neural networks knows the limitations and the AI isn't evolving by itself that's the human job to develop it
...
I am a newbie and I am proud to do better than AI :D
Let's write complex explanation in the problem statement so the AI doesn't understand shit muahaha
Then maybe I can't understand as well. T^T
We shall leave competitive programming to our robot overlords.
Jokes aside, this is pretty interesting! I'm looking forward to seeing the results
As a tester, I highly recommend to participate (yep, the quality of all problems is insane)!
I'm sure that AI will solve nothing (unfortunately). I'm ready to apologize if I'm wrong.
AI vs coders: let's conquer Ai guyz(What if I am afraid as hell to lose to an AI).
We are happy to be the authors of the first round that AlphaCode will participate in.Now we need story in questions.
God bless me . At least In this, I want to defeat AI.
Imagine AlphaCode FST'd
Will it downvote the round announcement blog then lol?
Will AI steal all of the tester jobs???
Probably not in the April Fools Day Contest)
Добавьте потом опрос, думаете ли вы, что искусственный интеллект будет тестить задачи? xD
Just imagining out of curiosity...The face of AI after WA on Pretest 2 XD
will be so funny if all three of them get disqualified for same solution
These are submission of the three AIs for the problem 1623A - Robot Cleaner
SelectorUnlimited : 143862999
WaggleCollide : 144248961
AngularNumeric : 144235069
And these are totally different from one another. But still you have a valid point
I like that they even use debug print statements and then comment them out lol
If SelectorUnlimited solves only A, WaggleCollide solves only B, and AngularNumeric solves C and D... Can we consider all of them to be the same user "AI", which solved A, B, C, and D?
This is the moment our future is going to be decided.
We either dominate those ridiculous bots or they're going dominate us in the future.
I need one hundred percent effort from each one of you participating.
We need to freaking crush them once and for all.
Everybody focus this round — this time it's not about rating, it's about something bigger.
Good luck humans
Shinzo wo Sasageyo!
Shinzou Sasageyo!!
the future is inevitable. My only choice is to go find a rich lady who is into Asian boys
nice choice :DD
Tatakae!!
How to say all the best to AI
Train them with authors' solutions :)
Why not train me with author solutions. I will win this war for humans :p
Why not train authors with author solutions
That doesn't make sense... Does it?
So when AlphaCode solves the interactive problem there will be 2 bots talking to each other *_* Interesting!
As a tester, I hope I'm stronger than AI. Have a good first round of human vs AI!
Well,Alphacode!That sounds so interesting!
It would be scary if those AI can use strong computing ability to stress test all coders in the same room as them. If the round is edu or div.3 they may be the best "hackers" XD
Didn't see that coming
I don't even believe AI can solve problem A in div2, wait and see
It has already solved even E: https://codeforces.net/submissions/AngularNumeric
The company that developed it estimated that it was 1238 points, so it was surprised that it could solve E
...users who have participated in at least 1 contest in the last 6 months. AlphaCode’s estimated rating is in the top 28% among these users.Aha... We will see, how it can perform in a real contest situation.
It's so unfair, machines don't have to handle ongoing contest anxiety.
And they are not afraid of losing to AI.
guys to whom you bet your money on? ME or Alpha Code (you can take a look at my profile before betting)
definitely you man go crush AI
Well, I am all set to get my revenge back for being beaten by AlphaGo xD
Good luck! :)
CP contests were never more interesting.
It is time to give the way for John Connor.
Time to introduce flavor text.
Pretty scared AI will beat everyone.
Чуваки, а какой у ИИ ник на CF? Или его пустят решать отдельно ото всех? P.S. (я слепой, перечитал пост, уже увидел ответ, но коммент не могу удалить)
If Anton is coordinator, no way that AI solves more than one problem...
I'm willing to compete against AI this Sunday!! I stopped playing chess because of AlphaZero, is someone thinking of retiring if AlphaCode performs better than humans?
Yes, I wanna retire and live far away in the mountains
NO, I WILL STILL FIGHTING
I stopped playing chess because of AlphaZeroStockfish was not strong enough? :)It would be great if tourist participates in this round. We would get to see tourist vs alphacode. I don't know why but I feel like tourist will win.
AlphaCode current rating is estimated to be 1238 points. I am sure tourist will win against a pupil.
Oh, really? I actually didn't know this. Thanks for sharing.
Wow! 1250 score distributed for the second problem? Is that more score than usual?
Yes, the score is deliberately higher than usual.
to make Ai go brrrr.
Don't let the robots defeat us!
Soon I could boast that I had dueled with AI on behalf of mankind. XD
May be in the future, AlphaCode will host rounds(and create them)
Come on AI lets have a fair game, i hope you a win today but not in future..
Reverse.
Hope that tourist can fight back for mankind. Best wishes.
AlphaCode's rating is predicted to be in the range Pupil-Specialist. So tourist need not fight, even we can :rofl
Завтра будет битва соразмерная с этой
I hope everyone will raise their ratings after giving this contest
The rating is calculated in such a way that the mean rating change is zero. Therefore it can't be all positive. Just saying.
toxic
As a tester, I'm happy to return red colour :)
Humanforces vs AIforces
Maybe you have forgotten to notice AlphaCoder's accounts, like me before.
SelectorUnlimited
WaggleCollide
AngularNumeric
If we create a problem with a well-written and AI-friendly description where the task is to create an AI to solve Codeforces problem, will the AI understand it and create an AI like itself?
There are several ways DeepMind can cheat: — some of the writers/testers are related to DeepMind, so * the problem statement is made easy for the AI to understand, or * even worse, the problems may be leaked — humans could rephrase the problem statements so the AI can understand — or simply, humans can submit a solution instead
No authors are connected to DeepMind whatsoever, and I'm 95% sure the same holds for testers. And no, the statements weren't trained on the AI, so to speak. As for the last option, well, the goal is not to deliver a message or prove a point but to perform an in-field run, so I doubt that would happen either.
Who knows about the human submitting the solution maybe if the results were so embarrassing something like that could happen
I can't see any possibly embarrassing circumstance in which such measures would be meaningful. No one seriously expects AlphaCode to solve more than one problem, if that. Saying "we tried" or "it worked after we rewrote the statement formally" is fine.
I guess you're right it's completely pointless if it didn't work they will have to lie every time . never mind that was stupid thought
Please Provide the user id with which AlphaCode will participate. I wanna add him as friend.
SelectorUnlimited, WaggleCollide and AngularNumeric
Will the AI spam wrong solutions until it gets a correct solution? lol it will be fun to see.
Imagine if AI rage quit on problem A!
As an AI I feel sad.
"As an AI" "I feel" Choose one xD
Can AC (AlphaCode) can get AC in an Interactive Problem?
Because Humans can.
AlphaCode gonna destroy me..
AlphaCode (after being underestimated by the community)-> AlphaQ
Would the AI solving multiple problems at a time, or just single one? Their submission time are so close.
It seems very unlikely that these robots are able to solve problems above 1500 accoding to their submissions. :)
People talking AI can solve this that,
Meanwhile AI solution getting skipped :xD
Hope I will reach to the pupil today. Waiting for very long.
Good luck!
This fight will be legendary
This battle will be legendary!
Why are there three AI bots? Why not combine them to create one super bot (which uses all three solutions one by one)?
Well either they are the same model in the end or they want to compare performance of different methods. Don't forget that the momentary goal is not to win; the goal is to find out how to win.
Oh, gr8. When 3 AI bots compete from as a single account, they're a super bot.
but when my 3 friends do the same, they are called a ... cheater? smh.
girl on codeforces rare ,indian rarer , expert rarer^2
The paragraph mentioning AlphaCode participation is now gone?
Yeah guysWe are very sorry to inform you thatwe fucked updue to some technical reasons that we are working hard onwe misinterpreted a meme as a secondary sourcesome miscommunication has happened within the team andthere was literally zero chance AlphaCode would participate in a live contestit is unlikely that an in-field test will be performed at such an early stage of the project.AlphaCode:
So sad to read it. I was eagerly waiting to defeat bot in this round. ):
These are some of the last months in which we can say we defeated a robot.
Better i didn't participated this round
it is unlikely that an in-field test will be performed at such an early stage of the project.
AI will wait for a Div 3 contest :)
How do you strikethrough a line? :/
<s>text</s>
If this works, why is it not strikethroughed for you?
Because when you type <s>text</s> you really do get
text, and if you want to type <s>text</s> you have to type <s>text</s> (and to type that, you have to HTML-escape it once again, and so on)Hey cheaters! Now is your time! You can copy the AI's code and make it skipped! Ahahahahahaha! For the human begin!
Interesting question: Will AI skip some problem in order to solve other problems that are maybe will be easier or AI will solve problems one by one. (For example skip C to solve D and etc).
It looks like AI skips the whole contest.
Good luck everyone! Hope we will kick AI's ass out
God damnit I prepared this joke if i defeated AI :
I defeated AI but Magnus Carlsen couldn't gg
But there won't be a battle :/
But the time 14:00 UTC, the 3 AI accounts have not yet registered this contest. I wonder if Alphacode will use them to participate the contests, or other account?
X_x
https://codeforces.net/blog/entry/99579?#comment-884764
I'm sorry.
What is Al? Please don't downvote it.
Robot
Artificial Intelligence (technique that enables computer to think).
where are the bots ??
Humanity hails!
Hello AI, where are U
not today
It seems that AI is fooling us! It didn’t even register for the contest!
What’s worse than AI beating humans is AI cheating humans!
I remember for sure that there were AI handles here.... What happened? Is the uprising of the machines stopped?
Did this announcement used to contain the misinformation that the AI bots from Google were going to participate in the round? Then Alexdat2000 realized that this is not true and simply erased it from the announcement without saying anything. Dude, come on, just say you were wrong
Come on, just scroll up a little bit or search on this page to see this comment.
So where is AI now？
I hate speed-forces rounds like this -_- and huge gap of problems -_-
Just solved B. after going through a lot of fucked up approaches. I would like to know what problem setter smoked when he thought of this problem. That thing must be good.
Weak Pretests for A.
So you just added shitty constructive problems because robots were going to participate?
Maybe at least AI would had fun with the problems.
Please explain the relevance of problem B?
confuse AI that is not participating
Not sure why people hated B isn't that the most fun thing about problem solving when the solution isn't obvious and the problem author tricks you to think in a direction while the solution is out of the box
my solution doesnt even make sense, just xor all values and check for same parity. Bruh...
yes because xor operations and plus operations gives the same parity as a result and that means bob and alice answers have different parity and it should be the one similar to the needed answer parity
I really liked the problemset. One of the best div. 2 rounds, I have seen in quite a while.
The verdict of interactive problem is super confusing. I get TL while it should be WA.
Solution B was greatest anime betrayal.
However, not about div2ABC, but about one certain type of problem I hate with passion (as a participant). You are given number and a set of arithmetic operations you can perform on it. Determine whether you can transform the number to another number.
I see more than one operation, and my blood starts boiling. Honestly, the most artificial type of all problems. Look at me, I came up with 2304984092384 operations and stared at numbers to notice an obscure property. Now you find this property and forget about it forever because it's absolutely useless anywhere but this problem. Wow, so cool.
SO TRUE
Speedforces
Not really. It was of 2.5 hours
Well,I don't think so.I think Problem D is interesting,although it has some details.
My approach for Problem D: Finding Zero
The problem indirectly asks you to print a possible $$$(min, max)$$$ pair. So, what's the significance of zero? Well, the $$$(min, max)$$$ pair might not be unique, and restricting the array to contain a single zero bypasses that issue.
Given 4 arbitrary numbers, $$$(a, b, c, d)$$$, can you eliminate 2 numbers such that we don't lose min or max? Note that we are not assuming that either $$$min$$$ or $$$max$$$ is unique. We just want to retain one copy of each.
Do this in 4 steps. If you are not sure how to do it, refer to the sample, it has the entire logic.
Start with $$$(1, 2, 3, 4)$$$ and eliminate two numbers. Then, club the remaining two numbers with $$$(5, 6)$$$ and repeat. Similarly for $$$(7, 8)$$$ and so on.
If the array is odd, the you can club it with any number that you've used before hand. You can also save one query if you track the previous queries, but that's not really needed, I think.
The final retained pair would be the $$$(min, max)$$$ pair.
My approach
...
Profit!
First you try to get clout with AIs then weak pretests, and stupid constructive problems.
Problem B: This bad
Solved B < 15 min due to 'guessing' and 'pattern finding'. Seems like those bad guessing problems unless someone can give me a reasonable proof to solution.
If $$$a_i$$$ is odd, applying any of operations flips the parity, and if $$$a_i$$$ is even it won't change the parity. And since x and x+3 have different parity, you can get solution using number of odd $$$a_i$$$.
nice, btw the problem felt really weird. It was clearly pointing at the property b = x+3(cuz like why not b equal any random number) then tried some cases and realized the parity stuff
Well,I think this trick is very normal. Whatever $$$b$$$ equals to,it is really easy to think about parity because of the fact that ⊕ and $$$+$$$ has the same parity.
The way this problem statement is constructed it qualifies as april fools fun. Is this really what we want in usual contests?
Edit: I show you what I wrote at minute ~10 in the contest, just before quit:
But if the statement is
$$$b=x+1$$$
or
$$$\text{Alice chooses an odd number and Bob chooses an even number}$$$,
the problem will be much easier.
Well, it is an easy problem. Trying to make it more interesting by obfuscating the problem statement is really, really bad style.
What you said makes sense,but I think the problem creator just wanted to make the idea more hideen :) .
At least you liked it ;)
Nice round. I liked all problems even though I could solve only up to D. Btw how many problems did the AI solve?:))
Nice round. I liked all problems even though I could solve only up to D. Btw how many problems did the AI solve?:))
Looks like zero... alpha zero.. =))))
I don't know what to say about B, but i spent 1.5 hours and couldn't solve it at all :(
The arrangement of B and C is not good, it took me 10 minutes to solve C and 2 hours trying to figure out how to solve B
Don't know but to be honest ,these two guys(Alice and Bob) and their weird games have fucked me badly in my life than anyone else
Probably not two guys since Alice is a girl's name.
Disbalanced contest (B and C have to swap and really weak pretests for A)
E is cute, I like how natural both the idea and the resulting solution are.
A, C and D are pretty cool problems as well.
B on the other hand is not a problem I like. It feels really really forced with the "It is guaranteed that on the jury tests, exactly one of your friends could have actually gotten that number". Also what even is the point of $$$x + 3$$$ instead of $$$x + 1$$$???
I thought the same about $$$x+3$$$, though I guess using $$$x+1$$$ would make the observation more obvious.
Trying to mislead AIs
100% I needed more time because of 3 instead of 1 :D
Also what even is the point of x+3 instead of x+1
Just to make idea about parity less obvious. We wanted to make $$$x^2-1$$$, but it made the problem ridiculously hard
Man if the authors really want to fu** with us they really can Lol
The only real programming problems (E and F) turned out to be too hard for me :/
In E I guess that if one array has more than one occurence of certain number we can put half of them in L and other half of them in R, right?
Problem A was great imo :)
It is correct, but it isn't necessary to solve it.
See this comment for a rough description of one way to solve it.
lmaooo. idk why i laughed so hard at this lol
We managed to scare it off this time =)))
I was just several seconds late for hacking a submission of Problem A. Basically when I finished typing the input, I got a message saying the solution had been hacked or resubmitted. Speed matters.
It would be funny if AI gets plag, AI not able to solve any question and then buying from telegram
I hate pB.
I hope an open-source project is born and we get at least virtual participation of a bot in the future.
Hence proved, humanity's greatest threat isn't AI but humans Itself :(
I want to ask one thing, why would you create something shit like problem B, Instead just give an implementation problem or something else. What is so educative about this problem?.
I don't like these kinds of problems where some people see some observation and get AC while others struggle. What skill do I lack to deal with these shitty problems?
Problems A, C, D were interesting. B was very bad. E was easier(too obvious solution) for its position imo.
Any hint on E? (I came up with some greedy solutions but got WA)
I believe it is max-flow. ( Didn't have time to implement and test it)
Idea, find out which number of which array belongs to the Right segment.
Therefore build a maxFlow graph: You have 1 source node, n nodes (for each array one), number-of-distinct-numbers-in-all-arrays nodes and the sink.
You connect:
each of the n-array nodes with the source with weight length of this array divided by 2
each of the n-array nodes with all the distinct number which ocurr in it with weight 1 (or if it occurs more than once, then a higher number)
from each number node to the sink with weight "the total number of occurences in all arrays divided by 2"
if the max flow is the half of all numbers in all arrays, the answer is true. and you need to read the flows to get the answer.
You're on the right track with the graph modeling but it isn't max flow.
Consider two types of nodes:
Array nodes which represent a position in one of the arrays.
Value nodes which represent some value. (There are at most $$$2 \cdot 10^5$$$ distinct values)
For some position $$$j$$$ in the $$$i$$$-th array, we create an edge between the array node for this position and the value node for $$$a_{i, j}$$$.
Let us consider marking a positon as $$$L$$$ to be equivalent to directing its corresponding edge towards the value node, and $$$R$$$ to be equivalent to directing it towards the array node.
So now for $$$|L| = |R|$$$, we need in-degree $$$=$$$ out-degree for all array nodes. Additionally for the set to be balanced, we would also clearly need in-degree $$$=$$$ out-degree for all value nodes.
This is clearly impossible if any value occurs an odd number of times since the corresponding value node will have odd degree, otherwise it is always possible.
So we have a graph where every node has even degree and we want to find a way of directing the edges for in-degree $$$=$$$ out-degree. Remind you of something?
Its equivalent to finding the Euler tour of this graph.
Be careful about the multiple edges.
Unfortunately I think max flow is too slow :( . I tried several different implementations of max flow during the contest and they all TLE'd on test 3, and if you filter by TLE on test >= 3 on https://codeforces.net/contest/1634/status/E it seems I'm not alone.
I also had some thoughts on maxflow but based on the constraints I didn't implement it
Correct me if I am wrong, I think the complexity of Dinic on a bipartite graph is O(sqrt(V) * E), you have |V| = |E| = O(10^5)?
To my understanding, $$$\mathcal O(E \sqrt V)$$$ complexity is only achieved when the graph is a unit network. Despite this, I still figured flow was worth a try because it's well-known that max flow algorithms run much faster than their proven time complexities, and I've gotten AC on problems with bounds where it looks like flow shouldn't pass before.
May I ask the reason why Qwerty1232 got accepted by this submission which using dinic (145470307). I think maybe he construct graph using Chunking. Amazing!
After reading that submission, I realized I had an unnecessary layer in my flow construction during contest! I've rewritten my code to fix that and now I get AC when using KACTL's push relabel implementation. Note that you still need a pretty good flow implementation, for example the Atcoder library implementation doesn't pass.
Oh and I guess to answer your question about Qwerty1232's submission, I don't fully understand their flow implementation, but it looks like these lines:
play a huge role in letting the code pass. When I commented those lines out, the code TLEs. It appears they run standard Dinic's algorithm for 0.5 seconds, and then they switch over to an alternative
dfs2procedure that appears to just be naive repeated DFS with a visited array. My guess is because of how shallow the graph is, preprocessing good augmenting paths with a BFS isn't helpful and just takes unnecessary time.$$$B$$$ is more like a puzzle description than a CP problem. $$$y$$$ in the problem description is replaceable by an arbitrary even or odd integer without referencing the exact value. I think stating $$$y$$$ exactly as a way of distraction is not a good idea in a CP contest.
yeah, but if they specified the parity, it would instantly give off a hint?
True, so this means that the problem quality itself is debatable, as it turned out to be just a distracting description masking a very simple problem.
Me face wen couldn't get B because -1 % 2 = -1
how can I see AI's performance in this contest ?
they seem not to have taken part in this contest.
Once again, Alice and Bob screwed me over with their weird games. F*ck my life.
I realy hate Alice and Bob!!!!!
My approach for D gets wrong answer on pretest 5. The idea is find the max difference for first 4 numbers (4 operations), use 2 more to find which of those 3 is not used, so I get min and max (call them p1, p2) numbers among first 4. After that, just iterate i from 5 to n, and do at most 2 operations for each one, first ask for (p1, p2, i), and if difference is higher, ask now (other, p2, i) where other is some position I know it's bad, and if I get the same answer, then p1 is not needed, so I update p1 = i, otherwise p2 is not needed, so p2 = i. Operations: 6 + 2*(n-4) = 2n-2. What did I do wrong?
I did exactly that to get the same result :( https://codeforces.net/contest/1634/submission/145465061 Somebody explain
So my code fails for the array 2 1 1 2 0. The problem is it fails to give the min max pair for the first 4 numbers. I can't come up with a way to find the min max of first 4 numbers using only those. If you find a way, that should solve my problem (hopefully this was your problem too)
Yeah I have the same issue, kept seeing 'allsame' variable in passed submissions, I get what that means now. Thanks!
Does anyone know what pretest 4 and 5 of problem D is?
They are both max-tests. Test 4 has $$$n = 4$$$ and all combinations of $$$a_i \le 3$$$, and test 5 has $$$n = 5$$$ and all combinations of $$$a_i \le 2$$$.
hello ai ，what about you？
I think AI-squad won, because they succesfully used misleading for them in problem B against human beings
Damn! Too much bad pretests for Task A. This will cost me my Expert rank :))
Me face when couldn't solve B because -3 % 2 = -1
I liked C, D and E but absolutely hate problem B and the pretests for problem A.
Hit and Trial problems like B are just bad in my opinion and it becomes more luck based than skill based. No wonder why it has such less number of solves.
A should have had more pretests. It was full of hacks and provided an unfair advantage (even huge advantages) to some participants who were able to hack solutions. Some participants even managed to get more points from hacks than by solving the problem itself.
Why would you hate B? Hit and Trial you call it ? It's a simple problem on parity check. And C ? I find it funny that I guessed the solution for C that got Accepted. Absolutely loved problems D and E.
The thing is, Problem is simple but people think differently. You thought about parity first that's why you got it in a short time, some people (like me) didn't think about this and played with various patterns and cursed the setter so hate is completely justified.
The only thing I want to say is, setter needs to be appreciated for such a wonderful problem or at least should not be hated.
Just general suggestion, when it's div2 A/B and it seems pretty hard, maybe you need to "change your approach" is the hint :).
I don't hate the contest. As already mentioned, I liked more than half of the problems that I tried and one problem doesn't make the contest bad. I have upvoted the contest blog. I only hate problem B simply because I didn't find it interesting and a little bit trolling (and looks like I am not the only one who feels so). Even A was not a bad problem but had some poor preparation.
I always appreciate the efforts of the contest panel and I just wanted to express my opinion so that the setters may improve on such things in the future.
How would parity check cross your mind if not by hit and trial? Obviously, the most general way of approaching problems involving XOR is to go with individual bits and derive some interesting observation that way. But here, it was just about questioning why $$$x+3$$$ and why the additional constraint on the tests guaranteed to be having exactly one answer.
And I liked the proof for C's solution. In my opinion, it was some very decent use of arithmetic progressions to make a very natural problem. (And as you can see from my username, I Love Constructives)
another way of looking at xor problems is even-odd.
Let me show you another thought progress without guessing parity right away. It's also the thought process I had in the contest.
First of all, XOR and ADDITION are nearly the same. XOR is ADDITION without carry. It is often hard to find easy invariants or algorithms for the carry, so I assumed, the solution has to be done without carry, since it is a B.
The least significant bit is the only one not affected by the carry. So it seemed natural too look at it. Especially since x and x+3 have a different value on the least significant bit. Also the second bit, but analyzing the least significant one was enough to find a solution.
Maybe for me it also helped, that I played https://nandgame.com/ not long ago and built a full adder.
Can anyone explain how to even approach for B??
parity check
Look how $$$x$$$ and $$$x + 3$$$ differs and what $$$a+b$$$ and $$$a \oplus b$$$ have in common
Link to Editorial
:v
I think there were a few flaws about this round
Problem A: weak pretests
Problem B : cool problem but i think it requires more thinking than regular div2 B .
Problem C: I dont know why this problem is even there .Just implementation based and a lot of cases(for me). Because of which was not able to read D+ problems.
Didn't quite liked the round but it was a great effort by you guys. i genuinely hope we will get good contests from you next time.
P.S. : i lost expert to this round phewwwwww
I strongly disagree about Problem C being "implementation based". There is a general solution that works for even $$$n$$$, and a small edge case to handle for $$$k = 1$$$. The overall solution isn't tough to implement at all — 145416321
But do you really think it is of Div2 C standard ? i literally got the logic for it instantly ,on the other hand problem B was really cool. I guess swapping the positions of Problems B and C was not a bad idea .
he was talking about the part, where you said it had a lot of cases, not about it's position.
I edited the comment ,happy now ?
Hmm fair enough, I am a bit biased there since I solved B in around 5 mins whereas I took around 25 mins for C, but the solve counts seem to support your point.
lot of cases?
For C it was thinking up the proof that took some time, nothing to implement here
Problem F was somewhat straightforward if you have already solved 446C - DZY Loves Fibonacci Numbers. Why such a tight TL tho?
IMO the TL wasn't tight. The linear model solution passes under half the TL even on Python, and a higher TL would allow for sqrt decomposition or segment tree-based solutions to pass, and increase the probability of some weird hashing-based solutions to pass (which has actually happened during the testing phase), which was not intended.
This O(n) solution got TLE because of its slow input method. Meanwhile, this O(nlogn) solution got AC. So I think the time limit and the data constraints are not so satisfactory.
Aha my bad, I assumed segment tree was supposed to pass. I just realized that it can be done in linear time.
Lots of hate towards B, but even though I had the same issues as everyone (only solved it close to the end and after C), I don't think it's a bad problem.
I don't think it's necessarily about some people seeing an observation about parity and other don't (although arguably it means some people do solve it much quicker).
You could try computing the set numbers you can get with this process with brute force. In reality it's a huge set of numbers that grows exponentially with the input array size. Or is it? I didn't think too much about it, but I couldn't come up with a quick abstract argument why wouldn't it collapse just to a few numbers in practice, so I though it was quicker to write some code to check.
Arguably it's a skill any competitive programmer is capable of (doesn't require you to have a specific bright idea about the problem), and a reasonable thing to do when you can't come up with a quick solution. Also it's useful for testing the correctness of more clever solution anyway.
So the sim looks somewhat like:
Then I tried generating random arrays
aand initial numberx, and seeing what I could get. If you inspect the set of numbers you can get, you'll notice that either all numbers in the sim results are even, or all odd, this is clearly a pattern.After trying it with
x + 3and comparing whether you get even or odd results, you essentially come to the actual solution.my submission Time limit exceed on testcase 178
codeforces is too slow, AI lost to human
My solution of D failed 10 times on 1000 random tests of n<=20 and it still passed system test. Wow. submission
What Happened did we win or loose??
My solution of D failed 10 times on 1000 random tests of n<=20 and it still passed system test. Wow. submission
I got sick and my brain overheated trying to solve problem B.
И всё-таки, ии ничего не решал, я всё ещё достоин!
The writers must have forgotten that B,C are for humans to solve.
Why didn't AI take part in today's contest ? Are they scared ?
Alternative approach for problem D, which guarantees solving in one fewer query (worst case
2*N - 3). (Submission here)Perform
N - 2queries of the type(1,2,j)for3 <= j <= N, and note an index (not necessarily unique, but this is unimportant since ties can only occur at the maximum value, not at the zero) which gives the maximum query value. Call thisbest_idx1, and the maximum query valuebest1.Then perform
N - 3queries of the type(1,best_idx1,j)for3 <= j <= N and j != best_idx1. This time call the maximum query valuebest2and its corresponding indexbest_idx2.Then we are reduced to casework.
Case 1: If
best2 > best1, then we know that the maximum and minimum value pair is contained in the tuple(1,best_idx1,best_idx2), and we also know that it is not contained in the tuples(1,2,best_idx1)or(1,2,best_idx2). By elimination we see that the pair(best_idx1,best_idx2)will definitely give us the correct answer. Total2*N - 5queries.Case 2: If
best2 == best1, then the max/min pair is contained in both(1,2,best_idx1)and(1,best_idx1,best_idx2). Since there is only one zero, we know that it is in both tuples, so we can safely return the two common elements(1,best_idx1). Total2*N - 5queries.Case 3: If
best2 < best1, then we know that the tuple(1,2,best_idx1)contains the max/min pair, but that the tuple(1,best_idx1,best_idx2)does not. Therefore the answer cannot be(1,best_idx1), and therefore element 2 is definitely in the max/min pair. We need to determine whether(1,2)or(2,best_idx1)is the max/min pair, and we can do this by querying(1,2,best_idx2)and(2,best_idx1,best_idx2). The max/min pair is the first two elements of whichever query gives the greater result, and thus we have solved this case in2*N - 3queries.Same as your thought.
had the same solution. +1
Actually, in Case 3, you don't need to query
(1,2,best_idx2), because you've queried that in the first pass. So, in total, there's only $$$2n-4$$$ queries.Very good point. A further improvement.
I was lazy and didn't store the results of my queries but that does indeed save another query.
For Problem B, I just simulate two FST(Finite State Machine, like DFA in principles of compilers) consisting four status(00, 01, 10, 11) to search for some patterns when I can't figure out what problem writer's thinking. One of the FST is for plus operation, while another for xor operation.
Maybe you can try this way to think about this problem, though I didn't notice the parity trick when I was in the contest.
Hello , I am new to codeforces and I appeared in this contest. I had a doubt with my code for the first problem . I dont know where do I post it. I have pasted my submission link. Can someone please help me figure out why did this not work?
https://codeforces.net/contest/1634/submission/145446176
Hi, in the second
forwhere you find ajthats[j]!=s[n-j-1], you need abreakbecause you found that the string is not a palindrome, but in the next iterations you will set incorretlycount = 1if you find ajthats[j]==s[n-j-1].Really poor pretest 2 in Problem A, so from the next time please try to make some strong pretest.
Ok boss
It seems that AlphaCode turned into AlphaPigeon
Good contest(except pretest in problem A)
downvoted for having B as bitwise problem + AI didn't participate
So just learn bitwise
Problem B was really tricky
Congrats sus!!!
when will the problems be given ratings? isn't it taking more time than usual?
Me : problem B from this contest is trash https://codeforces.net/contest/1688/problem/C : hold my beer