Hello, Codeforces!
It's my honor to invite you to Codeforces Round #536 (Div. 2), which takes place at 12:35 UTC, January 31st, 2019. The round will be rated for all division 2 participants (with rating less than 2100). Also we warmly welcome those division 1 participants to join us out of competition.
This is my second round on Codeforces platform, and my first round was on January 31st, 2018, which is such a coincidence that I would like to say thanks to KAN for his awesome coordination and great dedication to this round. Besides, much thanks to testers Aleks5d, cyand1317, mohammedehab2002, ---------- for their excellent testing work. Also, I would like to appreciate the Codeforces platform created and maintained by MikeMirzayanov, without which the round wouldn't be possible.
In order to celebrate the Lunar New Year (or Spring Festival) originated in China on February 5th, I proposed the round with 6 problems, whose theme is about the Lunar New Year. In this round, you are going to help Alice and Bob to solve some problems in the preparation of celebrating the Lunar New Year in 2 hours. I hope that those problems can interest you and improve your programming abilities, at the same time, bring you luckiness as well as high rating in the coming Lunar New Year!
As a convention, the scoring distribution will be announced soon.
Again, wish you more luckiness and higher rating!
UPD1: Editorial is published.
UPD2: The scoring distribution will be 500-1000-1250-1500-2250-3000. Note that there are 6 problems and you will be given 2 hours to solve them.
UPD3: System test is finished. We are sorry for that technical issue which ruined your happiness. Despite the issue, I hope you do learn something from the problem set, which might be far more important than the rating itself. Enjoy problems, and looking forward to the next contest with better problem set to learn something new, which in my opinion is what Codeforces platform wants to provide us with. Thanks for your participation and dedication even after the unrated announcement. :)
UPD4: The real Editorial is published. Thanks for your patience.
UPD5: Despite that the round is unrated, I have to announce the winners, who deserve it because of their hard work.
Div. 2
Nobody wanna write some comments and get upvotes?
me+
me
Me
Downvoted all the "me" comments, since they are irrelevant.
me
Does it mean,that I can still up specialist,until new year?)
Wish you solve all 6 problems and you will be an expert!
我想上紫名
I want to be purple.
Think bravely and code carefully. Hope you fulfill your dream of being purple!
seems there will be lots of hack!
There were lots of hacks in his former contest. So today we must code carefully....
Orz
First be purple and then think to be Orz. :P
hope your dream come true~
the same
I want to be purple too..
I have solved ABCD and rank300, if it's rated I will be purple.
嘤嘤嘤，搞我吗？？？
If it's rated I will be grey.
嘤嘤嘤
If it's rated I will be blue.
I will be blue if this is rated QAQ
Also want to be blue
嘤嘤嘤
i wish all of you to derank :)
you are russian and you have anime profile picture
Is it prohibited to use anime profile picture by Russian Constitution?
Isn't it a bit early to celebrate Lunar New Year on Jan 31th?
I hope there is a round on Feb 5...
Isn't it family time?
I actually had to skip having dinner out with family... only to find out this round will not be rated :( feelsbadman
I thought you might be busy when the Spring Festival is approaching, so I made it earlier.
大年三十肝CF不更美妙吗？ /滑稽
It could be more pleasant to have a CFround on Lunar New Year's Eve .....
deleted.
properly won't
You wrote "Codeforce" instead of "Codeforces" in the title. I'm pretty sure you didn't do that on purpose since you wrote "Codeforces" everywhere else in the announcement. :-)
Fixed. Thanks for your comment :)
Thank god. I finally dun have to wait till 22:35 to join a contest and die to wake up the day after.
Love Chinese round :)))
Same! Agree With U :)
When codeforces round starts early:
if (school && codeforcesround) { gotoschool=false; participateincodeforcesround=true; }
probably you must be programming with java
is it unrated? if its unrated i wont partisipate
Why not ask Mr. .isitrated XD
It is
and now it WAS .... lmao
god its contest made by chinese please no +150 lines of code implementation problems
Check out the implementation problem in SDOI2010
To be honest, 150 lines are not much. Even a segment tree requires 40 lines, let alone something like a HLD and other complex algorithms
And Red-black Trees are also loads of work.
No. 150 lines is definitely not friendly (at least for me).
Really thank you for this Chinese Round!I've never seen such a Chinese-friendly round before!
Very good for Chinese programmers. I don't need to buy a box of coffee this time:)
Thus getting a higher rating :)
Hope that those who are praising the Chinese round will also keep praising after the contest! :P
Again, wish you more luckiness and higher rating!
luckiness??? Most of the time I am so unlucky.
Then wish you more :)
Thank you very much. :)
i with you all bad ratings and good rating only for me as i am the only one who actually deserves it.
Nice to have a good timing for South and South East Asian programmers! Thanks for organizing the contest.
I hope the author was trained in the school of GreenGrape
greengrape's contests were bad
Not all his contests are the same.
Greengrape's problems are good, but the pretests are not.
Your former contest problem set is really awesome. I think this time also we get some awesome problems.
Incoming game theory problem ;)
i hope the chinese are nice and don't mix math and programming like other people do. i couldn't partisipate in the last contest because of this and it was a smart move. if this doesn't have math i will be guaranteed a one-way ticket out of expert to candidate master.
i hope you won't crush our dreams with useless math, jinlifu1999 !
Just interested, what do you call math? Is for loop like for (int i = 0; i<5; i++) also too complicated for you as it contains a plus sign which is obviously math?
I think that even when the problem asked to print "Hello World", it's still a math problem with him.
codeforces admins are imposing censorship among the members of the community
i am very sorry for this i really didn't mean to say it
why no one has taken the Bob handle yet?)
Will there be a translation into Russian? Sorry for bad English.
learn English, it is the universal language and it will stay the universal language for a really long time. if you can't understand English you shouldn't be here. how do you code if you don't understand English? how do people like you exist?
you have anime profile picture and are from india and you expect me to take you seriously?
It's not like the entire Codeforces community take you seriously either, you know.
Lunar New Year ,Alice and Bob ! The names and question story looking pretty much interesting ! Hoping for a great round ahed <3
oops seems like i cannot partisipate i have stuff to do whata bummer cout<<"poponar"
wise decision because as it seems it will most probably have math and you don't want to trash your rating...understandable
Awesome Editorial jinlifu1999
Hope this Helps :P
What happened to The Editorial??
UPD1: The editorial is published.
Alice and Bob means game theory A or B
"Editorial" is up guys! haha
je veux devenir pourpre
Tu est chinois
ou chinoise
Alice and Bob...
zici
Seems that hacking is important in this round... It's a challenge to us without doubt. Also...more funny will come.(maybe) I think it might be a special round.
So fast editorial!! XDDD
What a nice and brief editorial!!!
Just awesome.
Nice all.
Wow... what a nice contest time for koreans! (9:35pm over here :D)
I think it should be unrated.
no
rip contest :(
Contest should be unrated
I hope they fix it soon and the contest doesnt go unrated.
An OI contest....
all the submissions that I'm doing are in queue for the past half hour... is it happening with just me?
You can always check the contest status to see how many submissions are in queue https://codeforces.com/contest/1106/status
Semi-rated?
What do you mean?
He means my handler ;)
Seems strange. The author remembered to thanks MikeMirzayanov and bad thing still happens.
thx for very interesting and hard problems, none of those can't be solved in a minute, also I'm very glad to see a 228 hours queue so everybody can show his true skill.
Make it unrated, unfair to people waiting in queues for like half an hour and then getting a wa on a pretest.
Sad :(
why are u complaining about the judgers here instead of working on problems?
why aren't u working on problems?
why aren't u working on problems?
why aren't u working on problems?
Will it be rated?
Is my Butt an elbow?
Hope this turns out to be unrated. Submissions not getting judged since last 30 min. How to know "in queue" is "AC" / "WA" !!!
Хороший контест. Мог бы быть:(
The contest was turning pretty good. But then long queue happened.
An extremely bad experience because the “in queue”！！
World's shortest horror story: "The round will be unrated because of technical issues".
Finally. Long live the contest!
Reminder: in case of any technical issues, you can use lightweight websites m1.codeforces.com, m2.codeforces.com or m3.codeforces.comHow to use m1.codeforces.com to resolve
In Queueissue??It can be useful only if there's a problem with internet connection. Today using m1/m2/m3 couldn't help as the problem was with judgement system, not the website itself.
Well it could be a good round.
I think It should be rated or semi rated...all faced the same problem..so I hope it won't be unrated
or the round should be extended
I think it must be unrated :( Because we can't see a clearly result of our solution.
There's still an hour left! Hope the round will be rated
Help me find a word for this...
queue-forces? servers-down-forces??
WTF-is-happening-forces?!?!?!
shitty-task-forces
That's a bit correct for B, but other problems is good.
Isn't D is too easy for div2 D?
In my opinion, E is also too easy
Semi-Rated please !!
How can it be semi-rated? What does it mean?
In semi rated contest the rating change is applied only to the participants with positive change(increase) in their rating. It has been done in past contests.
Thanks for explanation, I didn't know. Yes, it could be a quite good idea.
Can't see my submissions, is this my problem? If I submit again, it says "You have submitted exactly the same code before" But I can't see any of them, they're all empty, not even in queue!
Same problem happenend with me too :(
Just make it fcking semi-rated
It would be unfair for the candidates who solved questions in first attempt to make it unrated, as they deserve their ratings. So better make it Semi-Rated.
30 minutes after I submitted my solution, it gave wrong answer verdict. Site is also too slow. Contest must be declared unrated.
Agree with you.
Exactly, you know, I mean WTF?? Just bekeshid biroon az contest...
Such Long Queue !!!!! What the hell :(
Is it rated?
If the contest goes rated, it would be unfair to those who made a silly mistake in their first submission, and got non-AC verdict more than thirty minutes after the submission. In normal Codeforces round, they would have quickly patched and resubmitted, but now they can't, and the points they would get for resubmitting the problem would be much much lesser than what they could have got generally.
Edit: even after the contest got extended, the above point still holds, and I believe quite a several number of people would be affected by such a situation.
WTF, make it unrated ..
What does the FOX say???
After such a long queue, I don't see any point in keeping this round rated anymore. Even increasing time duration doesn't make any sense.
Also problems C and D are much easier as compared to B.
What's the point extending the contest, I've never realized....
How come it would do justice with the inconvenience caused?
the problem C lookes just like NOIP2018 Day1 T1 when I hadn't gotten it's meaning
Looks like queue is moving. Wonder if it will clear before end of contest.
Is the contest extended? It still shows 1hr 15min remaining?
QueuedeForces
Maybe it should be semi rated that people who waited the queue and got any verdict other than AC it should be unrated for them..and people who waited the queue and got AC it should be rated for them.
Man, I got a 'WA' due to long long problems and waited for 30 minutes and received it ! Argh!
Should be unrated. Makes no sense to just extend the round.
WA on test case 1 after waiting for like 20 mins xD
Extended??
Let's not hate on jinlifu1999 too much, he made very interesting problems and the technical issues weren't his fault.
The problems were not interesting! C, D were easier than B which was just a dumb implementation question.
unrated. :(
The round is UNRATED....
I bunked my class for this contest :'(
sed
Another emotional story within 15 words . "Due to technical problems, the round will be unrated. We're really sorry about that"
It's a horror story for one who wants to be over a rating of 1600 like me ;-;
this is so sad!!!! :3
It's down again...
i will never become green :(
Anyone remembers round 485? The queue froze down. The same story like in this contests. The round was rated that time. I don't know why don't make it rated too. Codeforces should make these decisions consistently. If that was rated this should also be rated.
Story of today's Contest: 1) Submit solution till D in first half hour 2) Wait for verdict on B,C,D 3) Get a wrong/tle 4) Submit a better solution. 5) Be happy because predictor shows increment. 6) Contest goes Unrated. cries in corner
Guys, sorry about the failed round :( Please, do not downvote the post if you liked the problems. The writer is not responsible for the incident.
This time we faced with the direct actions to break down the testing process. Somebody found an issue in the judging process and exploited vulnerability to make it really slow. I'm working on the fix.
is it related to queues which were there in today's morning?
It seems, yes.
Why not semi rated??
What if rated but rating change = max(0, original_rating_change) ?
Rating inflation
Even though i'd have had +100 delta or something, this can't happen.
There would be too much inflation
+1
I know it's not easy at all to keep the system intact especially with the increasing number of participants day after day but it has become very demotivating to play well without any results. We must solve this problem once and for all
vote for you
Why on earth is that there is no hacks?
Maybe the problem should be ACDBEF?
I submit a code for problem B in 0:34, and get a Wrong Answer 7 in 1:14.
Then I found that I forget use long long.
Submit and Accept in 1:18.
Wrong Answer = 40min + 50point.
Hope Codeforces will be better.
I left codeforces some 2 years ago due to 80% of rounds being declared unrated back then. It was quite unwise to come back and expect something else I suppose.
It's more like 10% now to be fair.
I want to be candidate master In fact. I failed
-160 минут жизни
为什么 Codeforces 会在中国春节前出现问题？如果是黑客攻击的话，我感受到了黑客深深的恶意 另外，我本来能涨60分。。。。。。
Why does Codeforces always have problems before the Chinese New Year? If it is a hacker attack, I feel the hacker's deep spite What's more, I could have a rating change for +60
同感! 差這場就紫了 結果... I was about to become purple :(
看老爷子的说法好像是黑客攻击
According to MikeMirzayanov, Codeforces has(have?) been attacked by a hacker.
傻逼黑客
shabby hacker
I'm really really really sad to face this unrated contest...
It is farther for me to be a master...
what's your opinion about not to be rated ?
If it's rated I will -18.
But if I can get the WRONG ANSWER on time. Maybe I will get a better result?
who knows.
Where do you guys see what your rating change would be?
I use this -> https://codeforces.com/blog/entry/50411
Thanks!
I will also -18 if it is rated.
I forgot to add "1ll * " in just one branch of my function in problem B, so maybe I would have better performance if I see WA right after submission.
It is a really awesome round, seeing it to be unrated is sad, but seems that there's no other choice :(
Hello. I can not understand why the round will be unrated? What's the reason?
just can say hello :/
I heard this round is unrated. Is that true?
Yes,It's true...
f**k
Yes
What is wrong with my B. code? Its running fine in PC but showing WA in TC 1 ? How ? I m stuck..
This This This
It's still in match now, so I can't read your code.
We can't see your code.
But you can use the CUSTOM INVOCATION to see what happened in your code
"Как же я ненавижу эту математику" (fedoseev.timofey)
When first time solved 5 tasks during contest (if they will pass final tests, of course, but anyway!) and.. it is unrated :D
it was my first time to solve 4 problems within less than 1 hour... sad unrated
ALL of my friends had gave up this contest as soon as they got the message that the contest would be unrated.
I lost the only chance to be orange before the Spring Festival.(because if I want to join in other contests I must stay up late.)
I think Codeforces can build an extra judgement system in reserve since this happened more than once.
Sorry for my poor English.And hope Codeforces can become more and more nice.
Why not 85??
Thanks for contest.
Bad day, I stay up late till 22:44(local time). And tell me unrated? However that's alright, I'm in bad state today. So Happy Chinese NEW YEAR everyone!
is 22:44 late?
Of course, "NO".
Lol, you stay up LATE till 22:44 ? What if I say you that THE MOST of the contests for me starts in 00:35/01:35 ? But yesterday round started just in 22:35 :D That is why I took part in it, and... it is unrated :(
Problem C was nice, but now I can't stop thinking how could the problem been solved if n could be odd. Any idea?
i think you need only to marge to int then n will be even , but i don't know what is the best two number to marge them maybe it's the two largest number
Try merging the largest number with each of the other number and run the greedy process, then you have an N^2 kind of brutal algorithm, that’s the best I could come up with...
im so relieved i DDIDNT partisipate ikn this contest... Ive asked multiple times like usual: is it rated is it rated everyoine say IT IS RATED BITCH READ and i say sorry i cant read and then pfaaa mama im actual intellect because now its unrated as i exepcted
If its ok to discuss problems now, has anyone else faced WA on pretest 23 for problem E? I can't seem to figure out what might go wrong with the logic.
Upd: Never mind that, silliest implementation mistake. Really worth my handle name.
I think this round will be unrated because the system is too slow and there was too many queue
you think?!
How to solve D???
You can do an almost normal BFS traverse, starting from vertex 1.
The only difference is, to maintain the lowest lexicographically order, instead of storing to-traverse-list of vertices in a queue, we'll store in a MinHeap-based priority queue ;)
why we can't sort adjacent list and start dfs iristran911 ?
This is not enough. I made the same mistake as you ;)
Take this graph for example:
So, you start a DFS from 1, which leads to 2, then 3, then 5, then 4.
However, I can turn back and visit 4 beforehand instead ;)
thanks very much iristran911 ! you are right.I haven't seen it .
Thanks, I was also confused why it is not working
bfs with priority queue (lower node index has higher priority)
How to solve F? I reduced it to solving a root of xa = b(% p) , and found no way to solve it.
This is something called "discrete root algorithm" — you can see reference here. ;)
can any one explain B
What can we explain here? It's just a simulation of what's happening in a shop. There's no special algorithm or trick that can be used.
C was much easier then A and B
LOL seems like problem B & D must change their positions
How to solve F? I just find out that we can find the power of fk in fn using matrix exponentiation, but how to solve a congruence system like xa ≡ b (mod 998244353) for x if we know a and b?
Write both x and b as powers of some primitive root and do discrete log.
Thank you :D
Maybe this can help https://cp-algorithms.com/algebra/discrete-root.html
Thank you :D
Here's a proof for C's greedy solution if you are wondering:
1: Groups must be formed as pairs of 2.
Proof: As (a+b)^2 > a^2 + b^2 for positive a, b, we want to minimize group size. As size has to be greater than 1, and N is even, all group sizes must be 2.
Now, we have to pair each number with another such that sum is least. We double this sum. This doubled sum can now be represented as summation (ai + bi)^2 where ai and bi are both permutations of the given numbers.
2: ai and bi must be oppositely ordered sequences
Proof: summation (ai + bi)^2 = summation (ai)^2 + summation (bi)^2 + summation (2*ai*bi); We want to minimize this sum. We observe that the first two terms are constants (sum of squares of all given numbers). So, we want to minimize the 3rd term. This is done when ai and bi are oppositely ordered, proof is a direct application of rearrangement inequality.
Now, observe that this doubled sum corresponds to the pairing where ai is paired with a(N-i+1), with i <= N/2. Thus, we are done.
Me waiting after submission. Waiting....... waiting....... One eternity later .......... Fk it, anyways its going to unrated
I solved problem B in 30 seconds and wrote its code in 30 minutes :( I think problem B wasn't a good problem for an algorithmic contest. But maybe I'm wrong.
Div2 A/B are rarely algorithmic problems anyway. They're almost always implementation. It's just that the implementation was slightly annoying in this case.
Has anyone else faced WA on pretest 21 for problem E?
It might be that you use "set" instead of "multiset".
Um..I have used multiset, but also get WA on pretest21==
If u used multiset, u should erase like multi_set.erase(multi_set.find(x));
Because erase on multiset is erasing all elements which value is x.
I did same mistake lol.
Thanks~
Oh yikes really? I wasn't aware that that's how multiset::erase worked. That's unfortunate. Thanks.
Shit, I did this too. I've done this mistake some (long) times ago. Now seems like I forgot this behavior again :(
Has anyone else faced WA on test9 for problem E?.... And why I cannot submit my code now.....QAQ
Make it rated for first 25 minutes when there was no queue.
LOL thats unfair...
I'm disappointed too because I did well in this contest, but server was not good and we should accept this situation.
I see some people didn't like question B. Personally, I didn't mind problem B because it's a straightforward problem that wasn't too tedious to implement (my solution was only 30 lines and can probably be shortened). I think being able to quickly and correctly implement a solution is just as important of a skill as knowing that obscure number theory algorithm that is used in a problem once a decade. Also I think that it's sometimes hard for problem setters to come up with interesting div 2 A and B that aren't just implementation or simple math, but I appreciate their effort in trying.
Some people were also saying that B should have came after C and D. B's solution was just simulating the process (with speedup) and only required knowledge of sorting. C required intuition (need to think to match small with large) while D required graph knowledge, so I think B is more likely to be solved by a someone without experience (i.e. a beginner) than C or D.
Anyway, unfortunate situation with the long queue. Hope next contest goes better.
Agree.
Simulating can be one of the problem solving skill.
What is the solution of F?
I got stuck at counting the number of solutions of the ecuation
n^x=ySince 3 is primitive root for p = 998244353 you can assume f = 3g and we have
mod (p - 1) . And this equation can be solved easily by matrix exponentiation.
ok thanks!
https://cp-algorithms.com/algebra/discrete-root.html Using this you can find a solution if it exists.
don't blame Codeforces bad things happen:D
You owe us one more contest)
Hey,
Could someone provide me with pointers to why this submission got MLE? https://codeforces.com/contest/1106/submission/49268507
Seems as if most of the people who got an AC did the same thing, except maybe declaring the vectors as global.
You may visit the same node more than once.
I do maintain a list of visited nodes, so that shouldn't be the case.
You maintain it but you don't use it.
Right. Gotcha. Thanks a lot!
If the node is already visited you should not push its neighbours in priority queue. Sample :
You are pushing neighbours of 5 four times in priority queue.
Yeah, gotcha. Thanks a lot!
1 round unrated after so many contests is surely acceptable.Thanks Codeforces!
Whenever I want to gain some rating, the contest will be unrated = = sad story
Where is my rating :(
unrate
In queueueueueueueueueueueue round... How I hope that it can be rated!
thanks for the round i really learned something
Poor Alice(Expert) and Bob(specialist)!