### htoj's blog

By htoj, 5 months ago, ,

Hi Codeforces!

Sorry for being late for the announcement.

I'm glad to introduce to you my first contest Codeforces Round #482 (Div. 2). It will take place on May/14/2018 17:35 (Moscow time).

You will have 5 problems and 2 hours to solve them.

The problems were prepared by me (Quyen Dinh), _Kuroni_ (Trung Dang) and _Shirone_ (Lam Le) with suggestions from FallingStar1709 (Nhat Hoang) and HaiDang2001VN (Dang Huynh). I would like to thank KAN for his great help in checking the problems and giving comments, Tommyr7 for testing all the problems and MikeMirzayanov for the awesome Codeforces and Polygon platform.

Note that the round is rated for everyone with rating below 2100.

In this contest, you will meet Kuro, Shiro and Katie, the three naughty but smart cats who love asking thought-provoking questions. I hope you will find our problems interesting. Good luck to you all!

UPD: Also big thanks to cyand1317 for helping us with the problems and arsor for translating the problems into Russian. Sorry, I forgot you guys.

UPD2: The scoring distribution is 500 — 1000 — 1250 — 1750 — 2250. Have fun!

UPD3: Congratulations to the winners!

Div. 1 & Div. 2:

Our top 5 solved all the problems. Awesome!

Official:

1. mama_budra (solved all problems!)

2. coach.31 (solved all problems!)

3. Illidan

4. ranwen

5. iloveUtaha

Thanks for everything! Here is the editorial.

•
• +101
•

 » 5 months ago, # |   -41 Div-2 the most popular format of Codeforces round.
•  » » 5 months ago, # ^ | ← Rev. 3 →   -56 How did you know? Thanks for the information! You saved my day!
 » 5 months ago, # |   -23 got inspirations from young problemsetter...hope for the best :D
 » 5 months ago, # |   -24 A contest of Vietnamese :)
•  » » 5 months ago, # ^ | ← Rev. 3 →   -83 I'm worried all Asians love math & it's going to be some math/geometry contest FallingStar1709 :3
 » 5 months ago, # | ← Rev. 2 →   -34 Although I have to study for the final exam, I am looking forward to join the contest because I want to increase my rating.
 » 5 months ago, # | ← Rev. 2 →   +82 In my semester break...
•  » » 5 months ago, # ^ |   +61 The only breaks I see are in my switch statements.
•  » » » 5 months ago, # ^ |   -43 Haha...
•  » » » 5 months ago, # ^ |   0 I don't write switches :(
 » 5 months ago, # |   -25 I think the round will be interesting and intriguing
 » 5 months ago, # |   -24 Wow, This is the first time I saw the contest was prepared by Vietnamese people that are same my nationality. Hopefully, everyone will get a high rating.
•  » » 5 months ago, # ^ |   -12 Me too, first time I have seen. I hope the problems will be interesting.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +16 We had some Vietnamese rounds before:
»
5 months ago, # |
Rev. 2   -34

# Is It Rated?

•  » » 5 months ago, # ^ |   -9 The round is rated for everyone with the rating below 2100
 » 5 months ago, # |   -15 Expecting a balanced contest....
 » 5 months ago, # |   +16 ... you will meet Kuro, Shiro and Katie'Katie' is how felines call a special hue only visible to them, I suppose?
•  » » 5 months ago, # ^ |   +3 It is :D
 » 5 months ago, # |   -32 Thanks to the new rules! Now I can participate in div.2 contests!Wish all Candidate Masters (and all participants) can get high rating!
 » 5 months ago, # |   0 Wow, Three cats are a hero to asking the question in this round.
 » 5 months ago, # | ← Rev. 3 →   -14 ‌‌
 » 5 months ago, # | ← Rev. 2 →   +21 Wish u all low ratings like me :(
 » 5 months ago, # |   +4 Me, currently, reloading room's page to find someone, I can hack in problem A
 » 5 months ago, # |   +95 Candidate Masters These Days..
 » 5 months ago, # |   +5 If you think cf pretests are shit, try to get past the pretest 5 of problem B !!!
•  » » 5 months ago, # ^ |   +20 True Evil
•  » » 5 months ago, # ^ |   0 please tell me the pretest 5 of problem B!
•  » » » 5 months ago, # ^ |   +14 It's for the case that one of them has a letter all over the string(like aaaaa) then there's only one turn... Amazing that many people passed this on the first try :/
•  » » » » 5 months ago, # ^ |   0 Why answer of this test is draw? 3 aaaaaaa aaaabcd abcdefg 
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 aaaaaaa -> aaaaaab -> aaaaaac -> aaaaaaa aaaabcd -> aaaaacd -> aaaaaad -> aaaaaaa abcdefg -> aacdefg -> aaadefg -> aaaaefg1st guy and 2nd, both can win, hence draw
•  » » 5 months ago, # ^ |   0 I got it wrong on pretest 10, don't know why.
 » 5 months ago, # |   +488 Welp, the cats are smarter than me.
•  » » 5 months ago, # ^ |   -12 D was trivial, chess is harder :)
•  » » 5 months ago, # ^ |   +15 D problem was okay.but in all honesty . .If I ever see anyone playing a game like that , I will make sure they see meet their maker.
•  » » 5 months ago, # ^ |   0 LOL
 » 5 months ago, # |   +136 u can fold up the pizza and cut it！i think this round should be unrated...
•  » » 5 months ago, # ^ |   0 Exactly! And keeping that in mind I tried for a hack with n=2 (3 pieces) for which 2 cuts are enough but it showed unsuccessful hacking attempt!
•  » » 5 months ago, # ^ |   +3 The shape and size of the pizza slices are the same. Therefore no folds are required.
•  » » » 5 months ago, # ^ |   +12 Pizza with 3 slices of same shape and size can be created using 2 cuts if we fold the pizza by its diameter.
•  » » » 5 months ago, # ^ |   +3 u can cut pizza into 8 slices by cutting and folding 3 times
•  » » » 5 months ago, # ^ |   +3 when number of slices is even，one certainly can fold and get same shape
 » 5 months ago, # |   0 На Этот раз задачки были нормассс, правда не успел
 » 5 months ago, # | ← Rev. 6 →   +33 Hack for B: 3 aaaa aaab bbbb Answer is Draw.(My solution fails this test ;w;(I actually knew of this test but couldn't handle it correctly))
•  » » 5 months ago, # ^ |   0 can you explain why answer is draw?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +4 aaaa — aaab — aaac — aaaaaaab — aaab — aaac — aaaabbbb — bbba — bbbc — bbbb
•  » » 5 months ago, # ^ |   +6 FromaaabWe can get bbbb obviously, so the score is 4.How can we get a score of 4 from the other ones?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +21 aaaa -> aaab -> aaac -> aaaa(second one is same as this one).
•  » » » » 5 months ago, # ^ |   +5 Hmmm, from my understanding the letter has to be different than the one which was at the corresponding position at the original string (without any prior modifications). If I am correct, the expected output should not be Draw."an arbitrary color which is different from the unchanged one"
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +6 This rule applies only for current turn.
•  » » » » » » 5 months ago, # ^ |   +5 While I enjoyed the other problems, the problem statement was confusing in this case. The word "unchanged" only has a meaning when the context is stated, which was not the case here.
•  » » » 5 months ago, # ^ |   0 aaaa aaab aaac aaaa
 » 5 months ago, # |   0 bobo contest gay B suka
•  » » 5 months ago, # ^ |   0 too much dotka for you sir
 » 5 months ago, # |   +1 How to solve D?
•  » » 5 months ago, # ^ |   0 I didn't solve it completely but I think that segment tree storing divisors in each node + some additional data should work.
•  » » 5 months ago, # ^ |   +9 My solution kept sets for each possible k, 1 through 100.000. When adding a number u to the array (type 1) I go through all divisors of u, adding that u to each of sets where it qualifies with O(sqrt(n)) complexity (and O(log(n)) for each insert into a set). If the u is already in the array, I don't do anything (not sure if this improves anything but thought it might be a useful optimalisation).Then, to answer a question for x, k, s, I check if k divides x with the Euclidean algorithm. If not, return -1, if yes, I check if the set for given k is non-empty and if it contains any number not greater than s-x. If so, I can start searching for the optimal solution within this set.When I know which set I'm using and what is the maximal number from this set I can use, I can search bit-by-bit for the best solution, checking for every j-th bit (beginning with the greatest ones) if there exist a number in the set that satisfies both following conditions: 1) Its first j bits are the same as desired (i.e. all different from the x's bits or the same for those which cannot be different, based on previous steps) 2) It's not greater than s-x This can be done in logarythmical time for each bit.
•  » » » 5 months ago, # ^ |   +11 Why do we need Euclidean's algorithm to check if k divides x? I thought mean k|v and k|x?
•  » » » » 5 months ago, # ^ |   +16 Yeah, you're right xD I guess my brain stopped for a while.
•  » » 5 months ago, # ^ |   -11 maybe it can be solved like this:construct a set which will store array valuessince k|gcd(x, v), if this possible then x = p * k and v = q * k, if x%k! = 0 then output is -1,else, iterate over values of , find in set if set, maximise zor to find answer
 » 5 months ago, # | ← Rev. 2 →   0 What should be answer of 3 bbbbaa ccccaa ddddde in B?
•  » » 5 months ago, # ^ |   0 bbbbaa -> bbbbba -> bbbbbc -> bbbbbbccccaa -> ccccca -> cccccd -> ccccccddddde -> dddddf -> ddddde -> ddddddso the answer will be "Draw".
•  » » » 5 months ago, # ^ |   0 Got it ty:)
 » 5 months ago, # | ← Rev. 2 →   0 3 aaaaaacc xxxxkkkk xxxxkkkk ans : Kuro3 aaaaaa abcdxx abcdxx ans : Draw -> Kuro (Sorry My mistake)1 aaaaaaAAAAAA aaaaAAAAAAAA aaAAAAAAAAAA ans : KatieMy B hack data!! Unfortunately, I realized I'm wrong after lock :(
•  » » 5 months ago, # ^ |   +4 I don't get it — isn't the second case supposed to be Kuro?
•  » » 5 months ago, # ^ |   0 why is second test case "Draw"?
•  » » 5 months ago, # ^ | ← Rev. 4 →   0 I got it..
•  » » » 5 months ago, # ^ |   0 aaaaab->aaaaac->aaaaaa
•  » » » 5 months ago, # ^ |   0 aaaaaa -> aaaaab -> aaaaac -> aaaaaa
 » 5 months ago, # |   0 Problem D. Why O(NMlog10^5) gets TLE where N = number of query1 and M = number of query2 ?
•  » » 5 months ago, # ^ |   +3 For example, if N = 50000 and M = 50000, then N * M is a rather big number.
•  » » » 5 months ago, # ^ |   +16 My head just blow up. what a stupid.
 » 5 months ago, # |   +83 Fuck statement B, how could color segment means a single element!!!
•  » » 5 months ago, # ^ |   +25 fuck all problems I think :|
•  » » 5 months ago, # ^ |   +13 I think segment means the interval length >=1
•  » » » 5 months ago, # ^ |   +12 Yes, but not in problem B
•  » » » » 5 months ago, # ^ |   +5 When I was hacked, the more I reading PB again, the more content I can't understand, what is "one color segment"'s real meaning......
 » 5 months ago, # |   +12 hard to understand the statement in pD and pE :(
 » 5 months ago, # | ← Rev. 2 →   +2 RIP rating. PS :- bad problem statements and wrong constraints (in C atleast)
•  » » 5 months ago, # ^ |   0 because n is long?
•  » » » 5 months ago, # ^ |   +2 ya sry , i copy pasted my previous code. fucking silly me!
 » 5 months ago, # |   0 whats wrong with this solution for B? https://ideone.com/Gbvho1 i just found the string with maximum frequency of a character.
 » 5 months ago, # |   -26
 » 5 months ago, # |   0 Just a side note: In C, n >= 1 but n = 1 will not be possible according to constraints.
 » 5 months ago, # |   0 3 aaaa aaab bbbbAnswer is Shiro right?
•  » » 5 months ago, # ^ |   +4 No, it is DrawKuro can do aaaaa -> aaab -> aaac -> aaaa
•  » » 5 months ago, # ^ |   -8 chết chưa bobo suka
 » 5 months ago, # |   0 Could't open the hack page for a long time up to end of the contest!
 » 5 months ago, # |   +5 problem B, what is the answer for this test:5aaaaasI tried to hack a solution with this test and the solution answer was "Draw" but I got "Unsuccessful hacking attempt" !!!
•  » » 5 months ago, # ^ | ← Rev. 2 →   -7 EditedEverone can make aa.aa->ab->aa->ab->ac->aaaa->ab->aa->ab->ac->aaas->aa->as->ab->ac->aa
•  » » » 5 months ago, # ^ |   0 You use only 4 steps
•  » » » 5 months ago, # ^ |   0 In my test n = 5, you are making only 4 moves
•  » » 5 months ago, # ^ |   0 It's "Draw", right??
•  » » 5 months ago, # ^ |   +7 you can do 3 steps and the sequence stay same, aa -> ad -> as -> aaThis doesn't work only if you have to do 1 step
•  » » » 5 months ago, # ^ |   +8 Great, I think I don't have to wait System testing now -_-
•  » » » » 5 months ago, # ^ |   +3 We all don't
•  » » 5 months ago, # ^ |   +5 aa -> ab -> ac -> ad -> ae -> aa aa -> ab -> ac -> ad -> ae -> aa as — > ab -> ac -> ad -> ae -> aa
•  » » » 5 months ago, # ^ |   0 Thanks!
 » 5 months ago, # |   +3 Can someone explain why my hack with test is wrong: 3 aa bb ca. My solution gives "Katie" because of "Each move each of the friends must change exactly one section of the color in her tape to any other color chosen by her.". And solution that I tried to hack gives "Draw"
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 aa->ab->ac->aabb->bc->ba->bbca->cc->ca->cc
•  » » » 5 months ago, # ^ |   0 Thank you very much. I think this test will help many people!)
•  » » 5 months ago, # ^ |   0 it's kinda obvious that this is "draw" because "aa" and "bb" are exactly the same strings and should give the same answer, so.
 » 5 months ago, # |   +6 E: why n = 50 with n3 solution?
•  » » 5 months ago, # ^ |   +15 Maybe they wanted to allow n4 solutions like mine!!
•  » » » 5 months ago, # ^ |   +1 n = 50 allows n5 solution to pass with small constant..
 » 5 months ago, # | ← Rev. 2 →   +138 i really hate CF hacking systema guy that luckily be the first one that could find trivial mistake made by 10 grey/green coder in his room could get more score than a hardworking coder that solve D in last 20 minute.i think CF should limits the hacking attempt by a person (two or three hacking attempt for each problem)
•  » » 5 months ago, # ^ | ← Rev. 2 →   +32 I would say that pretests in div.2 should cover such obvious (but still easy to miss) cases like n = 0 in task A because, yes, nobody should be able to get +1000 points in a couple of minutes by just typing 0 and clicking "Hack".But it doesn't feel right to limit the number of hacking attempts because even multiple hacks for the same problem may require you to read and understand various incorrect solutions and come up with unique testcases against each of them (today this was the case for me: I got 5 successful hacking attempts on problem B but I had to use 5 testcases slightly different from each other). These solutions can be relatively large and tough to understand, so I think that such challenges should be rewarded. After all, it's quite important to be able to read somebody else's code, to grasp the logic behind it and to find a counter example if the underlying logic is wrong. If you want to get a bunch of hacks on harder problems, you will have to sacrifice the time that you could have spent solving other problems (with no reward, i.e. successful hacks, guaranteed), so it's about time/risk management as well.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +11 agreed with you. pretest must cover trivial test case so it won't create unfair advantage to the hackerwhat is the purpose of the problemsetter by not covering trivial case such as n = 0? anyone know that this type of cases will produce lot of unfair hack.unfortunately, there are a lot of contest that did not cover obvious test cases. it is really unfair for people that solved ABCD but lost to a hacker that solve ABC.
•  » » 5 months ago, # ^ |   +5 i think CF should have a hacking point for every problems :)
•  » » 5 months ago, # ^ |   +1 Even people who haven't solved any problem, and hacked as much as 10 codes in problem A are way ahead in standing than those who have solved even a single problem!
 » 5 months ago, # |   0 I think In solving problem D I was going in the right direction , whenever query of type 1 happens , find all its divisors and then make a trie for all those divisors in which we add the binary representation of the number v , but later read the problem statement correctly and found another condition that v + xi <= si . . now no idea how to solve this further keeping this condition in mind :'(. .How did you people solve problem D , i think I was kinda going in the right direction
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I didn't solve it. But my idea : save array as two dimension bool bit[512][512].1) add u to array: bit[ u >> 9][ u & 511 ] = true;2) find answer for x, k, s : 2.1) find that 0 <= ID < 512 that , x ^ (ID << 9) maximal. 2.2) for that ID go all 512 elements of ID's sub array.
•  » » » 5 months ago, # ^ |   0 Вот и решение тоже готовоhttp://codeforces.com/contest/979/submission/38248944
•  » » 5 months ago, # ^ |   0 yes you were. when you are searching the trie, keep in mind that the number you are searching (v) is <= si — xi, and you can verify this relation bitwise
•  » » 5 months ago, # ^ |   0 Your thought process is correct. Let's assume we have BSTs instead of tries. Split the BST in two parts: (elements <= s — x) and (elements > s — x). Solve 706D - Vasiliy's Multiset on the first part. This takes time. (Note: Since a trie is essentially equivalent to a BST, I think this can also be done in O(logn) time, but I'm not sure how to implement this.)
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 You mean 01-trie, right? It's a way, but yes, it can't handle the condition : v + xi <= siInstead, I used std::set in c++, which is more convenient.And you can use the lower_bound function to find the minimal value, And you can solve the problem. If you give every node in 01-trie min[] value, you can also solve the condition.min[node] means the minimal value in the subtree of the node(if you know what I mean).If min[node] + xi > si, the subtree of node will not have any v that satisfy the conditions.Sorry, my English is poor. Hope you'll understand me.
•  » » » 5 months ago, # ^ |   0 I get what you are trying to say but all this did not come to my mind immediately , I just started coding what came to my mind in 5 minutes without even reading carefully , was frustrated because of B , but now that I know my approach was ALMOST correct , I am happy , as ajecc said above , I just have to add very few lines in my 01 trie searching to ensure the condition v <= s — x , . . I can rest in peace now , the contest was a disaster
 » 5 months ago, # |   +20 the problem is shit!!!
•  » » 5 months ago, # ^ |   +5 I can't agree more.
•  » » 5 months ago, # ^ |   0 the truth！
 » 5 months ago, # |   0 My honest respect to contest coordinators, setters, testers and to all who worked so hard to arrange this contest. But the contest experience was not good. Lagging from the start, could not submit test case for hacking purpose at the last 10 minutes of the contest. And when I finally submitted the test case before one minute it successfully uploaded but the status keeps loading and loading, even till now. Such an worst experience for me. Maybe it was not my day.
 » 5 months ago, # |   +5 I can just hack others to get points in this contest.
 » 5 months ago, # |   +8 I suddenly realize in Problem B we have to change per string for exactly n times. No less, no more.Crying...
 » 5 months ago, # |   0 How to solve D? Some kind of divisors search?
 » 5 months ago, # |   +12 Not the best contest =/
 » 5 months ago, # | ← Rev. 2 →   0 Can anyone describe how to solve 979B - Treasure Hunt? Thanks!
•  » » 5 months ago, # ^ |   0 I suppose next. Find letter with maximum M appearances (using map for example). It's Beauty before. One can change N letters in the ribbon. So one can increase M with N. But sum should be not bigger than ribbon length. Let T = min(M + N, ribbon length). Special case is M = ribbon length and N = 1, here one have to change letter to another and T = M - 1. Finally, compare T for men.
•  » » » 5 months ago, # ^ |   0 Holy sh*t I thought that one letter only could be changed to its subsequent on the alphabet. Read over and over again the problem statements guys!
•  » » » 5 months ago, # ^ |   0 I lack of special case, probably it 's pretest 5.
 » 5 months ago, # |   -63 I had a serious discussion with Mike, I have decided that this contest is made unrated
•  » » 5 months ago, # ^ |   0 Lets make this the most down voted comment
 » 5 months ago, # |   +4 problem B???? what are you saying???
 » 5 months ago, # |   +8 Awesome contest, would be much better without hacks :D.
 » 5 months ago, # |   +50 Just my thoughts. For problem A, you could make statement more clear, that two best friends baffled me as n can be 0 or 1. Also this sentence — 'A cut is a straight segment, it might have ends inside or outside the pizza.'. I don't know if I'm only, but it took me some minutes to understand this. I think the word 'outside' here is not needed, it confuses. Or you could give a picture for making everything clear.I hated problem B. Statement is really bad written. For example, look here: 'For example, the ribbon aaaaaaa has the beauty of 7 because its subribbon a appears 7 times, and the ribbon abcdabc has the beauty of 2 because its subribbon abc appears twice.'. You should clarify what does 'appear' mean here. Also 'one color segment' is really confusing...
 » 5 months ago, # |   +35 Unbelievable. I've solved all and have only 300-points advantage concerning the guy who has only solved ABC. I think it isn't fair system, when I can lose the guy who have guessed to hack with the very easy trick, whereas he hasn't solved anything what I even though may try to call "problem", and not "exercise for blue coders".
 » 5 months ago, # |   +8 Another hacking contest
 » 5 months ago, # |   +3 why did you change the statements of problem B without an announcement?
•  » » 5 months ago, # ^ |   +10 Could you give more information, please? I didn't notice that.
•  » » » 5 months ago, # ^ |   0 They changed If there are at least two cats that share the beauty, print "Draw". to If there are at least two cats that share the maximum beauty, print "Draw". without any notification.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Actually you can't even pass sample test 2 if you follow the original instruction. So I think most people can guess what it really means.
 » 5 months ago, # |   +7 why in problem C n can be equal 1???
 » 5 months ago, # |   +71 Codeforces is like:
 » 5 months ago, # | ← Rev. 2 →   0 single line of mis-coding leads me to WA on C and I couldn't never fix it until the end of the contest.
 » 5 months ago, # | ← Rev. 2 →   +59 As problem setters, we intended B to be a problem where people may think a bit out of the box (dealing with odd turns). But we made some serious mistakes (unclear statements, bad pretests) and I would like to apologize to all of the participants this contest. We are currently having a discussion about the aftermath of this contest.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Although I did the contest badly, overall problems are good. But it's also true there's some mistakes on statements :'(
 » 5 months ago, # |   +96
•  » » 5 months ago, # ^ | ← Rev. 2 →   +11 Thanos : Half of submissions of problem B would cease to exists (snap) just like that.
 » 5 months ago, # |   +55
 » 5 months ago, # |   +11 I think the statements are open to different interpretations.That leads to lots of hacks and unhappy participants.
•  » » 5 months ago, # ^ |   0 i agree with u
 » 5 months ago, # | ← Rev. 2 →   +51 No one realizes the case where
•  » » 5 months ago, # ^ |   +13 When you want to hack because you know people will forget about this case...... but you don't know how to hack.
 » 5 months ago, # |   0 but there's one thing...there's one thing...it's wrong contest to judge with :)
 » 5 months ago, # |   +13 No need to make it unrated.Keep it rated. Problem statements were fine. Many people solved the questions so i dont have any complaints
•  » » 5 months ago, # ^ |   0 upvoters : did contest with good scoredownvoters : the othersfight of the most subjective voters
•  » » 5 months ago, # ^ |   +8 The statements weren't fine. Yes, the author's intended solution is to run back and forth between a->b->a. That's what the sample test case description says. Those who understood this way will be judged correct. But there's no problem at all to use a->b->c->a (or a loop longer than 3) under the given description.
 » 5 months ago, # |   0 What should be the answer of this test?2 aabc aaab aaacI believe that is Kuro, but I'm already confused because so many people's code print "Draw".
•  » » 5 months ago, # ^ |   +8 aaab->aaac->aaaa
•  » » » 5 months ago, # ^ |   0 Oh, you're right. ty!
•  » » 5 months ago, # ^ |   0 Draw because in first moveaaacaaacaaadin 2nd moveaaaaaaaaaaaa
 » 5 months ago, # |   +7 Maybe CodeForces should disable hacks in Div.2 Only contests. Some experienced and high-rated (not me :P) candidate masters are solving problems, while others are obsessed with hacks. Inasmuch as there can be a lot of hacks, we obviously see that people solved 2 problems gets a higher rank that contestants solved 3, even 4 problems. There are three options. Make pretests strong so in the contest, it takes less time for the testing solution, and disable hacks. Make the contest full-feedback. Make 12/24 hours hacking phase after the contest. Thanks for reading!
•  » » 5 months ago, # ^ |   +39 Actually there is one more idea. Someone mentioned above somewhere in comments, I felt it was nice. Limit the number of hacks to 3 per question per person.
•  » » 5 months ago, # ^ |   -27 So you can start hacking too. No one is forcing you not to hack. Debugging is also an important asset to have
•  » » » 5 months ago, # ^ |   +10 except that hunting for one if statement is not really debuging
•  » » » 5 months ago, # ^ |   +22 But the motive of contest should not disturbed. Also does it seem good that hacking forms important part than solving. In that way coding clean code for A is important than solving(Or rather attempting) rest??
•  » » » 5 months ago, # ^ |   +20 I also hacked some solutions and understand you that because of your skill is not good enough (do not get offensed from that, I'm just saying it to clarify my idea) you prefer hacking than solving further problems. Thinking on that problems would be better practice, at least it worked for me when I was less skilled. Also don't you think getting points with hacks depends on luck?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 spamming "0" to 10 coder that make such trivial mistake isn't called as debugging.Also, how do you feel when you solved D in the last 20 minute with all complicated code but there are 30 users that don't even attempt to read problem D and get higher score than yourself caused they spammed "0" 10 times.
•  » » 5 months ago, # ^ |   0 http://codeforces.com/blog/entry/59431?#comment-430573i thought disabling hacks won't be a solution. in my opinion, limiting hack attempt or covering obvious test is way better.there are some coder that seriously debugging other ppl code. but what i saw from this contest, most of the people just spamming 0 and click "hack" to get a free 1000 point because no one have started hacking in their room.
 » 5 months ago, # |   0 Please don't tell me the intended complexity for D is O(Q * 128 * log2(105)) (128 = largest number of divisors of numbers from 1 to 10^5).
•  » » 5 months ago, # ^ |   0 you are right for the complexity
 » 5 months ago, # | ← Rev. 2 →   +21 Why my solution 38219517 was Runtime error on test 29 for A? Can you check them please?
•  » » 5 months ago, # ^ |   +5 return !puts("0"); Your solution returns exit code 1 on n=0.
•  » » 5 months ago, # ^ |   0 Don't know why downvotes for my previous comment, but puts returns a non-negative value (on success). In your case puts returns 0 and your code makes return !0, i.e. return 1. Any non-zero exit code from the main process of a solution is treated as a runtime error.
 » 5 months ago, # |   +4 If you fold the pizza it takes less cuts
•  » » 5 months ago, # ^ |   +11 Do you have any test?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 n=7. Better answer = 3 if stacking/folding is allowed.
•  » » » » 5 months ago, # ^ |   0 if folding allowed then best answer for any n should be 1
 » 5 months ago, # |   +1 For C, can an input have n = 1 ? If n == 1 then x and y can not be distinct. But the range for n starts from 1 :P
•  » » 5 months ago, # ^ |   0 I asked about it and the answer was no.
 » 5 months ago, # |   +9 Came across one strange detail while viewing results for my room. The problem is said to be locked one second after it was hacked: https://pasteboard.co/HlaAgFu.png. We can't lock the problem if it doesn't have "pretests passed" status when we click "Lock", can we?
•  » » 5 months ago, # ^ |   0 I hope he is able to resubmit after that hack and not hack others xD
 » 5 months ago, # |   +30 Brute AC on D: 38234986.
 » 5 months ago, # |   0 you can use sigma(n/k)*q to solve D,so interesting
 » 5 months ago, # |   +5 When I read the problems, I misread a part of problem D's statement. I understood that and not . How to solve that version of the problem?PS: I have a solution, which is a bit complicated (not too complicated, but still) so any solution you can think of will be appreciated.
 » 5 months ago, # |   +1 Jonny, they are in the trees!!!
 » 5 months ago, # |   0
 » 5 months ago, # |   0 What is test 27 in C?
 » 5 months ago, # |   +1 How to solve this generalization of the problem C:Given an undirected graph with n nodes and m edges. How many are (u, v) pairs such that there exists a shortest path from u to v that it doesn't visit y if it visited x before? x and y are given.
 » 5 months ago, # |   +17 http://codeforces.com/contest/979/submission/38243030AC on D with O(n^2) and simple cutting..
•  » » 5 months ago, # ^ |   +6 http://codeforces.com/contest/979/submission/38236267 Не думал решение — такое простое!!!!!
 » 5 months ago, # |   +1 Wow! Problem B was a devastation! So many people (me included!) got it wrong on system tests!
 » 5 months ago, # |   0 Can someone point out why my solution to C fails? Link
•  » » 5 months ago, # ^ |   +4 ll(1000000*1000000) isn't 1e12. type conversion occurs after overflow.
•  » » 5 months ago, # ^ |   +6 (ll)(n*n) is wrong
 » 5 months ago, # |   0 Nice problems, Thanks!
 » 5 months ago, # | ← Rev. 2 →   0 Can anyone tell me why LINK is wrong for C?
•  » » 5 months ago, # ^ |   0 int ans=n*(n-1); overflow :(
•  » » » 5 months ago, # ^ |   0 I have defined int as long long int
•  » » » » 5 months ago, # ^ |   +3 oh i see..
•  » » » » » 5 months ago, # ^ |   0 Please sir can u tell whats wrong?
•  » » » » » 5 months ago, # ^ |   0 Leave it i understood my mistake
 » 5 months ago, # |   0 Problem C TLE. Is this 38236023 not O(n)? Poor python coder!
•  » » 5 months ago, # ^ | ← Rev. 2 →   +7 Because of passing vectors and arrays to recursive functions.So, you should declare those structures as global structures, to be able to use them without passing them to the functions
•  » » 5 months ago, # ^ |   +7 I have just looked at your newest submission. SpoilerYou don't need to pass "visited" to the function, it's enough to keep this array globaly declared.And for the vector "path", you can do the following:Each node you need to push it in the vector, push it. Then if this node don't lead to the destination, you just need to pop it at the end of the "dfs" function.
•  » » » 5 months ago, # ^ |   +4 Thanks for keeping a constant check. I would never have thought of these optimizations.
 » 5 months ago, # |   0 Welcome to HackForces! I think letting the round rated for everyone with rating below 2100 is a wrong decision.
•  » » 5 months ago, # ^ |   0 If they don't hack you then you are wrong anyway bruh.
•  » » » 5 months ago, # ^ |   0 I just think "DIV2 only" round is not suitable for purple players.
•  » » » » 5 months ago, # ^ |   0 And fewer people will take DIV1 round.
 » 5 months ago, # |   +1 Can someone explain what main test 79 in problem B was. Since the test case is too big, any alternate small test case with same logic?
•  » » 5 months ago, # ^ |   0 I've tried the case3 aaaa aaab bbbb=> Drawfrom an earlier reply which works like aaaa -> aaab -> aaac -> aaaa instead of a->b->a->b
•  » » » 5 months ago, # ^ |   0 Got the error ! My answer to this case is Shiro ! Thanks a lot.
 » 5 months ago, # | ← Rev. 2 →   +18 Why dose this solution (which is O(n^2)) get passed..http://codeforces.com/problemset/submission/979/38236267This generator can hack it.. #include using namespace std; int main(){ int q=100000; printf("%d\n",q); printf("1 1\n"); for(int i=1;i
 » 5 months ago, # |   +8 I would like to point out the test cases of D is too weak. It seems to me most of the cases are random cases and does not target for a specific range of values.My solution is to use trie for ki <= 400 queries (build a trie for each ki), otherwise, use O(n*si/ki) brute force. 38238355I tried to mess around the constant 400 to see if a faster runtime will be achieved. And I accidentally found that using a single trie to handle queries of ki = 1 and brute force all other ki >= 2 queries can pass all tests. 38260678 I believe brute force solution for ki = 2 should result in TLE like ki = 1. Consider the brute force part alone, ki = 1 should run about half speed when ki = 2. However, my solution pass with 249ms which is unexpectedly low.Also, it is reported that some O(n^2) brute force solutions with cutting can easily get accepted. See: I hope the problem authors can investigate this issue and make stronger cases for future rounds. Nevertheless, I enjoyed solving this problem. :) Note: My pure brute force solution TLE on 14 38260748
•  » » 5 months ago, # ^ |   0 Sorry for the weak test cases of problem D. We did not think much about brute force solutions with optimization so the test cases were not tough enough. We will absolutely make progress next time. Thanks for pointing it out.
 » 5 months ago, # | ← Rev. 2 →   0 Why am I getting TLE for O(n) solution in Java ? (problem C) http://codeforces.com/contest/979/submission/38266793
•  » » 5 months ago, # ^ |   0 get(int) method of LinkedList is . You should use ArrayList or similar instead.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yeah! :D I almost forgot this. I can use ArrayList instead.. Thanks alot.
 » 5 months ago, # | ← Rev. 2 →   0 s