Hello, Codeforces! & Happy Chinese Teachers' Day!
We (OICon Team) are so excited to invite you to take part in OICon Round 1 (Codeforces Round 896 (Div. 1) and Codeforces Round 896 (Div. 2)) which will start on 10.09.2023 17:05 (Московское время). You will be given 6 problems and 2.5 hours to solve them in both divisions.
- Please notice the unusual starting time!
- One of the problems has two versions but their statement are not exactly the same, which means that you can't pass the easy version using the code of the hard version. However, you can only make hacks when you pass both versions.
- There will be $$$0$$$ interactive problem in each division so you needn't read the guide for interactive problems.
- Score distribution:
- Div. 1: $$$500-(500+750)-1000-1750-2500-3000$$$
- Div. 2: $$$500-750-1250-(1250+1500)-2500-3250$$$
The problems were authored and prepared by Error_Yuan, duck_pear, programpiggy and me.
We would like to thank:
- Artyom123 for his long-term & high-quality coordination 😊😊😊
- Again, Artyom123 for the Russian translation 👍👍👍
- dqstz, BreakPlus, DisconnectedGraph for providing a few rejected problems 😭😭😭
- Um_nik, gyh20, MagicalFlower, Sugar_fan for Legendary GrandMaster testing 👽👽👽
- sansen, Kubic, Alex_Wei for International GrandMaster testing 😎😎😎
- rui_er, MatrixGroup, swiftc, themoon, N_z__, __builtin_gjr for GrandMaster testing 🧐🧐🧐
- HappyIvan, Azuma_Seren, User_Carrot, Wilson_Inversion, chen_03, Valters07, Lavine, Kieray for Master testing 😯😯😯
- guoziyang, NoCommander, Alan_dong, small_peter for Candidate Master testing 🤔🤔🤔
- Coffee_zzz, fAKezjf, purplevine, Black_Fate for Expert testing 😃😃😃
- mikcf, J.S.Eason for Specialist testing 🙂🙂🙂
- wz20201136 for the only Newbie testing 👀👀👀
- ChatGPT for getting 0 point in both divisions 🤡👈🤣
- And, You, for participating and getting positive delta 😘😘😘
- Last but not least, MikeMirzayanov for great Polygon and Codeforces platforms 🎅🎅🎅
Good Luck & Have Fun!
P.S.
UPD1. Editorial is out.
UPD2. Contest is over! Congratulations to the winners!
Div 1:
Div 2:
First Solves in Div 1:
First Solves in Div 2:
As a problemsetter, OICon stands for...
Obviously Incorrect Conclusion :)
(idea from our great red sun MatrixGroup)
Only Intuitive Conjecture
Oh, Incorrect, Comma nder.
Only Interesting Contests
OIers' Convolution
Yet another Chinese round!
As a tester, I enjoyed the round and found some very nice problems! I recommend you to participate.
Looking forward to it.
As a some-really-interesting-problems-in-this-contest-finder, I tested.
Hope all of you can get positive delta!
As a tester and a member of OICon, I want contribution!
This round has many really interesting problems, and I hope all of you can enjoy this round(and get positive delta)!
Done :)
As a first-time tester, I hope you enjoy this round!
As another first-time tester, I hope again you enjoy this round!
As a rare tester, I don't think it will be very, so called, Chinese, so I do hope you will enjoy this round!
As some strong testers' friend, it seems that this round is fun, but I cannot enjoy it :(
Hope u can get positive delta!
As a rival of the author, i want negative votes.
Fun fact: sszcdjr is homosexual:)
What is fun about homosexuals?
You are probably the most qualified person here to answer that question
Gay round! Whoo!
As a fake author and a fake tester, good luck to you & have fun.
Support our team, OICon.
"you can't pass the easy version using the code of the hard version"
wait what?
are you cyan at english too?
well, English isn't my first language :)
c++ is no one's first language either
you know that you can actually say
I was expecting this reply but it was just choice at the moment
fair enough. and also maybe you should consider using this line of code:
then your code will be much easier to write. for example now the code should be:
I do know that... you could see my submissions, thanks tho
oh ok, i didn't see your submissions, sorry
no worries, it was supposed to be a joke code so I didnt write what I actually do
It's obvious that he understood the sentence and was asking 'why the unusuality?'. Perhaps you need to improve your comprehension skills.
it is said that the easy version is different with the hard version at all
like 1786A1 - Non-alternating Deck (easy version) and 1786A2 - Alternating Deck (hard version)
Instead of just changing data scale and constraints
like 1856E1 - PermuTree (easy version) and 1856E2 - PermuTree (hard version)
qp
As a ChatGPT, this round is so difficult :(
I recommend all the bots to avoid participation, or you'll probably burn your CPUs up.
ChatGPT for getting 0 point in both divisions LMAO
Solving A in 00:00 and 10 unsuccessful hacking attempt ending :P
.
orz for no interactive problems.
OICon stands for Orz Institute & Constitution
Love sszcdjr
Love sszcdjr
Love N_z__
Love shinzanmono
Love sszcdjr
Love [DisconnectedGraph]
Love BreakPlus
funny emoji :)
sszcdjr /se /se /se
[O]nly [I]nteractive [Co]deforces Rou[n]d
But there are no interactive problems,so forget it.
Sdandy for
Spelling issue
September Fools' Day !
Wish i do well and get green
Wish getting positive delta and not get back to blue :)
Wish getting negative delta and get back to green :)
As a invited-to-but-actually-did-not-test 'tester', wish you positive delta.
sszcdjr is great.
orz sszcdjr
I hope my rating will be increased after this contest
Would it be a round of zero?
This is definitely the most interesting contest blog I have ever seen.
No ChatGPT is harmed in this round...(for 0 points)
Unrelated but does anyone know how long it takes to update the ratings for previous contest problems ?
You're unrated contestant in last div3
I am asking about problem ratings.
oh, my bad. it takes usually 3-5 days.
It usually takes way more time than that.
As a Chinese, hope I can get positive delta.
Wouldn't it be better if it started at 19.35 as usual ?
We authors are in UTC+8, and it will be 22:35 for us if the round starts at the usual time. We want to go to bed earlier :)
Why you can't start it more ealier like 20:05？
Because one of the authors won't be available before 22:00 (UTC+8) :(
By the way, when you start to prepare for this contest?thx.
We proposed the proposal on Feb 2023, and got our coordinator on May.
But for some other countries wouldn't it be too early
Emoji Forces ;)
or maybe it's (l)O(l)ICon :))
or maybe it's (no numerical prize in V)OICon(tét)
The start time is 07:35 PM IST then why is it not started yet?
I thought the round is today my bad.
I might be wrong, but I think that the first step to be GM is to put an anime profile photo.
this is same as what i've figured out :lol:
As sszcdjr's 'ami(e)', j'aime il.
Hoping that unusual time won't become usual again :)
In my opinion, OICon=Olympiad in Informatics Conference :P
OICon stands for
Over Implementation Contest
It happened.
222776617
Hope to become an expert, good luck
Chinese round from sszcdjr and so on. Sounds loke it will be VERY difficult. Luckily I'm afked. Hope others have fun.
"you can't pass the easy version using the code of the hard version"
wait, what?
D1 and D2,,, hope the problem isn't so eccentric
Hi, is it only me that m2.codeforces.com is kinda broken? It seems that some of the JS files are replaced with the redirect message. It's not happening in m1 and m3.
For me too.
Use of emojis!! cooolll..
as a tester hope u enjoy the contest :)
Yet another Chinese round!
OMG interesting dude!
Div2 D1&D2 are brilliant!!
Thought i had D1 in 5 min but after getting 2WA realized i was wrong. Really nice contest!
what's so brilliant about it?
I had fun solving them.
what was div 2d?
In the contest when the site went down I submitted the code on m3.Codeforces.com but I had already queued a submission on the main site. The code is exactly the same but I got a 50 points cut because there were two submissions both of which passed. I sincerely hope this issue could be sorted and I could get my actual points in that. Mike and the organisers please look into this.
D2 == mystery of pretest 3
WHY in $$$E$$$ ($$$n$$$ $$$<$$$ $$$10^{18}$$$) and there is NO pretest where $$$n$$$$$$>$$$$$$200$$$ $$$??$$$
i love problem B so much
How to solve it?
Minimum of:
distance from a to b
distance from a to major city + distance from b to major city
I think it's better written as min(dis(a,b), min(dis(a,majorCity)) + min(dis(majorCity,b))).
Can someone give any hints about how to solve D1
For each element you need to give some power of 2 to someone and also take some power of 2 from someone and for each element not equal to the average of the whole array this give take pair is unique. Also if the sum of all elements of the array is not divisible by it's size then answer doesn't exist.
I was trying to do same thing but got WA on pretest 6. Are there any edge cases ?
Idk but i also got WA on pretest 6 due to silly mistake(Writing — instead of +). I also ignored all elements equal to the target final value because we can always use them as the middle man for some operation.
This was my first submission
222777285
Can you help me figure out the mistake ??
idk bro. i didn't do it by manipulating the bits directly but by trying 2 options for each element. Either it gives first some power of 2 and then takes some power of 2 or the other way around and whichever worked without violating the conditions stored it in the map and then checked whether the counts are equal or not
222801225
Let S = sum(a), then obviously we need each element to be S/n. For each element find its difference from the target value. Using the constraints (ie everyone must give and get a power of 2), find exactly how much one must give and get (this is the hard part). Then check if each give has a corresponding get.
Each person needs to gain or lose some amount of candles to reach the average. So $$$a_i - avg = 2^x - 2^y$$$. It turns out that if $$$a_i - avg$$$ is not $$$0$$$, then it is either impossible or there is exactly one way to choose $$$x$$$ and $$$y$$$.
Another hint: Since we use powers of two, think about the binary representations.
Once you compute $$$x$$$ and $$$y$$$ for each person, the answer can be found by considering the set of all $$$x$$$ and the set of all $$$y$$$.
there's at most only a way to make a number that's different from avg equal to avg. Let delta = v[i]-avg. Abs(delta) must be in form "0...01...10..0" and you can just add the first bit before the one part and subtract the last 1 bit (if abs flips the sign you have to flip which bit to add and which to subtract). If delta is 0 you can ignore it, and if it isn't in the case i mentioned, just answer "NO".
Now just count all the bits added and subtracted. If this is even for each bit, then answer "YES". (My code 222771034)
The idea for D2 was to just consider the case when abs(delta) = "0...010....0". In this case you can just give/get that one bit. I'm not sure why my code fails though
My version (propably there are much easier ways):
if Sum(a)%n!=0 answer NO. let d be Sum(a)/n
Calculate all numbers 2^x-2^y from -10^9 to 10^9 and memorise what x and y are for each of them (with exception of 0 there are only one option for each number). Let's call this numbers "good"
Check that d-a[i] is a good number for all i, otherwise answer NO
let's call people who need to receive candies before give candies "poor". everyone who is not poor is "rich".
let's create four arrays of sets: poor/rich people who need to receive/give 2^x candies. (if someone already have d candies, we always can deal with them). Check that |poorReceive[x]| + |richReceive[x]| = |poorGive[x]| + |richGive[x]|, otherwise answer NO.
If there are no poor people, answer YES
for each x for each poor in poorReceive[x] if richGive[x] isn't empty remove one rich from richGiveEmpty, remove current poor from poorReceive[x] and add them to richGive[y] (2^y is the amount that this poor need to give).
if we did'n change anything in step 7, answer NO. Else, return to 6.
We will not repeat steps 6-8 too many times because there can't be more than ~30 people in each cycle without people who already have d candies.
Ok, editorial says that steps 6-8 aren't needed at all and poor/rich division too.
D1 and D2 are amazing problems but i couldn't figure out some edge case apparently ;)
Div2D once again yeeted my hopes and dreams of becoming CM.
How to solve Div2 C?
I'm sorry, but my solution to F has a complexity of $$$O(N^2)$$$. I hope the systest is as weak as pretest.
Your solution is the fastest :) Do you have a test with TLE?
I uphacked my submission with a test like this:
$$$1,-1,1,2,-2,2,3,-3,3,...,n,-n,n$$$ ($$$n=166666$$$)
Felt like I was close to getting D2 but just missed. Still might become expert today.
Please don't tell me that in Div2 D1 you just have to check if for each element abs(element-avg) should be a power of 2 is the answer. Tell me that this was not it.
This was my first approach which gave WA. So you are good
this was not it
I checked the balance after breaking the difference of element — avg into two powers of 2(as a swap goes both ways). Any number which is a difference of 2 powers of 2 must have exactly one string of '1s' in its binary representation (we can check using binary subtraction). In other words, 2 ^ (high-bit + 1) — 2 ^ low-bit should be equal to the difference between element and average. Here we are referring to the low-bit and high-bit of the difference. At the end, the balance should be 0 for all bits for a valid arrangement.
In div1 , score [2000,2200] is from around 160-th to around 60-th.
Many participants are ranked by "the number of dirts" since the total score is quite small. Unfortunately, i'm the one who has many dirts. Sad.
Sorry bro, it's true that the score is quite tight and we should have made the score distribution larger for Div1 :(
I wrote $$$Tlog^3n+mlog^2n$$$ and got TLE in problem C :(
deserve the downvotes ngl
I think he is talking about div1 C
I mean div.1 C
ok mb i didn;t see your rating
I know why I got TLE.
I used
while ((1 << d) - 1 < n) d++;withoutlonglongso it would loop infinitely.Turned out D1 indeed was easy...
fixing tons of cases in div1D is frustrating :(
My thoughts on the Div2 D1, please help to improve.
We can group all people into three types: rich/poor/avg. Rich means he has more than avg candies, and poor means the opposite.
We need to record for everyone, how many to give out and how many to receive in.
For rich people, suppose he has 111000 (binary) more, then he must receive 1000 (binary) and give 1000000 (binary) since 1000 + 111000 = 1000000;
For poor people, suppose he has 110000 (binary) less, then he must receive 1000000 (binary) and give 10000 (binary) since 10000 + 110000 = 1000000;
All the above receives and gives must cancel out each other to make the whole party happy.
What about the avg people? Well, apparently if they are more than 1, they can just stand in a loop and choose the next one to give and receive from the previous one. What if this is only one avg people? I don't have good thought yet.
The first example shows you what to do with 1 avg person (you can just put them into any chain of transfers as they just pass any received candies straight on).
Thx!
avg can just connect two people. instead of a giving to b, a gives to c, which is avg and c gives to b
Edit: damn i'm always late for comments today
Thx!
Is there a penalty for re-uploading a solution even though if previous one was correct?
According to rules, anything apart from AC and compilation error runs into a penalty. Compilation error I'm not sure but AC won't result in penalty.
But it did for me,it skipped my 1st upload.
Terrible difficulty gap, ABC then go to jail
Sorry, we didn't expect D to be that hard :( Some testers thought it was suitable :(
annoying case work
Indeed it can be solved without case working...
True I think D1 a suitable problem for that range
Sorry, I thought he was talking about d1 of Div2....I have no idea of D of Div1...pls ignore my previous comment
How?
(Div2, problem B) I submitted O(N + K) solution written in Kotlin, but I got TL at test 3. Do anyone else have the same situation? Does really result depend on programming language? If so, is it fair enough?
UPD: I rewrote my code a bit and got TL 6, where N = max possible value. Honestly, I do not understand the motivation to use such a small time limit in the task
UPD2: My rating decreased -_-
It is fair, nobody is stopping you from using C++.
I agree that it’s fair, but it looks a bit strange for me, especially when I use linear solution and N <= 2 * 10^5 (not really huge number)
Anyway, tasks were interesting, I enjoyed the round
Will O(K) pass?
K <= N, but at least you should input all the positions, so solution is O(N + K) = O(N + N) = O(N)
My solution is O(N + K), but I got TL at test 3; then I rewrote my code a bit, but got TL at test 6
In div 2 , problem A, problem setter should be ensure us l != r. But he didn't. If l==r , I take range only one index and Xor same index will become ultimately zero If n is odd. I submitted same implement in different approach about six times. But always wrong answer. then I decided to not to take same index instead of using first two index. For a result , number of k also increased. then got AC. But I was always right if l==r according to this problem description. Am I right or not?
you are wrong. if $$$l=r$$$ then $$$s=a_l$$$, so you will replace $$$a_l$$$ by $$$a_l$$$, which does not become $$$0$$$. Read the problem statement next time
Next time you should use the "Ask a question" tab on the constest front page to clarify it. I also woundered if $$$l = i = r \implies s = a_i \oplus a_i$$$, but before guessing that and implementing it, I asked the problemsetters and in a few seconds got the reply "No."
A very bad round!!! I'm upset!!!
I agree, to give so much constructive...
Problem A edgecase l == r killed me.
I need to learn to not make stupid assumptions...
What a mathforces round...
Div.1A: I just guessed the pattern and proved it by AC.
Div.1B: I got to the key observation (Hint 2 in the editorial) relatively fast, but the implementation of B2 took me a long time.
Div.1C: I came up with the rest of the solution in ~15 minutes, but I had a hard time dealing with $$$n \le 10^{18}$$$. Passed sample tests 1 hour after the contest. (Why is my submission still in queue = =)
i do bad at the contest but it has some really good problems like E(of div2) and other problems where really good for them rate
Am I the only one who felt Div2 D1 was too much implementation heavy or was it really?
Nah not much of implementation tbh
First time hitting 1500))
why my and other solutions in queue but another solutions get tests momently
I was close to getting a $$$\Theta(900 n)$$$ solution for div2.D1, but kept Wa on Test 3 because I forgot to determine that $$$2^x - 2^y$$$ might be unsolvable, and I feel that because I used several unproven conditions, it kept me wondering if the ones I was using were right, thus ignoring the very obvious error of $$$2^x - 2^ y$$$.
It's a very good problem, but for me, writing about this kind of problem makes it a not that enjoyable experience :(
B1 and B2 are interesting problems, but I solved them for too long time.
Congrats to null_awe, finally GM almost half a year after 2399.
Thanks!（´∀｀）
Meanwhile a clown participated in this just to 2398->2309
My screencast
I wrote something wrong in B1,B2 and I only fst B1. Maybe B2 test case too weak? I found a hack of my submission 222782134. But it shows Unexpected verdict in hacks.
The test:
1 18 20090905 20090905 20090905 20090905 20090914 20090914 20090908 20090908 20090908 20090908 20090908 20090908 20090908 20090908 20090908 20090908 20090908 20090908
Sorry, the tests for B2 are a bit too weak. You got the Unexpected verdict because one of the testers' solutions (which is marked with "Accepted") got hacked in your challenge. The test case will be added soon.
It's a really good contest and let me return to violet, thanks to problems setter~
I posted a video editorial of problem C from Div. 2, I hope you enjoy it and find it interesting.
tho it seems that this round isn't that good, but it's still not so bad I think. But ig it's more like guessforces in div.1 A&B1B2.
A: I just observed the pattern of the sample. Once you noticed that, it's trivial. Not the best problem in my opinion, but still not bad.
B1&B2: I just did it the same as hos.lyric's. Guess the claim mentioned in the editorial, and don't prove it at all. then just pass it.
C: Quite educational in my opinion. Though it may be quite standard for some high-rated geniuses?
Overall this round isn't that bad. Sure, the problems aren't that nice, but it's not a reason to downvote.
Why is there a popup notification "Can't read or parse problem descriptor" every time I try to open any of problems of these rounds? For example, 1869F - Flower-like Pseudotree won't open.
It looks like it's been a temporary glitch. Now everything is working.
I usually like chinese rounds. Problems will be observation based.
Has the editorial blog been deleted? I couldn't open it