Hello, Codeforces!
It's my honor to invite you to Codeforces Round #460 (Div. 2), which takes place at 13:05 UTC, January 31st. The round will be rated for all division 2 participants. Also we warmly welcome those division 1 participants to join us out of competition. Note that round starts in the unusual time! :)
This round is prepared by me and my friend wuminyan0607. Many thanks to my friend for helping me testing the round and generating testcases. Besides, many thanks to the Codeforces coordinator KAN for giving me a chance to hold this round, testers cdkrot, cyand1317, demon1999, Glebodin, vintage_Vlad_Makeev, FalseMirror for testing this round and MikeMirzayanov for the great Codeforces and Polygon platforms. Without their huge effort, this round would't be possible.
Hope you can find these problems interesting. Wish all of you fewer bugs and higher rating!
The scoring distribution will be announced soon.
UPD1: There will be 6 problems and you have 2 hours to solve them. The scoring distribution will be 500-750-1000-1500-2000-2500.
UPD2: System test is over. Hope you will like those problems. Congratulations to the winners!
Div. 2
OO0OOO00O0O0O0O00OOO0OO (Solved all 6 problems and got 4 successful hacking attempts)
pannibal (Solved all 6 problems)
Div. 1 & Div. 2
UPD3: Editorial is ready!
two consecutive rated rounds that's good__
Hope you enjoy this round :P
not, if you decrease your rate.
What's the name of the cute character? :P
It's something like "The thinking bear".
To be honest, I'm not sure about the English name of that character. :)
I think it is from uoj.ac. At least that is where I've seen it.
GREAT I will give you an upvote :P
A partial list can be found here (#2, #3, #5, #6, #7 from the top). I skimmed through my message images and found six more, which altogether are enough to supply two picture rounds (no I don't suggest that).
Good time for East Asia participants！
Why so [user:@Phos] ?
Usually this round would begin in 17:35(MSK),for Chinese participants they have to start their work in 22:35(CST) and Japanese even later 23:35(JST). It's too late for most of the students in the East Asia.
To be honest, if these bears appear in the problem statements, I'll consider spending the remaining contest time looking at them instead of raging randomly :P
No pictures in problem statement. :P
So you can focus on solving problems. :P
And so that pages can load more quickly. :)
1 upvote = 1 pray
1 downvote = ?
We will try to bear this round too.
Your pun is soo POLARizing
It is borderline un BEARable :P
This time, my handle will definitely turn into "Green" . Nobody can stop me !
Haha all the best. By the way you have to solve atleast 4 problems to become green. My advice is solve at least 2 problems consistently in all contests to become stable in green rather than targeting too much once at a time
Regularly solving only A and B is enough to become green.
Yes but his rating is 933.In order to become green he has to get +267 which I think is only possible by solving 4 problems in this contest.
If he solved four problems he will probably become specialist in one round! This is not impossible. worse did something like that.
OMG!! Thanks for sharing that
Thank you guys ! Specially Knight_of_Thirteen and bharath. I am looking forward to solve A and B.
emmmmmm looking forward to doing something
Opps
I have solved A and B.
Great, hope they will pass system tests :)
I hope they will pass, but struggling to solve C. :(
Cute drawings!
Another cute images contest!
I think that adrozdova is very old nick of demon1999) Why do you use it?
I think it might be because they prepared the blog post way in the past, when it was still his nickname. This is only a guess though.
More than one year?)
Maybe testers' Polygon handles are directly copied here — grikukan is also gritukan's former handle.
CS Academy Round #67 starts right after the round, is there something to be done about this?
Looks like that we can't participate in both contests.
UPD: In codeforces calendar this contest is shown in 13:35 UTC. Please fix it.
UPD: It's fine now
C137 Adhami It is delayed for 30 minutes
Is this round a Chinese round?
I realized the author is Chinese at the first sight of thinking bear... BTW, I study in SJTU too. It's frustrating that campus network doesn't work from 00:00 to 06:00. So now it's a fantastic chance for us to participate in contests and get higher rating, isn't it?@jinlifu1999
But it is a div2-only one :P
I hope the difficulty gradient for this contest will be somewhat better than the last one. 2 rated contest in a row. ✌
"The scoring distribution will be announced soon."
Lies, lies everywhere.
Support teacher Jin OVO 资磁靳老师
OVO
Thanks :P
solved 2 problems and got 50+ ratings :) , seems cool :D:D
Don't you think of solving 3 or more :P
Yes , I think of solving 3 or more , but , now a days , solving 2 problems is quite tough for me , but i will try my best to develop , and thanks for inspiration :D :D jinlifu1999
Well, your dream of solving 3 or more will fulfill in this round :)
Believe me :P
Thanks a lot thanks a lot , if it occurs , i will be a specialist soon , pray for me :)
How's your perform in the contest :P
Really 3 were easy problems. The real competition began with the 4th question. :)
3 problems werre passed pretests but C was caught in main test, if it could be hacked in the contest time, I could debug it, but no one hacked mine, so....
So it seems that you're really unlucky. :(
Hope you can solve 3 next time. :P
Will the problems` background happens on "the thinking bear"?
I don't know either :P
Let's hope and see :P
Who found a palindrome here?
PS. I love palindromes.
919?
Something like that?
Respect for your eagled eyes.
Yet another Chinese round...
I'm interesting in if the round time was scheduled so that it does not overlap with the round on csacademy? Anyway, coordinators, good job!
hope everyone dies in this round :) :> :D xD =) =D <3 (:
Meme
Doki doki literature club!That's a miraculous game……
Oh no, I am alive.
BJLFZS
CONTEST, CONTEST and CONTEST...
RATING, RATING and RATING...
AIM Tech Mini Marathon 1 is an unrated contest.
Then, RATING, TRAINING and RATING ;)
None of this contests are rated for me , so it is sleeping
I hope after this contest my handle becomes like yours and Educational round becomes unrated for me too :)
I also hope after this contest my handle becomes purple and every div.2 becomes unrated for me.
I don't like rated. If I don't do well in this contest, my rating will go down and down...
CONTEST, RATING, TRAINING, CONTEST, RATING, TRAINING ...
thinking bear, moe! baidu's only contribution(LUL
Can't go to WC,so I'm here for CF round.
We suggest you go to WC when necessary during CF round :P
Oh,sorry,WC is an abbreviation form of Winter Camp.
I know that :P
So it's just for fun :P
If it's half an hour ahead, it's perfect.
You can finish this round in half an hour,then go to sleep XD.
Please correct the timing of this contest in the Codeforces Calendar. It is 30 minutes ahead.
Please, wait a minute. I will ask the coordinator to fix that :P
Huge thanks to your correction :P I hadn't noticed that until I saw the calendar.
I have a question to those people who submit Problem A just in 1 minute ..??
A problem takes at least 3-5 minute to read from me, So how could you..??
Do you want to share or give me any tips about this..??
It takes 20 seconds to read the problem for me. Maybe it is because I am reading in Russian and Russian is my native language.
Do you read total problem just in 20 sec...!!!!!
Lol. You don't need to read the whole problem statement) Don't read input/output format, skip useless legend or maybe learn to read faster) But it doesn't matter how fast do you solve first problem. 5 minutes or one minute. You need to solve MORE problems, time isn't the most important thing
Usually it takes me from 30 seconds to 1 minute.
If there are any tips about this, I may provide two: skimming for main keywords and improving your typing speed (for quickly finishing your code).
Thank you man.
Is thank you illegal in codeforces..?? I just have told thank you to Akikaze and some people gave me down vote... Was that necessary..??
By the way, Due to your down vote I just solved 2 problems..
Once Again Thank you MikeMirzayanov for creating this platform..
Go read the examples and notes. That works only on A
Thanks for your advice..man
jinlifu1999
Can we have the editorials please ?
Edit : I wanted the editorial for Round #459. I did not notice and asked it here before the start of this contest. Sorry for the misconception.
Bro, you're asking for editorial before contest!!! Whats the rush??? Enjoy the round.
Sorry mate I wanted the editorials for round #459. I'll go there and comment and delete this one. Sorry :P
Good luck to all!
This is a perfect time for afternoon brazilian students. Thanks
30 minutes after the beginning of the round, super blue blood moon rises..
Use Eclipse Luna for this round and you'll be blessed.
Just Curious to know, Why some contest have Unusual start time.
I wonder how CF appeals to global audience with all the different time zones. BTW In INDIA I prefer 15:35 UTC.
The author lives in China so that time is perfect for him. but not bad for us BTW
Usual start time in UTC+8 is often in the midnight...
This is the first time I used this account to participate in CF. What do I need to watch out for?
Hacks, Beware of Hacks and weak Pretests, always gets people XD LOL!
It's lunar eclipse today while the contest and it's happening after a long time but consecutive two "fully" rated contest is even rare!:p XD lol. Let's hope it's worth missing the eclipse!!
"The scoring distribution will be announced SOON." What does "SOON" mean? :)
After Contest and after testing ^_^
after the rating changes
SOON After the MOON Eclipse !! hehe
4 min before the contest starts and still no score distribution.
it's available
Hope for the short problem statements
Because of the eclipse, I may have to endure the wind on the balcony to participate in this game. I think this is not a pleasant experience :(
hope contest will be rated my first contest wish everone big rating so excited about it thank you MikeMirzayanov for platform codeforces.
why all downvotes
Stop using your ugly big fonts
how to use small font
lmao
how to use big font?
It is available for front-end devs only.
Another contest without scoring distribution...
It's up now
The first time that I'm happy that my flight is delayed! I could participate in a CF round at least! ¯_(ツ)_/¯
Mans rich.
What does "consecutive" means in C?
Does
2 3 3 **. ...
gives the answer of 2 rather than 1?
I think answer should be 1
it took me 37 min to see that k could be 1 in c ugh... the text said for you and your firends that made me thin k>=2
from 1500 to 2500 because of this mistake ...my first life lesson in cf :
READ THE PROBLEM CLEARLY!
Exactly I also thought that I'll always have a friend with me. Took me ages too to get the hack case.
Same lesson learnt :)
one can have 0 friends as well :)
that one must be a programmer
It took two minutes for me!
How to solve D?
topological sort & DP
Can you please elaborate a bit?
DP table brings apprearances each alphabet. Then just fill it in topological order.
First of all check for cycles with Tarjans/Kosaraju's algorithm, if there are any (or self edges), the answer is -1.
Otherwise, create a dynamic programming array dp[N][26], where N is each node.
The value of dp[v][i] is the maximum of dp[u][i] for each neighbour, +1 if the letter i is the letter of the node.
The answer is the maximum dp value.
I did the same thing but was getting wa on test 7.
Code Link: https://pastebin.com/ecFA7Hhi
You mean Kosaraju's algorithm!
You're right, thanks for correcting me.
I've been pronouncing it wrong ever since I learned it. ;d
Ignoring level : Infinity
Hey man. You are calling go() for every node each time it is encountered.
You should only call it if it's not visited yet. Still though, I don't really know why is that solution giving WA. Best of luck fixing the bug though. :)
Ok great, WA was because I was initializing dp with -1, instead of 0. And to remove tle, used topological sorting, then iterative dp.
Link: http://codeforces.com/contest/919/submission/34778654
Well done
I used the following approach: if there is any cycle answer is
-1otherwise use dp, wheredp[i][j]is max path len from vertexicounting characterj. Answer is maximum ofdp[i][j]Very nice round, with good difficulty distribution.
How to solve E?
Hint: Fermat little theorem, Inverse modulo, Chinese Remainder Theorem.
Similar as merging process in merge sort.
Make a table1 = (k^(-1) * b mod p, k), table2 = (a^k mod p, k)
Then find a elements s.t. table1.first == table2.first
what is 'k'? is it [1, b]?
[1,b-1] in table1, [0,b-2] in table2
-> Sorry, [1,p-1] in table1, [0,p-2] in table2
can you please elaborate a bit!
Oh Sorry, my big mistake. Not b, but p.
first, k^(-1) for k = 1, 2, 3, .. , p-1 may different. and since b != 0, we don't have to care n = 0. So for table1, range is [1,p-1]
second, a^k for k = 0,1,2,..,p-2 may different. but k >= p-1, since a^(p-1) = 1, we don't have to care about it.
what might be the 15th testcase in D ? I kept getting tle .
I'm very impressed by the problem E. Very very nice.
how you solved E?
I have just got pretest passed, so solution could be wrong.
Note that 'a' is co-prime to P. So, powers of 'a' form multiplicative group mod P. Let the size of this group be x. So , for each i, ai = ai + x mod P. Also, by euler's formula, we know x is a divisor of P - 1. So, x and P are co-prime.
Now, it comes down to finding the number of j ≤ N (N is max limit), such that j·aj%x = b. This is because aj%x = aj mod P.
This last part can be done using CRT, using the fact that x and P are co-prime.
can you please explain the solution?
k=1 in problem C :)
What was test 15 in Problem D? I was getting a TLE. Is there a better solution than O(26*(V+E))? I did a DFS and stored the counts of all alphabets in a vector and took the maximum of them when I reached a leaf. I did this for every disconnected portion of the graph and took the maximum out of them.
Edit: It wasn't because of cycles, unless my code for detecting cycles was wrong. I had taken care of them beforehand
Do you take care of cycles?
Yes, I took care of cycles before proceeding to do this.
Do you check the condition "Note that x can be equal to y and there can be multiple edges between x and y"?
Yes. I had taken care cycles, before proceeding.
This is something I didn't take care of.... and maybe that's why I got TL on test 15.
:(
I went nuts optimizing my code. I removed the factor of 26, and went to simple DFS (only parameters passed were values u and v). And still TLE!!
Although I had to make 2 DFs functions (1 to check if theres a cycle in that forest and other for ans from that forest).
I dont think its complexity problem- there must be some edge case on cycles. Thats what I can think of. Any suggestions?
Multiedges and you don't use a visited array apparently, thus DFS is not O(V + E) anymore
Thank you. Aside from that, I think Len 's case is the thing. For the given configuration, my loop does goto O(N2). Should have been careful. Thank you :)
I don't think your solution is 26 * (V + E).
Consider test like this
n -> n — 1
n — 1 -> n — 2
...
2 -> 1.
I think you will run O(V) dfses, i-th dfs will visit i vertexes(total V^2).
Why would I run O(V) dfses? I'd just run one dfs for this graph, no? I run multiple dfses only when the graph is disconnected
I don't think that term disconnected can be used for oriented graphs. Everytime if(!vis[i]) will be true because i-th dfs can't visit vertexes > i on this graph.
OH! I get it now. Thanks a lot! Do you reckon it's possible with a modified version of DFS?
Just use memoization.
I have taken care of visited vertices and also I made dfs after topological sorting but still getting TLE in 15th test case
What about complete bipartite graph that has n / 2 vertices in right and n / 2 in left
It was my dream to be purple after this contest, but it seemed that I failed.
Problem C in a nutshell
Anybody has any idea what the 10th testcase for C might be??
magnificent dots in one line / row
That moment when you lock your problem and after that you realize your solution has a bug
Anyone with a hint on how to handle E when x/p is greater than p?
My contest in a nutshell: solved 3 first problems in 10 minutes, got hacked in C and recovered right after, stuck with D for an eternity without knowing exactly what I've done wrong, then going on with E and realize that there wasn't enough time to make it perfect...
UPD: Just realized that my topological solution for D has gone completely wrong. Well the suffering seems to have no end... :<
F: It is right?
I thought the same, but was too lazy to write it. I am sure there is a smaller solution.
I submitted two codes for problem 2 Code 1 in Java: http://codeforces.com/contest/919/submission/34754490 code 2 in C++: http://codeforces.com/contest/919/submission/34757925 Both the codes have exactly same implementation, but, Java code got TLE on pretest 6 whereas C++ Code passed the pretests ! How is this possible?? I don't think fast IO can be a issue here. Can anyone explain why did it happen? Thank you !
because it is JAVA
C++ is faster than Java. 10^6 should be very comfortable in C++, might be tight in Java
why 10^6? for k = 10000 the answer is 10800100 (10^7)
Oh, sorry, I thought he was talking about C.
Got it. But isn't the time limit different for different programming languages?
No, it is like that on some other sites though.
use BufferedReader for reading in Java
I don't think Fast IO can be a issue in problem B.
I wasted much of my time thinking about the reason and then tried C++ and it cleared the pretests immediately ! I don't think That's fair if language really can be the issue. MikeMirzayanov jinlifu1999 KAN wuminyan0607 Please look into my problem and help me. Thank you.
Hmmmmm it seems that it's our mistake. We have tested using language 'D' which seems to be OK. I really have no idea with Java. Sorry for that. :(
BTW, you could come up with a better brute force. You can refer to editorial after system testing.
Sincerely.
My java brute force solution passed in approx 1 / 3rd of TL.
I just tried to resubmit my exact Java code for problem 2 right now and guess what it got accepted. Exact same code gave TLE on pretest 6 but now it cleared all the tests. Link to code 1 giving TLE Link to code 2 accepted Seems like there was some problem with the judge. Unlucky ! :(
On the bound of the TL passing system tests really needs to be lucky :P
You should not have used long, and it would probably have been faster
(CF system is 32bit)
edit: here 34773486 it passed with int in 655ms
Thanks jinlifu1999, Good contest :)
Problem C:
Am I the only one to do binary search with digit dp in B? :D
only 10000 of course brute it
I think Brute force without Fast I/O will give TLE,if you are using i++. Edit:-it seems it won't be problem here
You're reading 5 characters at most.
)
JUST WTF MAN!! I wrote code for E and put it paste.ubuntu.com for sending it after contest (I sent link to myself so I could send code with mobile phone). Now I looked some peoples' code and I see they just COPIED MY CODE. How this happens! Is there any reliable paste site?
My code created 14:22:32: https://paste.ubuntu.com/26495347/
Some examples sent after my code:
http://codeforces.com/contest/919/submission/34769724 LMissher
http://codeforces.com/contest/919/submission/34769669 20155603
I know it's my mistake, but I want them to get disqualified from contest as it is really unfair.
Am I the only one who saw k=100000 in B and spent 1 hour thinking about how to solve it ?
Even if k=100000 you can use the same solution that you use for k=10000. Just ran my code and it was < 1 s.
EDIT: Didn't realize you could literally brute force every number. I had tried that and it seemed too long for k=10000, so I did another sort of brute force enumeration, enumerating in lexicographically smallest order.
Can anyone send a code of problem E?
In problem B, is there a way to estimate the number of digits in the 10000th perfect number?
The number of perfect number with length N is approximately the number of way to put 10 balls into N boxes, which is Combinatoric(N + 9, N) by stars and bars theorem.
Thanks!
To anyone else wondering, check out this code. The number of perfect numbers with digits <= 7 is ~ 7997. Hence the 10,000 perfect number should be of 8 digits.
Do you think the brute force solution would pass the system tests?
I used brute force and it passed.
Almost everyone in my room used brute force. I was talking about the main tests. Logically I could argue that a loop of 10^8 calculations should give TLE. But thats not the case as all the top participants have used brute force.
You can just test k=10000 locally (why are you lazy, it's so simple) and see that result is 10800100 (order 10^7), thus calculating the sum of digits takes at most 8 iterations, 8*10^7 simple operations can pass easily
8 digits is ~10^7
In problem D, the problem statement says a path's value. Path in most cases means the vertices cannot repeat in the path. But the question assumes that the vertices can repeat and hence the answer is -1 if there is a cycle in the graph. I only understood the assumption after looking at the second test case and wasted a lot of time before that. Anyone face this problem?
The last line of the statement says "If the value can be arbitrarily large, output -1 instead.". Should be pretty clear that "arbitrarily large" means infinite path and therefore cycle. Just my opinion.
I shouldn't have to infer it from the question which is in general not expected. I anyway inferred the same after seeing lot of submissions on the question. But that took sometime and nobody should waste time during the contest.
Same here. I'm amazed how everyone else was OK with this. Poor problem statement IMHO.
Whats Happens if I get a TLE on the first pretest of a problem? Do I get a -50 points for it?
(I know that there is no penalty for a WA but am not sure for a TLE)
Note to self: remember that an element's order in Z_p is not necessarily p -1. I failed E because of this. Oh well.
Yeah, quickest examples of non p-1 order elements are 1 and -1
Yup. It was a really silly mistake on my part.
i did a normal dfs on problem D and i count the value after reaching each leaf and get the maximum value between last value and this value,but i got wrong answer. can someone tell me why my solution is wrong?
You may see your judgement protocol after system testing.
OK
Can someone please help me to figure out difference between my solution and this solution. It seems same but my solution is giving TLE.
mathmaniac, we both have done same thing. What is the problem with my solution?
It was easy contest
But, interesting (with hacks).
So problem C says "You need to find k consecutive empty seats in the same row or column and arrange those seats for you and your friends", and "k consecutive empty seats" means "k seats that are consecutive without considering those seats that are occupied" instead of "k seats that are consecutive and they are all empty". That's why I'm hacked...
No, "k consecutive empty seats" means exactly "k seats that are consecutive and they are all empty". You got hacked because you didn't treat the case k=1. For example, on test
Your code prints out 8 instead of 4.
I don't understand why submission http://codeforces.com/contest/919/submission/34754490 although submited at 00:42:27,it is has been run after all other submissions.
Can someone see why this submission TLE for problem D 34771026? or it is just because of time constraint is too tight for Java?
Height of UNLUCKINESS. Got one test case wrong only enough to destroy rank in 4th problem. So remember even one test case after pretest pass is sufficient to kill you temporarily :(. Thanks for the beautifully designed problems in the contest :)
My submission in Java for problem D gets TLE on test 32. Am I missing something? http://codeforces.com/contest/919/submission/34773421
Edit: Somehow this submission of mine gets AC :P http://codeforces.com/contest/919/submission/34778206
The same situation :( It's a pity that any solution on C++ passes...
Great Contest! I did not realise a brute force solution would pass in B and ended up coding and debugging a DFS :P Anyways, a nice lesson for the future.
Why i have a time limit exceded In my C submisiorn C++11 compiler and why i have accepted in c++14 compiler??
Who is OO0OOO00O0O0O0O00OOO0OO ?
http://codeforces.com/profile/OO0OOO00O0OOO0O00OOO0OO
So what is the problem with the D's 15th test case?
I got TLE for 15th test case because there was an issue in my modified DFS. I forgot to put vis array check and it got TLE. After putting the vis check, it got AC.
Hi, I'm not sure if this is the place to put it but please re-evaluate my solutions for contest 919. The system claims that neutron-byte/34741180 is too similar to czommerfelds/34745389. The solution is very simple so it is no surprise it would be similar. Also the first result on Google for "c++ sum of digits" yields the exact same function http://www.sanfoundry.com/cpp-program-display-sum-of-digits/. Thank you. Best, Christian
With all due respect I didn't like the contest that much ... the reason is mostly because problems D and E were not a challenge and this increases the expectation for problem F , and 'F' was only hard to code and didn't have that much theoretical beauty in my opinion Though I surely hope the next rounds jinlifu1999 would come up with will be much better :)
Thanks for your comment.
I think I will come up with better problems (perhaps challenging for Div.1 participants) if there will be "next time". :P
Thanks.