Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

GreenGrape's blog

By GreenGrape, 3 years ago,

Less than 24 hours till the round?
And still no announcement?
How come, Mr. Grape?

Codeforces Round #471 will take part on Friday at 19:35 MSK. Note that the duration is a bit longer that usual.

The round will be rated for all division 2 participants. Division 1 is welcome aswell :)

My gratitude to Grisha (vintage_Vlad_Makeev) for round coordination, Ildar (300iq), Nikita (FalseMirror), Azat (ismagilov.code), Eugene (rek) and Oleg (xen) for testing and Mike (MikeMirzayanov) for awesome Codeforces and Polygon.

There will be six problems with the following scoring:
500 — 1000 — 1500 — 2000 — 2500 — 3000

UPD. System testing is over. Editorial

Congratz to the winners!

Div. 2:

Div. 1 (unofficial):

• +210

 » 3 years ago, # | ← Rev. 2 →   0 A BIT longer
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # | ← Rev. 2 →   +32 Why are registrations starting so late?
 » 3 years ago, # |   +5 i hope a lot of Hacking <3
 » 3 years ago, # |   0 It is raining contests...!!!
•  » » 3 years ago, # ^ |   -10 Hallelujah?
•  » » » 3 years ago, # ^ |   +5 I think, In your contest, problems are easy to solve but difficult to understand..
•  » » » » 3 years ago, # ^ |   0 hhhhhhh i think that
 » 3 years ago, # |   -24 It is at night in China. I will feel sleepy at that time.
•  » » 3 years ago, # ^ |   -64 no one cares :D
•  » » 3 years ago, # ^ |   +5 It means that it is time to take higher rank for other country's participants!!!
 » 3 years ago, # |   0 Shoot...this contest start at midnight?
 » 3 years ago, # |   +39 I don't really mean anything, but I remember your previous 2 rounds were all hackforces :pWish for better balance this time :D
 » 3 years ago, # | ← Rev. 2 →   +4 I know what you did last contest, Mr Grape
 » 3 years ago, # |   +2 My God !It is China's midnight~
•  » » 3 years ago, # ^ |   0 also a thailand pre-midnight TT
•  » » 3 years ago, # ^ | ← Rev. 2 →   +12 Codeforces contests are usually in midnight in China
•  » » » 3 years ago, # ^ |   +17 Enough for you chinese to become red.
•  » » » » 3 years ago, # ^ |   0 Not every Chinese.
 » 3 years ago, # |   -23 hope problem statement as short as this post .
 » 3 years ago, # |   -22 Ooh no the old harsh start time 1:30 AM....
 » 3 years ago, # |   -45 Who is hero in this contest?
 » 3 years ago, # |   -50 Can you set the contest without any huge statement?
»
3 years ago, # |
Rev. 2   -60

Your last contest blog you said,

"The main character of this round will be Imp the playful monster. Yet the statements are guaranteed to be short :)".

 » 3 years ago, # |   +21 So late! But I will do it.
•  » » 3 years ago, # ^ |   -10 NO ONE CARES!
 » 3 years ago, # |   +49 I really liked your past rounds. :) Excited to see the problems.
 » 3 years ago, # | ← Rev. 3 →   +31 Good luck for everyone in owls contest. :)
 » 3 years ago, # |   0 CF Contest B2B !!! ALL THE BEST EVERYONE
 » 3 years ago, # | ← Rev. 2 →   +11 wait this channel will solving every A and B problems After every div2 contest in (Arabic). https://www.youtube.com/channel/UCmWvb73kIq_oRThWd05Mtfg
•  » » 3 years ago, # ^ |   0 Great
 » 3 years ago, # |   0 Hope a good contest ^_^ and try to Hacking <3
 » 3 years ago, # |   +6 the thing that pushes me to participate in this contest is just the writer"GREEN GRAPE",problems written by him are amazing and involves brain storming as can be seen from previous ones..:)moreover he is among top contributors ->12
 » 3 years ago, # |   +6 I have just advanced into div1 after the previous educational round, but I registered this round before the rating change. Will I become unrated in this round?
 » 3 years ago, # |   +6 Can we expect 6000 participation. :)
•  » » 3 years ago, # ^ |   0 Yes
 » 3 years ago, # | ← Rev. 2 →   +5 5 minute until start the contest this is my first contest and i hope that will be good.Pray me please :)
 » 3 years ago, # |   0 I can't register?
 » 3 years ago, # |   +15 can some body explains the meaning of problem B???
•  » » 3 years ago, # ^ |   +14 it's not fair, i solved A in ten minutes but after 30 minutes i couldn't understand the meaning of B!!!
•  » » » 3 years ago, # ^ |   +2 Same as you.
•  » » » 3 years ago, # ^ |   0 Basically the problem is divided into two statements. First is which string is adorable. The string which contains exactly two characters is adorable. for example cx, aabba is adorable. And secondly the question asked whether it's possible to divide the given string into two adorable strings.( taking some character in first string and rest others in second string.)
 » 3 years ago, # |   +7 Just after locking B and seeing the first B submission in the room, I realized that I screwed myself up.Heck. Life just can't get any better than this.
•  » » 3 years ago, # ^ |   -13 NO ONE CARES
 » 3 years ago, # |   +16 IT IS difficult to understand B. :)
•  » » 3 years ago, # ^ |   +11 I feel sad for my pool understanding of English.
 » 3 years ago, # |   +43 B is just unreadable
 » 3 years ago, # |   +22 What would GreenGrape do with the time that he/she gained from problem B statements ???
 » 3 years ago, # |   +6 Why in task B in the second test zzcxx,but in the example zzxcc?
•  » » 3 years ago, # ^ |   +6 do you know that there are ask button?
•  » » » 3 years ago, # ^ |   0 it is not at all helpful @superjava
•  » » » » 3 years ago, # ^ |   +3 my question was answered in approximately 5 minutes.
 » 3 years ago, # |   +16 C is horrible
 » 3 years ago, # |   0 I think we all had this during the contest
 » 3 years ago, # | ← Rev. 2 →   +20 [deleted]
 » 3 years ago, # |   0 Problem A: What is end time of discount?
•  » » 3 years ago, # ^ |   0 Discount is valid from 20:00 to 23:59.
•  » » » 3 years ago, # ^ |   0 Thanks, got it.
 » 3 years ago, # |   +104 I think GreenGrape should write problems for Div 1, not Div 2.
•  » » 3 years ago, # ^ |   -15 Or maybe shouldn't write at all
 » 3 years ago, # |   +81 Very nice strategy by Mike and GreenGrape, Make problems so hard, so that server load will be very less...
 » 3 years ago, # |   0 can someone seriously explain problem B? i thot i understood then i got confused again are v supposed to divide the group in such a way that it can be divided again? like aabbb -> aa and bbb -> a|a and b|bb and yeee -> y|eee -> no solution
•  » » 3 years ago, # ^ |   0 Yes, we need to divide the group in such a way that it can be divided again. For example, in the test case ababa, we can group it to ab(which is adorable) and aba(which is also adorable). For zzxcc, we can group it into zx(which is adorable) and zcc(which is also adorable). For yeee, we can't group it into 2 adorable strings.
 » 3 years ago, # |   +58 I think you should win the worst problem statement ever for problem B
 » 3 years ago, # |   +118 GreenGrape stop making rounds please
•  » » 3 years ago, # ^ |   0 problem B any idea?
•  » » » 3 years ago, # ^ |   +10 not during the round sorry
•  » » » » 3 years ago, # ^ |   +1 woah , not askin for solution, just explanation for the statement man
•  » » » » » 3 years ago, # ^ |   +32 thats also part of the problem
•  » » 3 years ago, # ^ |   0 It would have been better if problem statement for second question was in Russian(even though i don't know Russian) I would have still solved the problem cause English here is much Understandable
 » 3 years ago, # | ← Rev. 3 →   +30 When someone forget to take english classes properly what happens? Something like Statement of PROBLEM B
 » 3 years ago, # | ← Rev. 3 →   +23 I find it quite funny how GreenGrape always has some very nice ideas for rounds, but the rounds themselves don't turn out as nice as the problems, either because of hacks or difficulty spread (or both) :p And yes, I do agree statement for B wasn't very clear, before anyone points that out for me.
 » 3 years ago, # | ← Rev. 2 →   +34 My 2 year old brother is speaking english better
 » 3 years ago, # | ← Rev. 2 →   -31 kya hi chutiya problem statement banayi hai isne,brother you should stop making rounds.
•  » » 3 years ago, # ^ |   -30 sahi mein yaar, problem B toh ghanta samajh mein aaraha he
•  » » » 3 years ago, # ^ |   +31 Wow, You can speak greengrape's language !!?
 » 3 years ago, # |   +8 Problems are not A, B, C, D, ... They are B, C, D, E, ... |^_^|
•  » » 3 years ago, # ^ |   +8 maybe B B D F G F
 » 3 years ago, # |   +12 This is why you should implement your own sqrt function.
•  » » 3 years ago, # ^ |   0 True, I was getting WA on test 5 with sqrt() all the time, when I changed it to sqrtl(), I got AC :)
•  » » » 3 years ago, # ^ |   +4 Thanks, got AC after 25 WA
•  » » 3 years ago, # ^ |   0 you can check if the answer is correct or not by multiplying the result.
•  » » 3 years ago, # ^ |   +6 If you use long double instead of long long the sqrt() function will work fine
•  » » 3 years ago, # ^ |   0 yes its true cos the sqrt function returns the double value by rounding it
 » 3 years ago, # | ← Rev. 2 →   0 Can someone please go through my C submissions (there are about 5-6 of them, here is one.Got 5 TLE's and wasted 1.5 hours of my life :(Edit: the logic is surely correct, I really have no clue where I messed up despite so many constant optimizations.
•  » » 3 years ago, # ^ |   0 My soln is very similar to yours. I also got TLE on 3rd pretest. I think this is not the intended soln.
 » 3 years ago, # |   +67 I appreciate the contest, even though the problemset might have been a little to hard for Div2.Problem C especially was a very nice problem.Keep making rounds, and don't get discouraged by the haters.
 » 3 years ago, # |   0 Got idea for C in last 15 minutes...didnt have time to implement it :( is it binary search for every exponent from 2 to 30 ? complexity is about 30*log( 10^18) * Q.
 » 3 years ago, # |   +4 how to solve problem C ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +34 For each number <= 1000000 insert to a set all the powers greater than 2 of the number.Make sure to erase all perfect squares in the set.Then, the answer is the number of items in the set in the range + the number of squares, which is floor(sqrtl(r)) — ceil(sqrtl(l)) + 1.
•  » » » 3 years ago, # ^ |   0 I Implemented the same idea but still got a WA on test 1 36549275
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 your solution will fail for this input 1 10968163442 10968163442 ans should be 0 your code will give 1 ps :- sorry my wrong
•  » » » 3 years ago, # ^ |   0 CF checker is too fast?The following code of someone is accepted in C. f(j, 3, 63) { for(int i = 1; i <= 1e9; i++) { if(pow(i, j) > size) break; int t = 1; f(k, 1, j+1) t *= i; s.insert(t); } } 
•  » » » » 3 years ago, # ^ |   +1 Submission link? This is just irritating. How do people pull such stuff off, its a skill on its own.
•  » » » » » 3 years ago, # ^ |   0
•  » » » » » 3 years ago, # ^ | ← Rev. 3 →   0 I think its okay, since j starts at 3. i wont go more than 1e6.Edit: after understanding the solution, its quite nice solution without needing any prior knowledge of number of squares between [1, n] etc. I would say good job, there.
•  » » 3 years ago, # ^ |   0 i am only guessing, although there may a pattern if someone wrote a brute force to check. my guess: it sum kind of sum of pow(r, 1/j) + pow(r, 1/(j+1)) + pow(r, 1/(j+2)).. lets just guess, all of us collectively.
 » 3 years ago, # |   +4 C was too hard, and with lots of ways to go wrong. I think if it was changed to a D it would've been a better contest.
 » 3 years ago, # |   +6 The problem statement of B was unclear, it took me an hour to understand it correctly.
 » 3 years ago, # |   0 This contest cried me :'(Whatever, new problems to learn new approaches
 » 3 years ago, # |   +4 What is test #3 of problem C?
 » 3 years ago, # |   +6 Problem B is just shit!I cannot really understand it after reading it about three times.Questions? "Read the problem statement"What the hell is this answer?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 they told me the same. it is like our teachers in high school. 1 + 1 = 2 is shown in classroom and in exam they give 1000000000*1000000000000 — ABC + worst contest = ? -_-
•  » » 3 years ago, # ^ |   0 First question's answer was " Read the problem statement" . Then in my second time question , i added " Don't reply "Read the statement " type of answer ." , then they answered my question .
 » 3 years ago, # |   +3 36552101it took 1.5 sec in codeblocks but showing TLE (takes more than 10 sec on CF compiler). by debugging i found out that the problem is in siv() function. but i cant find why. I also added this condition (if (temp <= 0 or temp > 1e18)break;) still not working. can anyone help?
•  » » 3 years ago, # ^ |   0 You can use "costum innovation" to see what's going wrong .
•  » » » 3 years ago, # ^ |   0 I did but found nothing. working fine on codeblocks. it showed TLE on test case 1 but is working perfectly on codeblocks. custom invocation shows TLE (10 sec) -_- .
•  » » » 3 years ago, # ^ |   0 The problem is in siv() function but i cant find it...
 » 3 years ago, # |   +1 I've got lots of wronganswers in C Maybe the accuracy problem Sad...
 » 3 years ago, # |   0 Could D be solved with binary search + hash I mean we go i=0...n-1 and we find maximal d such that s[i...i+d-1] = t[0...d-1],then we store all values in some vector, same for the right side but we do on suffix instead of prefix. and then we brute force for the length of first part we use in solution,greedily picking leftmost valid choice?
 » 3 years ago, # |   +2 Critical info missing in A. Poor wording to understand B. Impossible to solve C. As you can guess, didn't get any further than C. I bet english PS must be translated one.
•  » » 3 years ago, # ^ |   0 if it is impossible to solve problem C How did many people solve it ?
•  » » 3 years ago, # ^ |   +1 "Impossible to solve C" More like, "Impossible to optimize C"(i'm still mad at my 2136 ms solution getting TLE)
 » 3 years ago, # | ← Rev. 3 →   +4 I could have got an AC in C if I didn't spend much time in understanding B...I think logic for C is iterate through p=2 to p=floor(log2l(R)) and calculate for log2l(L)<=p*log2l(a)<=log2l(R) and then do inclusion exclusion for 16 which can be written in two ways pow(2,4) and pow(4,2) .
 » 3 years ago, # |   0 [submission:36553906] 0.136 seconds too slow...(not sure if correct)
 » 3 years ago, # |   +6 Div 2 B says: "Check whether it can be split into two non-empty subsequences such that the strings formed by these subsequences are adorable. Here a subsequence is an arbitrary set of indexes of the string."This doesn't imply that all characters of the string must be used or that they must be necessarily distinct. It simply defines the subsequences as an arbitrary set of indexes of the string. Thus a problem such as "asrewsafdv" allows you to choose the subsequences "as" and "re" to form a valid "split into two non-empty subsequences such that the strings formed by these subsequences are adorable".
 » 3 years ago, # |   -56 This amount of clarification requests turned out to be a real surprise for me.
•  » » 3 years ago, # ^ |   0 Will the contest be unrated???
 » 3 years ago, # |   0 How to solve F?My solution idea was as follows: for k = 1, we can calculate part of answer using depths of subtrees. for 2 <= k <= MAXK=547, dp_k(u) <= MAXM=18. So calculate part of answer through calculating isKHeap[u][m] -- if there's heap of depth m rooted at vertex u. for k > 547, dp_k(u) <= 2. Again, use that fact to calculate part of answer using number of children for each vertex. This works in about O(MAXK * MAXM * n), which is too long. But I hoped, through stricter bounds on MAXM(k) and non-asymptotic optimizations, solution could be made fast enough. Unfortunately I got stuck at TL 10 =(
•  » » 3 years ago, # ^ |   +3 u could optimize this if u keep dp_k(node) = the maximum depth of a k-ary tree rooted at node and u obtain O(sqrt(N) * N) but this tle too
•  » » 3 years ago, # ^ | ← Rev. 3 →   +23 Iterate through 1..k..n. Solve the problem rooting the heap at every vertex with >= k children (< k children has answer 1). There are n / k such vertices. Delete the edges that go to vertices with < k children (so you don't visit them again). The cost for this part is O(n*log^2n) because N / 1 + N / 2 + ... = O(nlogn) and you need an extra log to get the k-th element of the children. Now, sort the answers in increasing order of values and use something like HLD to see how many ancestors have this answer. For each "chain", keep the maximum height where you enter this chain. You only need that since you just go up. The total complexity is O(n*log^2n).
 » 3 years ago, # | ← Rev. 2 →   +2 if i want to write the problem B:can we divide a string into 4 nonempty part , in a way that each part contains only one kind of letter?what did you want to do with just writing that things???
 » 3 years ago, # |   +7 CF predictor shows -99 but there is no codeforces HOT NEWS or any option to share it
 » 3 years ago, # |   +36 And Would waiting for the editorial return back the 3 hours we wasted :((?You're certainly missing a point there,People aren't mad because the problems are hard,but because they are misplaced..(and the Bad english in B)If you were to place Problem C as D and Get a better translation for problem B,no one would be mad right now..
•  » » 3 years ago, # ^ |   -80 agree with you and already down voted the idiot.Stupid B. Real Piece of Shit. And fucking stupid replies.
•  » » » 3 years ago, # ^ |   +77 So rude of you. Does calling me an idiot makes your life better or anything?
•  » » » » 3 years ago, # ^ |   -72 well if i am getting up votes, that means people are agreeing with me. Seriously, my rating increased 5 times in a row until this. And i know i could have solved B if you could have explained it better. -_- No, calling you stupid, idiot does not make my life better. If idiots like you stop making contests and other people dont suffer — that will make my life better and EVERYTHING...
•  » » » » » 3 years ago, # ^ |   +32 People Agreeing with you doesn't make you correct.. also it's rude to call him an idiot Psycho,the problem set might have been a little unbalanced with some mistakes,but it doesn't make it bad.. Anyway Sorry Grape about saying the wasted 3 hours and good luck on next rounds..
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +20 Weak point. If you're stuck with B, what prevents you from skipping it and proceeding to C and further?If you are so vulnerable and cannot control your nerves, ain't it better for you to abstain from participating in rated rounds?Such childish behaviour...
•  » » » » » » 3 years ago, # ^ |   +4 i think what prevents he from skipping B and proceeding to C was :problem C in fact was a D problem, not C!!(in my opinion)
•  » » » » » » » 3 years ago, # ^ |   0 It wasn't a D, it was maybe C.5 but not D. (I didnt solve it either but it was not D)
•  » » » » » » » » 3 years ago, # ^ |   0 maybe an easy Di've seen a lot of D problems that they were a lot easier than this one
•  » » » » » » » » » 3 years ago, # ^ |   +5 It would've been a lot easier for me if the time limit was 3 seconds instead of 2.
•  » » » » » » 3 years ago, # ^ |   0 skip is not working, I can't solve C, then it goes worse(DEF is even worse) :pof course nothing will happen except rating -87in fact if get 6 AC then +300 (but not possible for me now)which means I'm too weak to solve these problem nowbut this round's problem is really not suitable for Div.2 :pI want to solve Div.2 problem to improve myself but not Div.1 now ;w;after all, waiting for your next round.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 I'm always open to whatever feedback I receive, but this time it's hard for me to agree. Could you please explain what remained uncovered in statement of B?It's clearly stated that you have to figure out whether you can split the string into two adorable ones. What's the issue?
•  » » » 3 years ago, # ^ |   -11 How can you redefine the meaning of sub-sequence?
•  » » » 3 years ago, # ^ |   -6 I can't speak for others but this was the problem I had with the description:Div 2 B says: "Check whether it can be split into two non-empty subsequences such that the strings formed by these subsequences are adorable. Here a subsequence is an arbitrary set of indexes of the string."This doesn't imply that all characters of the string must be used or that they must be necessarily distinct. It simply defines the subsequences as an arbitrary set of indexes of the string. Thus a problem such as "asrewsafdv" allows you to choose the subsequences "as" and "re" to form a valid "split into two non-empty subsequences such that the strings formed by these subsequences are adorable".
•  » » » » 3 years ago, # ^ |   +33 This doesn't imply that all characters of the string must be used The word "split" does imply that all of the characters should be used.
•  » » » 3 years ago, # ^ |   -6 What does it mean by the phrase: equal symbolsDoes it mean equal number of symbols or number of distinct symbols?
•  » » » 3 years ago, # ^ |   +8 While I really liked Problem C, I just wish the time limit was a little more liberal as many of us had an alternate thats just up by a constant of around 5. It was efficient in it's own way too (O(1) Memory). That and perhaps an easier D would've made it a great contest for me, Thanks!
•  » » » 3 years ago, # ^ |   -8 atleast dear good sir accept it that the problem statement was not clear,if it was so crystal clear then why so many people are complaining?
•  » » » » 3 years ago, # ^ |   +17 You didn't read the actual question.The statement doesn't ask whether the input string is adorable, but whether we can split it into two adorable strings (not substring, but subsequence)
•  » » » 3 years ago, # ^ |   0 miss those days when Tourist used to make such a interesting and unambiguos round and also his problems used to be original.
•  » » » 3 years ago, # ^ |   +48 carsonbradshaw, generally the meaning of "split" is to divide something into non-intersecting parts so that the union of these parts forms the entire object. I assumed this is quite obvious and seemingly failed.win11905, this question is quite strange. a and a are equal, a and b are not, for example. Ragnarok22, if you ever look through the clars as an author, you would probably change your mind. shash42, 5 is quite a huge constant. There were similar solutions during the testing phase, but they all passed in 1.5-1.6 seconds.Zaee, it seems that you misinterpreted the entire task :(
•  » » » » 3 years ago, # ^ |   +4 A tongue twister might has no syntax error,but it's really hard to read.You could say it in another way easier to understand,thanks. Besides,you might be angry,but think of it,few people here means to pick a quarrel,and most people here is just wrote a feedback.A feedback like this shows that many people really cannot read B's statements well,and persuade the feedback-providers is in no use.
•  » » 3 years ago, # ^ |   +7 Well for me and my friends C is far easier than D,thus the placement has no problem.But B is totally unreadable.I don't think it right to call that poor thing English.
 » 3 years ago, # |   0 The scoring distribution be like 500 — 1000 — 2000 — 2500 — 3000 — 3000. :P
 » 3 years ago, # |   0 "You'd rather wait for the editorial before downvoting :)" I think even though someone didn't wanted to down vote but after reading this from official comment GreenGrape, we are inclined to downvote. This has just increased the down vote.
 » 3 years ago, # |   +37 Fastest System Test EVER!!
 » 3 years ago, # |   +37 Add one more problem and this could have been Div1+Div2 combined contest.
 » 3 years ago, # | ← Rev. 2 →   -24 Problem C from the contest has already been used before: http://ws.kh.ua/media/sbornik/Sbornik2012.pdf, (page 111, Problem perfect powers) there is even an editoral in the book. (This problem at e-olymp online judge: https://www.e-olymp.com/ru/problems/2890). I believe that due to this reason concerning bad English statement of problem B round should be made unrated.
•  » » 3 years ago, # ^ |   +1 How was I supposed to figure this out? :) I've never solved problems at E-Olymp.Moreover, the solution uses a different approach which is hard to squeeze when there're lots of queries.
•  » » » 3 years ago, # ^ |   +3 I tried 18 submissions, but inclusion-exclusion approach does not pass whatever I do.
•  » » » 3 years ago, # ^ |   0 Good problem C ,though i couldn't solve this problem in the contest time . Just a simple observation is needed :) Thank you GreenGrape
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 @vova_rakal Even though it was used before,there were very less submissions in contest. It means that no one has found it out and it is very difficult to find.
•  » » 3 years ago, # ^ |   0 The constraints of A and B in the second link is 10^14 while in this one it is 10^18. That makes some difference in solution, I think.
 » 3 years ago, # |   +5 I'm surprised that there are only two AC on problem E. It is just to understand the statement :)
 » 3 years ago, # |   +3 Thanks 471, my black streak of failure is over)
 » 3 years ago, # |   +8 Great contest with good problems. Ignore the negative comments. :-)
 » 3 years ago, # | ← Rev. 2 →   0 Why this source didn't get hacked on test abcdefghijklmnopqrst http://codeforces.com/contest/955/submission/36549772It should have got killed by signal on this test and thus succesful hack
•  » » 3 years ago, # ^ |   0
•  » » 3 years ago, # ^ |   0 You really should read the solution more carefully.  else if(num==4) cout<<"Yes"<
•  » » » 3 years ago, # ^ |   0 It would have gotten killed by signal?Isn't this wrong?
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 Ouch, now it was I who didn't read carefully. Sorry about that (pretty ironic feeling to me anyway).I've just submitted one of my solutions, with the return 0; command removed. It works with all C++ compilers. (36555214, 36555218, 36555221, 36555227).So I'm going to a conclusion that if no return command is called with in a non-void-returned function, it will always return the convertible-to-zero value.
 » 3 years ago, # |   +18 it's really shame that some people want the round to be unrated becausethey couldn't solve the problems
 » 3 years ago, # |   +2 I liked problem C despite not being able to solve it :)
 » 3 years ago, # |   0 B is too hard to readat the beginning I think adorable means a stirng with even kinds of letterssubmit, pp, hackedI going crazy after read it many times but still can't find anything wrong.I guess maybe the "group" of adorable string should contain only one kind of letter.resubmit , pp (now it's AC)besides, after I locked my A just 3 min later my B get hacked(I'm so lucky not locking B first)and maybe Problem C's time limit is too tight ......?after all, hopes next round will be better
 » 3 years ago, # |   0 it's really shame that some people want the round to be unrated becausethey couldn't solve the problems, B has a lot of AC so what??
 » 3 years ago, # |   0 Problem statement of B is horrible. Even now I don't know why my solution is wrong (fails on test 35).The least that could be done was to explain a few examples to make this statement clear. Very very bad contest, considering only 2 problems were solvable for most Div 2 participants and here also, the problem statement is so hard to understand for one of them.GreenGrape, learn to accept your mistake (maybe your problem statement wasn't ambiguous in Russian, but in English it's a mess).
•  » » 3 years ago, # ^ |   0 This part in your code is not correct: if (count.size() > 3) { cout << "Yes" << endl; } Input: abcde — correct answer is No , but you output Yes
•  » » » 3 years ago, # ^ |   +3 That's exactly what I missed in my solution as well. I only realized it after locking, so I hacked with abcde once instead :)
•  » » » 3 years ago, # ^ |   0 My bad — I missed the part of the problem statement where it says "equal symbols".I didn't even check the problem statement after I got hacked, because I had passed pretests. Pretests are becoming useless nowadays in contest.
 » 3 years ago, # |   0 Problem B was poorly stated, very difficult to understand. Unfair round.
 » 3 years ago, # |   +3 can anyone please explain the problem B. :'(
•  » » 3 years ago, # ^ | ← Rev. 2 →   +6 adorable strings are strings with 2 groups, each group have > 0 same characters. (ab, aab, abb, aabb).given a string, you have to find out if you can make 2 adorable strings using all the characters.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 It's kinda simple.First: An adorable string is anyone that has exactly 2 different letters inside.Second: If we want to get a subsequence of the starting string S such that it's adorable, then this subsequence must have exactly 2 different letters. Third: With Second observation, we realize that if we have 5 different letters or just 1 the answer is immediately "No".Fourth: Now, we only have the cases with:2 different letters: - Let (x,Qx) and (y,Qy) be the 2 letters with their frequency. Then, we can get 1 from x and 1 from y and create a adorable subsequence, with the rest of letters being the other one. Now, the other one must be non-empty, and thus, have size of at least 2 (1 x and 1 y). So the answer will be "Yes" iif Qx >= 1+1 = 2 and Qy >=1+1 = 23 different letters: - Let (x,Qx), (y,Qy) and (z,Qz), so that Qx >= Qy >= Qz. Then, since Qx is the maximum, it's the best candidate so that we take 1 from it and what's left would be > 1. So, we can create an adorable subsequence taking 1 x and all y's, and the other one would be Qx-1 x and Qz z's. So the answer will be "Yes" iif Qx >= 1+1 = 2. 4 different letters: - We can split the 4 letters into 2 subsets of 2 letters each, so the answer is always "Yes".
•  » » 3 years ago, # ^ |   +3 Problem statement is so hard though solution is very easy . S -> P | Q -> m | n || r | s Here S is for main string . P and Q is for after splitting first time . Then P will be splitted into two parts m and n . Q also follow the rules . All the distinct characters of m must be same . But m and n's mustn't be same . r and s also .
 » 3 years ago, # |   +3 I liked the concept of this contest. The problems weren't hard in comparison to the usual CF Round, but the dificulty difference between each consecutive problem was kinda unusual (greater). It reminded me of CSAcademy rounds. GL & HR for everyone in tomorrow's contest :D
 » 3 years ago, # |   +6 when will the rates changes ????
 » 3 years ago, # |   +39 Please stop complaining about the statement or the difficulty! Don't blame other thing to make yourself think that your failure is not due to your weakness!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +3 sigh Finally the point has been made.Must admit, if I had ranted about my performance, heck, it should have been even worse than matthew99's incident...
 » 3 years ago, # |   +11 Your problems are easy to solve but difficult to understand.
 » 3 years ago, # |   +3 It's not really "mature" to blame other for your own mistakes, the round was good maybe C was a litlle bit harder than usual but look to the bright side after the editorial you will learn new approachs and techniques, there is never a "bad" round ... there is a good/bad performance and in both cases it's always an oppurtunity to learn new things and better ways to attack futur problems
 » 3 years ago, # |   0 GreenGrape editorials are only in Russian.
•  » » 3 years ago, # ^ |   -6 I know :(I'll translate them tomorrow.
•  » » » 3 years ago, # ^ |   0 OK thanks and there is no editorial for D, E and F. Hope tomorrow they will be published too :)
 » 3 years ago, # |   +6 Can anyone tell me why my submission got TLE? Because I use python? http://codeforces.com/contest/955/submission/36549700
 » 3 years ago, # | ← Rev. 2 →   0 in the problem statement he says -> "For example, ababa is adorable (you can transform it to aaabb, where the first three letters form a group of a-s and others — a group of b-s), but cccc is not since in each possible consequent partition letters in these two groups coincide" what does mean by forming a group of a's and b's (aaa | bb) and how this thing is adorable ? and also zx | zcc adorable how?
•  » » 3 years ago, # ^ |   +1 ababa = exactly two different letters (of two type) in string means string is adorable. but cccc doesn't contains exactly two different kind of letters (only one type)..
•  » » » 3 years ago, # ^ |   0 Okay so we were needed to figure out what exactly adorable here means or u just deduce it by problem statement?
•  » » » » 3 years ago, # ^ |   0 I deduce it by problem statement. Obviously in actual world the word adorable is not coonected to problem. First in problem statement we need to understand what adorable means and then we need to check whether its possible to split the given string into two adorable strings.
•  » » » » » 3 years ago, # ^ |   0 no i mean u came up with the logic itself? because what examples stated here were totally ambiguos one is aaa|bb, zc|zxx and ye|ee doesn't make any sense and also nowhere in problem it was stated that each adorable string should have two different symbol.
•  » » » » » » 3 years ago, # ^ |   0 "two consequent groups of equal symbols (note that different groups must contain different symbols)."equal symbols means same character. different group must contains different symbols means different groups must contains different characters.It can also be written again as "two consequent groups of same characters (note that different groups must contain different characters...I hope it's now clear....
 » 3 years ago, # |   0 Editorial is not opening.
 » 3 years ago, # |   +3 Why does it say "You are not allowed to view the page" when i click on the link to the Editorial?
 » 3 years ago, # |   +4 Here is my approach for problem C.1) I stored all divisors of range [2, 64].2) Now, for each L-R query, I ran loop for powers from 64 to 2[reverse loop].3) According to inclusion-exclusion principle, if any number having power p is included in the range of L-R than it will be included by the power divisor too. We need to subtract the overcount by this power. Suppose the number is 2^8, than 4^4 will result in the same value. So, we need to subtract the overcount. 2^8 value is same for 4^4, 16^2. We will subtract the value 2 from ans.I am getting WA on test 2 999999999999999999. My output is 1001003331, the expected output is 1001003330.Can anybody explain me where am I making the mistake?? Link to my solution.
•  » » 3 years ago, # ^ |   0 Your approach seems correct, but when working with integers/longs,it's recommended to keep all your calculations in integers/longs and do all functions such as square root, log... manually, as all default functions in most programming languages works with floats/doubles, which can potentially lead to WA, when converting back to integers/longs, due to precision errors. So for the ceil of nth root of a number, you can try binary search it instead.
•  » » » 3 years ago, # ^ |   0 Can you suggest me how to do this? I tried StrictMath library of Java. It is still giving the same error. I am unable to get your idea of binary search.
•  » » » » 3 years ago, # ^ |   0 Here's how, we get our mid, w raise mid the nth power, if it's bigger than x, then all values bigger than mid will eventually give bigger results, and there's not need to test them, thus right = mid, and the same thing if mid to the nth power is a smaller the x, following the same reasoning, left = mid.In case it's not clear, here's the code, it's easier to follow with. Spoilerint nth_root(ll x, int n){ int l = 0, r = (int)pow(2e18, 1.0 / n);// setting an upper limit while(l < r){ int mid = (l + r + 1) / 2; ll tmp = 1; for(int i=0;i
 » 3 years ago, # |   0 hm... matter of my life : solve a problem or hack someone's code?
 » 3 years ago, # |   0 editorial not yet
 » 3 years ago, # |   0 why so hard.................. log in , find i can't solve C, goodbye & sleepwhen i get up....
•  » » 3 years ago, # ^ |   0 codeforces have to add (Div 0)so GreenGrape can put his problems there
•  » » » 3 years ago, # ^ |   0 yes
 » 3 years ago, # |   +9 Please FIX the tutorial link...it says 'You are not allowed to view the requested page'
 » 3 years ago, # | ← Rev. 2 →   0 Sorry for the late of comment, but is there anyone could plz explain about problem D? I have some questions about the time complexity. I have seen some code that compute the array (the left most position to get a prefix of certain length and the right most position to get a suffix of certain length) using a "for" including a "while" inside. I can't figure out the complexity of this, I just know that it isn't worse than O(nm), but a solution with O(nm) is surely not an expected one. I just can't figure out how this "for" with "while" inside can be less than O(nm), and if so what is its complexity? Could someone plz explain that?
 » 3 years ago, # | ← Rev. 2 →   +21 I've done this contest later as virtual contest. I've been reading the comments of the forum here and have seen many people angry with the author. I've found the contest difficult for me, and perhaps problem B a little bit difficult to read, although it is correctly written, but as we know, something can be correctly written and difficult to read simultaneously. Anyway, it would be a pitty if the author feels discouraged to prepare a further contest. The problems are very beautiful from any reasonable perspective, so they are a great contribution. Writing in an accessible way and measuring the difficulty of a problem is a very challenging task that requires a lot of effort and experience. Even experienced writers fail from time to time. Practice makes perfect.
 » 3 years ago, # |   0 .