Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

jinlifu1999's blog

By jinlifu1999, 2 years ago, ,

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, gritukan, neckbosov 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

1. OO0OOO00O0O0O0O00OOO0OO (Solved all 6 problems and got 4 successful hacking attempts)

2. pannibal (Solved all 6 problems)

3. sasasagagaga

4. velity

5. Hacker_White

6. Ren_shimosawa

8. just_soso

9. jijiang

10. wzz

Div. 1 & Div. 2

• +402

 » 2 years ago, # |   +17 two consecutive rated rounds that's good__
•  » » 2 years ago, # ^ | ← Rev. 2 →   +10 Hope you enjoy this round :P
•  » » 2 years ago, # ^ |   -8 not, if you decrease your rate.
 » 2 years ago, # |   +9 What's the name of the cute character? :P
•  » » 2 years ago, # ^ |   +2 It's something like "The thinking bear".To be honest, I'm not sure about the English name of that character. :)
•  » » 2 years ago, # ^ |   +7 I think it is from uoj.ac. At least that is where I've seen it.
•  » » » 2 years ago, # ^ |   0 GREAT I will give you an upvote :P
•  » » » 2 years ago, # ^ |   +12 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).
 » 2 years ago, # |   +7 Good time for East Asia participants！
•  » » 2 years ago, # ^ |   0 Why so [user:@Phos] ?
•  » » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   +6 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
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 No pictures in problem statement. :PSo you can focus on solving problems. :P
•  » » » 2 years ago, # ^ |   +5 And so that pages can load more quickly. :)
 » 2 years ago, # |   -26 1 upvote = 1 pray
•  » » 2 years ago, # ^ |   0 1 downvote = ?
 » 2 years ago, # |   +24 We will try to bear this round too.
•  » » 2 years ago, # ^ |   +30 Your pun is soo POLARizingIt is borderline un BEARable :P
 » 2 years ago, # |   0 I hope the problem statements are as short. Good luck to all!
 » 2 years ago, # |   0
 » 2 years ago, # |   -7 This time, my handle will definitely turn into "Green" . Nobody can stop me !
•  » » 2 years ago, # ^ | ← Rev. 2 →   +8 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
•  » » » 2 years ago, # ^ |   +19 Regularly solving only A and B is enough to become green.
•  » » » » 2 years ago, # ^ |   0 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.
•  » » » » » 2 years ago, # ^ |   +6 If he solved four problems he will probably become specialist in one round! This is not impossible. worse did something like that.
•  » » » » » » 2 years ago, # ^ |   0 OMG!! Thanks for sharing that
•  » » » » » » » 2 years ago, # ^ |   +6 Thank you guys ! Specially Knight_of_Thirteen and bharath. I am looking forward to solve A and B.
•  » » » » » » » » 2 years ago, # ^ |   0 emmmmmm looking forward to doing something
•  » » » » » » » » » 2 years ago, # ^ |   0 Opps
•  » » » » 2 years ago, # ^ |   +7 I have solved A and B.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +1 Great, hope they will pass system tests :)
•  » » » » » » 2 years ago, # ^ |   +1 I hope they will pass, but struggling to solve C. :(
 » 2 years ago, # |   +1 Cute drawings!
 » 2 years ago, # |   +4 Another cute images contest!
 » 2 years ago, # |   +11 I think that adrozdova is very old nick of demon1999) Why do you use it?
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   0 More than one year?)
•  » » 2 years ago, # ^ |   +18 Maybe testers' Polygon handles are directly copied here — grikukan is also gritukan's former handle.
 » 2 years ago, # |   0 CS Academy Round #67 starts right after the round, is there something to be done about this?
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 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
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 C137 SuperJava It is delayed for 30 minutes
 » 2 years ago, # |   +24 Is this round a Chinese round?
 » 2 years ago, # |   +8 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
•  » » 2 years ago, # ^ |   +6 But it is a div2-only one :P
 » 2 years ago, # | ← Rev. 4 →   +6 I hope the difficulty gradient for this contest will be somewhat better than the last one. 2 rated contest in a row. ✌
 » 2 years ago, # |   +52 "The scoring distribution will be announced soon."Lies, lies everywhere.
 » 2 years ago, # |   +14 Support teacher Jin OVO 资磁靳老师
•  » » 2 years ago, # ^ |   0 OVOThanks :P
 » 2 years ago, # |   +5 solved 2 problems and got 50+ ratings :) , seems cool :D:D
•  » » 2 years ago, # ^ |   0 Don't you think of solving 3 or more :P
•  » » » 2 years ago, # ^ |   +3 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
•  » » » » 2 years ago, # ^ |   +2 Well, your dream of solving 3 or more will fulfill in this round :)Believe me :P
•  » » » » » 2 years ago, # ^ |   0 Thanks a lot thanks a lot , if it occurs , i will be a specialist soon , pray for me :)
•  » » » » » » 2 years ago, # ^ |   0 How's your perform in the contest :P
•  » » » » » » » 2 years ago, # ^ |   0 Really 3 were easy problems. The real competition began with the 4th question. :)
•  » » » » » » » 2 years ago, # ^ |   +5 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....
•  » » » » » » » » 2 years ago, # ^ |   0 So it seems that you're really unlucky. :(Hope you can solve 3 next time. :P
 » 2 years ago, # |   0 I hope the problem statements would be as short and concise as the announcement. Good luck to all!
 » 2 years ago, # |   0 Will the problems background happens on "the thinking bear"?
•  » » 2 years ago, # ^ |   0 I don't know either :PLet's hope and see :P
 » 2 years ago, # |   -13 Who found a palindrome here?PS. I love palindromes.
•  » » 2 years ago, # ^ |   +12 919?Something like that?
•  » » » 2 years ago, # ^ |   +27 Respect for your eagled eyes.
 » 2 years ago, # |   0 Yet another Chinese round...
 » 2 years ago, # |   0 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!
 » 2 years ago, # |   -24 hope everyone dies in this round :) :> :D xD =) =D <3 (:
•  » » 2 years ago, # ^ | ← Rev. 2 →   -57 Meme
•  » » » 2 years ago, # ^ |   -8 Doki doki literature club!That's a miraculous game……
•  » » » 2 years ago, # ^ |   -33 i know im dead inside and i hate my life and i suffer want to hear how my soul died and how demons took over my body? everyone bullies me at school and i keep teling them i will some day achieve great powers with which i will seek revenge they call me gay for some reason so with these powers i will kill all gay people and hang their bodies at bullies' doors and laugh ha ah ha ha at them
•  » » » 2 years ago, # ^ |   -33 and you bertter delete that \gay anime profile or i will tell my dad who owns this website to get you banned
•  » » » 2 years ago, # ^ |   0 Oh no, I am alive.
 » 2 years ago, # |   0 BJLFZS
 » 2 years ago, # |   +18 CONTEST, CONTEST and CONTEST...
•  » » 2 years ago, # ^ |   +30 RATING, RATING and RATING...
•  » » » 2 years ago, # ^ |   +18 AIM Tech Mini Marathon 1 is an unrated contest.
•  » » » » 2 years ago, # ^ |   +33 Then, RATING, TRAINING and RATING ;)
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +30 None of this contests are rated for me , so it is sleeping
•  » » » » » » 2 years ago, # ^ |   +11 I hope after this contest my handle becomes like yours and Educational round becomes unrated for me too :)
•  » » » » » » » 2 years ago, # ^ |   +3 I also hope after this contest my handle becomes purple and every div.2 becomes unrated for me.
•  » » » » » » » » 2 years ago, # ^ |   0 I don't like rated. If I don't do well in this contest, my rating will go down and down...
•  » » » » » 2 years ago, # ^ |   +3 CONTEST, RATING, TRAINING, CONTEST, RATING, TRAINING ...
 » 2 years ago, # |   +5 thinking bear, moe! baidu's only contribution(LUL
 » 2 years ago, # |   +17 Can't go to WC,so I'm here for CF round.
•  » » 2 years ago, # ^ |   +31 We suggest you go to WC when necessary during CF round :P
•  » » » 2 years ago, # ^ |   0 Oh,sorry,WC is an abbreviation form of Winter Camp.
•  » » » » 2 years ago, # ^ |   +14 I know that :PSo it's just for fun :P
 » 2 years ago, # |   0 If it's half an hour ahead, it's perfect.
•  » » 2 years ago, # ^ |   +11 You can finish this round in half an hour,then go to sleep XD.
 » 2 years ago, # |   +1 Please correct the timing of this contest in the Codeforces Calendar. It is 30 minutes ahead.
•  » » 2 years ago, # ^ |   0 Please, wait a minute. I will ask the coordinator to fix that :PHuge thanks to your correction :P I hadn't noticed that until I saw the calendar.
 » 2 years ago, # |   0 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..??
•  » » 2 years ago, # ^ |   +13 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.
•  » » » 2 years ago, # ^ |   0 Do you read total problem just in 20 sec...!!!!!
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +22 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
•  » » 2 years ago, # ^ |   0 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).
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -6 Thank you man.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 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..
•  » » 2 years ago, # ^ |   +3 Go read the examples and notes. That works only on A
•  » » » 2 years ago, # ^ |   0 Thanks for your advice..man
 » 2 years ago, # | ← Rev. 2 →   +21 jinlifu1999Can 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.
•  » » 2 years ago, # ^ |   +20 Bro, you're asking for editorial before contest!!! Whats the rush??? Enjoy the round.
•  » » » 2 years ago, # ^ |   +17 Sorry mate I wanted the editorials for round #459. I'll go there and comment and delete this one. Sorry :P
 » 2 years ago, # |   0 Good luck to all!
 » 2 years ago, # |   0 Is main character of this round this bear ?
 » 2 years ago, # |   +6 This is a perfect time for afternoon brazilian students. Thanks
 » 2 years ago, # |   +10 30 minutes after the beginning of the round, super blue blood moon rises..
•  » » 2 years ago, # ^ |   +38 Use Eclipse Luna for this round and you'll be blessed.
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 The author lives in China so that time is perfect for him. but not bad for us BTW
•  » » 2 years ago, # ^ |   0 Usual start time in UTC+8 is often in the midnight...
 » 2 years ago, # |   0
 » 2 years ago, # |   0 This is the first time I used this account to participate in CF. What do I need to watch out for?
•  » » 2 years ago, # ^ |   +1 Hacks, Beware of Hacks and weak Pretests, always gets people XD LOL!
 » 2 years ago, # |   +2 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!!
 » 2 years ago, # |   +2 "The scoring distribution will be announced SOON." What does "SOON" mean? :)
•  » » 2 years ago, # ^ |   +1 After Contest and after testing ^_^
•  » » » 2 years ago, # ^ |   +1 after the rating changes
•  » » 2 years ago, # ^ |   0 SOON After the MOON Eclipse !! hehe
•  » » 2 years ago, # ^ |   0 4 min before the contest starts and still no score distribution.
•  » » 2 years ago, # ^ |   0 it's available
 » 2 years ago, # |   0 Hope for the short problem statements
 » 2 years ago, # | ← Rev. 2 →   0 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 :(
»
2 years ago, # |
-35

hope contest will be rated my first contest wish everone big rating so excited about it thank you MikeMirzayanov for platform codeforces.

• »
»
2 years ago, # ^ |
-25

•  » » » 2 years ago, # ^ |   +6 Stop using your ugly big fonts
• »
»
»
»
2 years ago, # ^ |
+19

how to use small font

•  » » » » » 2 years ago, # ^ |   +1 lmao
•  » » » » » 2 years ago, # ^ |   +3 how to use big font?
• »
»
»
»
»
»
2 years ago, # ^ |
Rev. 2   0

It is available for front-end devs only.

 » 2 years ago, # |   +4 Another contest without scoring distribution...
•  » » 2 years ago, # ^ |   0 It's up now
 » 2 years ago, # |   0 waiting....
 » 2 years ago, # |   0 is registration time end?
•  » » 2 years ago, # ^ |   0 YES, you need to register 1 day earlier.
•  » » » 2 years ago, # ^ |   0 Thanks A lot
 » 2 years ago, # |   +14 The first time that I'm happy that my flight is delayed! I could participate in a CF round at least! ¯_(ツ)_/¯
•  » » 2 years ago, # ^ |   +5 Mans rich.
•  » » » 2 years ago, # ^ |   +9
 » 2 years ago, # |   0 What does "consecutive" means in C?Does 2 3 3 **. ... gives the answer of 2 rather than 1?
•  » » 2 years ago, # ^ |   0 I think answer should be 1
 » 2 years ago, # |   +14 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!
•  » » 2 years ago, # ^ |   0 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 :)
•  » » 2 years ago, # ^ |   0 one can have 0 friends as well :)
•  » » » 2 years ago, # ^ |   +1 that one must be a programmer
•  » » » » 2 years ago, # ^ |   0 yeah!
•  » » 2 years ago, # ^ |   0 It took two minutes for me!
 » 2 years ago, # |   +7 How to solve D?
•  » » 2 years ago, # ^ |   +5 topological sort & DP
•  » » » 2 years ago, # ^ |   0 Can you please elaborate a bit?
•  » » » » 2 years ago, # ^ |   0 DP table brings apprearances each alphabet. Then just fill it in topological order.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +7 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.
•  » » » 2 years ago, # ^ |   0 I did the same thing but was getting wa on test 7.Code Link: https://pastebin.com/ecFA7Hhi
•  » » » 2 years ago, # ^ |   0 You mean Kosaraju's algorithm!
•  » » » » 2 years ago, # ^ |   +1 You're right, thanks for correcting me.I've been pronouncing it wrong ever since I learned it. ;d
•  » » » » » 2 years ago, # ^ |   0 Thank you for explaining your approach!
•  » » » » » 2 years ago, # ^ |   0 Ignoring level : Infinity
•  » » » » » » 2 years ago, # ^ |   0 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. :)
•  » » » » » » » 2 years ago, # ^ |   +3 Ok great, WA was because I was initializing dp with -1, instead of 0. And to remove tle, used topological sorting, then iterative dp.
•  » » » » » » » » 2 years ago, # ^ |   +1 Well done
•  » » 2 years ago, # ^ |   0 i don't know weather it is correct or not. for each alphabet do a dfs.at each node select the child which gives maximum count for current alphabet and return it. if there's a cycle ans = -1.
•  » » 2 years ago, # ^ |   0 I used the following approach: if there is any cycle answer is -1 otherwise use dp, where dp[i][j] is max path len from vertex i counting character j. Answer is maximum of dp[i][j]
 » 2 years ago, # |   +6 Very nice round, with good difficulty distribution.
 » 2 years ago, # |   +10 How to solve E?
•  » » 2 years ago, # ^ |   +5 Hint: Fermat little theorem, Inverse modulo, Chinese Remainder Theorem.
•  » » 2 years ago, # ^ |   0 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
•  » » » 2 years ago, # ^ |   0 what is 'k'? is it [1, b]?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 [1,b-1] in table1, [0,b-2] in table2-> Sorry, [1,p-1] in table1, [0,p-2] in table2
•  » » » » » 2 years ago, # ^ |   0 can you please elaborate a bit!
•  » » » » » » 2 years ago, # ^ | ← Rev. 3 →   0 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.
 » 2 years ago, # |   0 what might be the 15th testcase in D ? I kept getting tle .
•  » » 2 years ago, # ^ |   0 indeed....
 » 2 years ago, # |   -6 Time limit for problem Div2D is a bit tight ?
 » 2 years ago, # |   +15 I'm very impressed by the problem E. Very very nice.
•  » » 2 years ago, # ^ |   +3 how you solved E?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ |   0 can you please explain the solution?
 » 2 years ago, # |   +41 k=1 in problem C :)
 » 2 years ago, # | ← Rev. 2 →   +1 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
•  » » 2 years ago, # ^ |   0 Do you take care of cycles?
•  » » » 2 years ago, # ^ |   0 Yes, I took care of cycles before proceeding to do this.
•  » » 2 years ago, # ^ |   +1 Do you check the condition "Note that x can be equal to y and there can be multiple edges between x and y"?
•  » » » 2 years ago, # ^ |   0 Yes. I had taken care cycles, before proceeding.
•  » » » 2 years ago, # ^ |   0 This is something I didn't take care of.... and maybe that's why I got TL on test 15.
•  » » » » 2 years ago, # ^ |   0 :(
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » » 2 years ago, # ^ |   0 Multiedges and you don't use a visited array apparently, thus DFS is not O(V + E) anymore
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 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 :)
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » » 2 years ago, # ^ |   0 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
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 2 years ago, # ^ |   0 OH! I get it now. Thanks a lot! Do you reckon it's possible with a modified version of DFS?
•  » » » » » » 2 years ago, # ^ |   0 Just use memoization.
•  » » » 2 years ago, # ^ |   0 I have taken care of visited vertices and also I made dfs after topological sorting but still getting TLE in 15th test case
•  » » 2 years ago, # ^ |   0 What about complete bipartite graph that has n / 2 vertices in right and n / 2 in left
 » 2 years ago, # |   +4 It was my dream to be purple after this contest, but it seemed that I failed.
 » 2 years ago, # | ← Rev. 2 →   +40 Problem C in a nutshell
•  » » 2 years ago, # ^ |   0 Anybody has any idea what the 10th testcase for C might be??
•  » » » 2 years ago, # ^ |   0 magnificent dots in one line / row
•  » » 2 years ago, # ^ |   0 My god this is really accurate. Got hacked.
 » 2 years ago, # |   +10 That moment when you lock your problem and after that you realize your solution has a bug
•  » » 2 years ago, # ^ |   0 My solution got hacked 10 second after I locked the problem. Couldn't correct it even though I knew what the hack case was :(
 » 2 years ago, # | ← Rev. 2 →   +1 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... :<
 » 2 years ago, # |   +5
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I thought the same, but was too lazy to write it. I am sure there is a smaller solution.
 » 2 years ago, # |   0 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 !
•  » » 2 years ago, # ^ |   +4 because it is JAVA
•  » » 2 years ago, # ^ |   0 C++ is faster than Java. 10^6 should be very comfortable in C++, might be tight in Java
•  » » » 2 years ago, # ^ |   0 10^6 is fast enough in Java as well. I primarily use Java and have done many questions with such constraints but it was never an issue. Today is the first time I faced this anomaly
•  » » » 2 years ago, # ^ |   +1 why 10^6? for k = 10000 the answer is 10800100 (10^7)
•  » » » » 2 years ago, # ^ |   0 Oh, sorry, I thought he was talking about C.
•  » » » » 2 years ago, # ^ |   0 Got it. But isn't the time limit different for different programming languages?
•  » » » » » 2 years ago, # ^ |   0 No, it is like that on some other sites though.
•  » » 2 years ago, # ^ |   0 use BufferedReader for reading in Java
•  » » » 2 years ago, # ^ |   +1 I don't think Fast IO can be a issue in problem B.
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   +1 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.
•  » » » » 2 years ago, # ^ |   0 My java brute force solution passed in approx 1 / 3rd of TL.
•  » » » » » 2 years ago, # ^ |   0 My same code that gave TLE during the contest on prestest 6 is now getting accepted without a single change in the code. Seems like some trouble with the judge, neverthless unlucky me :(
•  » » » » 2 years ago, # ^ |   0 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 ! :(
•  » » » » » 2 years ago, # ^ |   0 On the bound of the TL passing system tests really needs to be lucky :P
•  » » » » » » 2 years ago, # ^ |   0 Bad luck comes in all forms :P Haha, thanks for the wonderful contest BTW :)
•  » » » 2 years ago, # ^ | ← Rev. 5 →   +3 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
 » 2 years ago, # |   +21 Thanks jinlifu1999, Good contest :)
 » 2 years ago, # |   +9 Problem C:
 » 2 years ago, # | ← Rev. 2 →   0 Am I the only one to do binary search with digit dp in B? :D
•  » » 2 years ago, # ^ |   0 only 10000 of course brute it
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 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
•  » » » 2 years ago, # ^ |   +5 You're reading 5 characters at most.
 » 2 years ago, # |   +5 ![Summary of the contest]()
 » 2 years ago, # |   +67 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: I know it's my mistake, but I want them to get disqualified from contest as it is really unfair.
 » 2 years ago, # |   +1 Am I the only one who saw k=100000 in B and spent 1 hour thinking about how to solve it ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
 » 2 years ago, # |   0 Can anyone send a code of problem E?
 » 2 years ago, # |   0 A contest for memory, First time to solve problem in the last minute
 » 2 years ago, # | ← Rev. 2 →   0 In problem B, is there a way to estimate the number of digits in the 10000th perfect number?
•  » » 2 years ago, # ^ |   +9 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.
•  » » » 2 years ago, # ^ |   0 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?
•  » » » » 2 years ago, # ^ |   0 I used brute force and it passed.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 2 years ago, # ^ |   0 but it should give TLE .. IT MIGHT BE THAT IN ACTUAL TEST CASE K<10000
•  » » » » » » 2 years ago, # ^ |   0 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
•  » » » » 2 years ago, # ^ |   +1 8 digits is ~10^7
 » 2 years ago, # |   +16 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?
•  » » 2 years ago, # ^ |   +2 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.
•  » » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   0 Same here. I'm amazed how everyone else was OK with this. Poor problem statement IMHO.
 » 2 years ago, # |   0 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)
•  » » 2 years ago, # ^ |   0 No.
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 Yeah, quickest examples of non p-1 order elements are 1 and -1
•  » » » 2 years ago, # ^ |   0 Yup. It was a really silly mistake on my part.
 » 2 years ago, # |   0 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?
•  » » 2 years ago, # ^ |   0 You may see your judgement protocol after system testing.
•  » » » 2 years ago, # ^ |   0 OK
 » 2 years ago, # |   0 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?
 » 2 years ago, # |   -10 It was easy contest
•  » » 2 years ago, # ^ |   0 But, interesting (with hacks).
•  » » » 2 years ago, # ^ |   0 I join it after 45 minutes passed. so, I couldn't do hacking
 » 2 years ago, # |   0 jinlifu1999 Thankyou. This was very good contest and good difficulty distribution.
 » 2 years ago, # |   0 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...
•  » » 2 years ago, # ^ |   0 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 2 2 1 .. .. `Your code prints out 8 instead of 4.
•  » » » 2 years ago, # ^ |   0 Thanks.
 » 2 years ago, # | ← Rev. 2 →   +3 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.
 » 2 years ago, # |   +7 Can someone see why this submission TLE for problem D 34771026? or it is just because of time constraint is too tight for Java?
 » 2 years ago, # |   0 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 :)
 » 2 years ago, # |   0 nyc contest. short and sweet problem statements. and it was exciting.
 » 2 years ago, # |   0 Recently, a student of my college was found cheating and copying codes in short contests from ideone.com https://discuss.codechef.com/questions/122305/ratings-over-learningAfter realising that I was not making any progress on solving problem D, I thought of checking ideone and see whether it worked. I got a solution for problem D which was compiled as public while 20-25 minutes were left for the contest to end. I saved the solution locally.I just submitted the code, and it resulted AC. A humble request to all, please make sure your codes are private at ideone and other such online IDEs.My suggestion would be to use Codechef ide or CF custom invocation.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 @rohitthapliyal, thanks for the issue. Dear Comrades when you use ideone please click on the glasses to make it private. Thanks.Image on how to protect your codes on ideoneEdit: BTW, how do you add image to your comments? Thanks.
 » 2 years ago, # | ← Rev. 4 →   +7 My submission in Java for problem D gets TLE on test 32. Am I missing something? http://codeforces.com/contest/919/submission/34773421Edit: Somehow this submission of mine gets AC :P http://codeforces.com/contest/919/submission/34778206
•  » » 2 years ago, # ^ |   0 The same situation :( It's a pity that any solution on C++ passes...
 » 2 years ago, # |   0 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.
 » 2 years ago, # |   +5 Why i have a time limit exceded In my C submisiorn C++11 compiler and why i have accepted in c++14 compiler??
 » 2 years ago, # |   0 Who is OO0OOO00O0O0O0O00OOO0OO ?
•  » » 2 years ago, # ^ |   0
 » 2 years ago, # |   0 So what is the problem with the D's 15th test case?
•  » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   +1 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
 » 2 years ago, # | ← Rev. 2 →   +8 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 :)
•  » » 2 years ago, # ^ |   +9 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". :PThanks.