Менее 24 часов до раунда?
И до сих пор никакого анонса?
Как так, Mr. Grape?
Codeforces Round #471 состоится в пятницу в 19:35 по московскому времени. Обратите внимание, что раунд несколько длиннее обычного.
Раунд будет рейтинговым для участников из второго дивизиона. Первый дивизион тоже приветствуется, но, как и всегда, вне конкурса :)
Спасибо Грише (vintage_Vlad_Makeev) за координацию раунда, Ильдару (300iq), Никите (FalseMirror), Азату (ismagilov.code), Жене (rek) и Олегу (xen) за тестирование и, конечно, Майку (MikeMirzayanov) за Codeforces и Polygon.
Задач будет шесть со следующей разбалловкой:
500 — 1000 — 1500 — 2000 — 2500 — 3000
UPD. Системное тестирование окончено! Разбор
Поздравляем победителей!
Div. 2:
Div. 1 (unofficial):
Когда сказали, что раунд для див 2 рейтинговый, что, пацаны, минус рейтинг?
A BIT longer
prakhar17252
Why are registrations starting so late?
i hope a lot of Hacking <3
It is raining contests...!!!
Hallelujah?
I think, In your contest, problems are easy to solve but difficult to understand..
It is at night in China. I will feel sleepy at that time.
It means that it is time to take higher rank for other country's participants!!!
Shoot...this contest start at midnight?
I don't really mean anything, but I remember your previous 2 rounds were all hackforces :p
Wish for better balance this time :D
I know what you did last contest, Mr Grape
My God !It is China's midnight~
also a thailand pre-midnight TT
Codeforces contests are usually in midnight in China
Enough for you chinese to become red.
Not every Chinese.
hope problem statement as short as this post .
Ooh no the old harsh start time 1:30 AM....
Who is hero in this contest?
Can you set the contest without any huge statement?
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 :)".
But you said nothing about statement in this blog...
Please tell about statement clear!!!
So late! But I will do it.
I really liked your past rounds. :) Excited to see the problems.
Good luck for everyone in owls contest. :)
wait this channel will solving every A and B problems After every div2 contest in (Arabic). https://www.youtube.com/channel/UCmWvb73kIq_oRThWd05Mtfg
Если кто-нибудь будет сегодня в биокорпусе дорешивать, пришлите мне плиз мой логин и пароль от яндекс.контеста (мой стол в дальнем углу)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
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?
Can we expect 6000 participation. :)
Yes
Настало ли время узнать разбалловку?
5 minute until start the contest this is my first contest and i hope that will be good.Pray me please :)
I can't register?
can some body explains the meaning of problem B???
it's not fair, i solved A in ten minutes but after 30 minutes i couldn't understand the meaning of B!!!
Same as you.
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.)
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.
IT IS difficult to understand B. :)
I feel sad for my pool understanding of English.
B is just unreadable
What would GreenGrape do with the time that he/she gained from problem B statements ???
Why in task B in the second test zzcxx,but in the example zzxcc?
do you know that there are ask button?
it is not at all helpful @superjava
my question was answered in approximately 5 minutes.
C is horrible
I think we all had this during the contest
[deleted]
Problem A: What is end time of discount?
Discount is valid from 20:00 to 23:59.
I think GreenGrape should write problems for Div 1, not Div 2.
Very nice strategy by Mike and GreenGrape, Make problems so hard, so that server load will be very less...
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
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.
I think you should win the worst problem statement ever for problem B
GreenGrape stop making rounds please
problem B any idea?
not during the round sorry
woah , not askin for solution, just explanation for the statement man
thats also part of the problem
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
When someone forget to take english classes properly what happens? Something like Statement of PROBLEM B
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.
My 2 year old brother is speaking english better
kya hi chutiya problem statement banayi hai isne,brother you should stop making rounds.
sahi mein yaar, problem B toh ghanta samajh mein aaraha he
Wow, You can speak greengrape's language !!?
Problems are not A, B, C, D, ... They are B, C, D, E, ... |^_^|
maybe B B D F G F
This is why you should implement your own sqrt function.
True, I was getting WA on test 5 with sqrt() all the time, when I changed it to sqrtl(), I got AC :)
Thanks, got AC after 25 WA
you can check if the answer is correct or not by multiplying the result.
If you use long double instead of long long the sqrt() function will work fine
yes its true cos the sqrt function returns the double value by rounding it
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.
My soln is very similar to yours. I also got TLE on 3rd pretest. I think this is not the intended soln.
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.
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.
how to solve problem C ?
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 <l;r> + the number of squares, which is floor(sqrtl(r)) — ceil(sqrtl(l)) + 1.
I Implemented the same idea but still got a WA on test 1 36549275
your solution will fail for this input 1 10968163442 10968163442 ans should be 0 your code will give 1 ps :- sorry my wrong
CF checker is too fast?
The following code of someone is accepted in C.
Submission link? This is just irritating. How do people pull such stuff off, its a skill on its own.
http://mirror.codeforces.com/contest/955/submission/36546771
I think its okay, since
jstarts at 3.iwont 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.
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.
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.
The problem statement of B was unclear, it took me an hour to understand it correctly.
This contest cried me :'(
Whatever, new problems to learn new approaches
What is test #3 of problem C?
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?
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 = ? -_-
36552101
it 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?
You can use "costum innovation" to see what's going wrong .
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) -_- .
The problem is in siv() function but i cant find it...
I've got lots of wronganswers in C Maybe the accuracy problem Sad...
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?
As you can guess, didn't get any further than C. I bet english PS must be translated one.
if it is impossible to solve problem C How did many people solve it ?
"Impossible to solve C" More like, "Impossible to optimize C"(i'm still mad at my 2136 ms solution getting TLE)
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 forlog2l(L)<=p*log2l(a)<=log2l(R)and then do inclusion exclusion for16which can be written in two wayspow(2,4)andpow(4,2).[submission:36553906] 0.136 seconds too slow...(not sure if correct)
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".
This amount of clarification requests turned out to be a real surprise for me.
How to solve F?
My solution idea was as follows:
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 =(
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
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).
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???
CF predictor shows -99 but there is no codeforces HOT NEWS or any option to share it
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..
agree with you and already down voted the idiot.
Stupid B. Real Piece of Shit. And fucking stupid replies.
So rude of you. Does calling me an idiot makes your life better or anything?
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...
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..
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...
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)
It wasn't a D, it was maybe C.5 but not D. (I didnt solve it either but it was not D)
maybe an easy D
i've seen a lot of D problems that they were a lot easier than this one
It would've been a lot easier for me if the time limit was 3 seconds instead of 2.
skip is not working, I can't solve C, then it goes worse(DEF is even worse) :p
of course nothing will happen except rating -87
in fact if get 6 AC then +300 (but not possible for me now)
which means I'm too weak to solve these problem now
but this round's problem is really not suitable for Div.2 :p
I want to solve Div.2 problem to improve myself but not Div.1 now ;w;
after all, waiting for your next round.
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?
How can you redefine the meaning of sub-sequence?
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".
The word "split" does imply that all of the characters should be used.
What does it mean by the phrase: equal symbols
Does it mean equal number of symbols or number of distinct symbols?
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!
Here are the questions i asked myself while reading Problem B(which you didn't cover)
1-Why is 'ababa' adorable but 'cccc' is not? Your explanation: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.
My thinking:You can simply divide 'cccc' to cc-cc
My Alternative thinking:Maybe it should be distinct letters?
After reading the sample explanation: 'In sample case two zzcxx can be split into subsequences zc and zxx each of which is adorable.'
Like Wtf? why is zzcxx adorable and cccc isn't?
The alternative thinking turned out to be wrong..Then my eyes dropped on
subsequence..and how was aaa,bb a subsequence of ababa..
I hope this is enough for you to reach how i thought while reading the statment
Until now,i cant understand what it asks for
--upd adding symbols there was also mislead,should've been letters
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)
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 :(
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.
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.
The scoring distribution be like 500 — 1000 — 2000 — 2500 — 3000 — 3000. :P
"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.
Fastest System Test EVER!!
Add one more problem and this could have been Div1+Div2 combined contest.
Задача C баян: http://ws.kh.ua/media/sbornik/Sbornik2012.pdf,(стр 111, perfect powers) там даже разбор есть. (Можно сдать на e-olymp https://www.e-olymp.com/ru/problems/2890). Я считаю что вместе с плохим английским условием задачи B это повод сделать раунд нерейтинговым.
там немного другая задача же. A и B совпадают с L и R
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.
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.
I tried 18 submissions, but inclusion-exclusion approach does not pass whatever I do.
@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.
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.
I'm surprised that there are only two AC on problem E. It is just to understand the statement :)
Thanks 471, my black streak of failure is over)
Great contest with good problems. Ignore the negative comments. :-)
Why this source didn't get hacked on test abcdefghijklmnopqrst http://mirror.codeforces.com/contest/955/submission/36549772
It should have got killed by signal on this test and thus succesful hack
GreenGrape
You really should read the solution more carefully.
The case you gave was handled correctly.
It would have gotten killed by signal?
Isn't this wrong?
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
returncommand is called with in a non-void-returned function, it will always return theconvertible-to-zerovalue.it's really shame that some people want the round to be unrated because
they couldn't solve the problems
I liked problem C despite not being able to solve it :)
B is too hard to read
at the beginning I think adorable means a stirng with even kinds of letters
submit, pp, hacked
I 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
it's really shame that some people want the round to be unrated because
they couldn't solve the problems, B has a lot of AC so what??
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).
This part in your code is not correct:
Input:
abcde— correct answer isNo, but you outputYesThat's exactly what I missed in my solution as well. I only realized it after locking, so I hacked with abcde once instead :)
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.
Problem B was poorly stated, very difficult to understand. Unfair round.
can anyone please explain the problem B. :'(
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.
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 = 2
3 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".
Problem statement is so hard though solution is very easy .
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 .
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
when will the rates changes ????
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!
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...
Your problems are easy to solve but difficult to understand.
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
GreenGrape editorials are only in Russian.
I know :(
I'll translate them tomorrow.
OK thanks and there is no editorial for D, E and F. Hope tomorrow they will be published too :)
Can anyone tell me why my submission got TLE? Because I use python? http://mirror.codeforces.com/contest/955/submission/36549700
Спасибо раунду за моё новое звание)
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?
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)..
Okay so we were needed to figure out what exactly adorable here means or u just deduce it by problem statement?
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.
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.
"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....
Editorial is not opening.
Why does it say "You are not allowed to view the page" when i click on the link to the Editorial?
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.
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.
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.
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.
hm... matter of my life : solve a problem or hack someone's code?
editorial not yet
why so hard.................. log in , find i can't solve C, goodbye & sleep
when i get up....
Please FIX the tutorial link...it says 'You are not allowed to view the requested page'
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?
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.
.