### Aksenov239's blog

By Aksenov239, 7 years ago, translation, ,

Hello everybody! There is less than 3 hours before my second codeforces round, in which I participating as author. (The first one was — Codeforces Beta Round #56.) It will be llok like the previous one. (That was not bad, I wish. :-)!) I wish, you like today's contest.

I'm the author of this round, except one problem, which was proposed by Gerald.

In preparing this round was participating : Gerald (He always makes problems better.), cerealguy (Who helps in preparing, i think, the hardest problem of this round. He had solved the first version of round — and think, that it's easy.), delinur (Who translate the problems). And also it was done with help of "Polygon" and "Codeforces".

I wish, you luck in this contest and to have high rating.

Problem scores will be as always. I wish, that problems are sorted well.

UPD: I'm very bad man, and have written wrong solution in problem "C". Problem under investigation.

• +26

 » 7 years ago, # | ← Rev. 2 →   +34 And are there dynamic problem max scores used?
•  » » 7 years ago, # ^ |   0 Same question as Betlista. How about the scores and order of problems?
 » 7 years ago, # |   +6 What about the ordering of the problems? Are they arranged in the order of difficulty?
•  » » 7 years ago, # ^ |   0 Yes.
 » 7 years ago, # |   0 I hate hack announcement on prob A because of I misunderstanding with the problem :(
 » 7 years ago, # |   +13 problem A was unclear until correction came. Why should we assume that we must make exactly one swap unless it is mentioned? Problem C had problems too. Did the authors mentioned anywhere that we must count smallest triangles? though it is obvious after counting triangles in figure, it should've mentioned been in the statement. And also the problem was google-able,just find 1st few n's and search in google,you'll get this: http://oeis.org/A007582.
•  » » 7 years ago, # ^ |   0 I understood "A" from the very beginning. Also, didn't see any problem with description in "C". Seems that problems were with translation=)
•  » » » 7 years ago, # ^ |   +2 A was ambiguous. Some may understand correctly at first glance,some may get confused. I am unlucky and got confused :(. C didn't have any big problem,but they should've mentioned about smallest triangle.
•  » » 7 years ago, # ^ |   -48 You are looking answers for contest problems on google? Hm...
•  » » » 7 years ago, # ^ |   +23 oeis.org have a collection of a huge number of sequences. Anyone could've find the formula. The fact i want to point out is "Contest problem shouldn't be google-able".
•  » » » » 7 years ago, # ^ |   -8 for the purpose of increasing your coding ability, it is the 'best' idea to come up with the solution on your own, rather than browsing through the web... also, once you are past some level, browsing through the web is not dramatically fast as browsing through your brain; one requires some physical effort under time-pressure while the other is almost purely mental (modulo writing things)...
•  » » » » » 7 years ago, # ^ |   +35 You are right. But still my point holds: “Contest problem shouldn’t be google-able”. Once someone is almost sure that he'll find the answer in a certain site,googling is not a slow process!
•  » » » » » » 7 years ago, # ^ |   -15 why would you ever do that, if you are under a premise that you'd like to improve yourself?your rating isn't going to go above certain threshold however hard you try to cheat.
•  » » » » » » » 7 years ago, # ^ |   -17 Why are you minusing yongwhan posts? He's right. There are problems on onsites, where if you can use google — you can solve the problem. If you use oeis here — it's really cheating, because you shoud think it like onsite round without internet.
•  » » » » » » » » 7 years ago, # ^ |   +14 There are rules for Codeforces rounds and different rules for different onsite rounds. For example, on CROC onsite participants were also permitted to use Internet.Either you set strict rules for your Codeforces round and make them clear and available before the round, or I don't see why one should treat using OEIS as cheating.
•  » » » » 7 years ago, # ^ |   0 I agree. So what do you think about this contest?
•  » » 7 years ago, # ^ |   0 I hacked 3 solutions of "A" during the contest,but later my solution was hacked,too,and I don't know why. But my problem had already locked, T.T
 » 7 years ago, # |   +84 Problem B — this is programming or math contest?
•  » » 7 years ago, # ^ |   -17 Common, it was very simple formulae, you can ask the same for C...
•  » » » 7 years ago, # ^ |   +8 It's different. B is really about math
•  » » » 7 years ago, # ^ |   +8 He meant problem B from div 1, not div 2.
•  » » » » 7 years ago, # ^ |   -11 Ou, I'm sorry, I didn't realize O:-)
•  » » 7 years ago, # ^ |   +3 Can somebody explain the solution of B?
•  » » » 7 years ago, # ^ |   0 Let a_i is number of /\ triangle, and b_i is number of \/ triangle after i-th day.Then (a_i,b_i)matrix((3,1),(1,3)) = (3a_i + b_i, a_i + 3b_i) = (a_(i+1), b_(i+1))So, we need calculate (1,0)*matrix((3,1),(1,3))^n
•  » » » » 7 years ago, # ^ |   0 Is binpow solution better ?
•  » » » » » 7 years ago, # ^ |   0 better than what? my solution is binpow, because you can calculate it for O(n)
•  » » » » » » 7 years ago, # ^ |   +8 Also, it is possible (it will be run-time better, but code-time worse) to transform this matrix to Jordan normal form, and get a formula for the task.
•  » » » 7 years ago, # ^ |   +13 It turns out that just as with problem A, the solution can be found on Google along with an explanation.I wonder if there was a traffic spike to that page today...
•  » » » » 7 years ago, # ^ |   +6 It feels that it is better to learn searching by Google instead of practicing on sport programming :)
•  » » » » 7 years ago, # ^ |   +2 Or you can do it that way.
•  » » » 7 years ago, # ^ |   +8 if you are referring to http://codeforces.com/contest/185/problem/B, it's just an application of Lagrange multiplier.very similar problem is given in Project Euler -- Problem 190.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +20 Or just use AM-GM inequality:Assume that a, b, c are not zero: s/(a+b+c) = (a(x/a)+b(y/b)+c(z/c))/(a+b+c) >= ((x/a)^a*(y/b)^b*(z/c)^c)^(1/(a+b+c)) = (x^a*y^b*z^c)^(1/(a+b+c))/(a^a*b^b*c^c)^(1/(a+b+c)) Equality holds when x/a = y/b = z/cEdit: Thanks wack-a-mole for pointing out my error.
•  » » » » » 7 years ago, # ^ |   0 Shouldn't that be s/(a+b+c) = (a(x/a)+b(y/b)+c(z/c))/(a+b+c) >= ((x/a)^a*(y/b)^b*(z/c)^c)^(1/(a+b+c)) = (x^a*y^b*z^c)^(1/(a+b+c))/(a^a*b^b*c^c)^(1/(a+b+c)) ? (The difference is 1/(a+b+c) instead of 1/abc in the RHS of the inequality)
•  » » 7 years ago, # ^ |   +14 but algorithm is a branch of math...
•  » » » 7 years ago, # ^ |   +17 I respect math, but I find that algorithmic programming & logic tasks are different than calculating logarithms and using numeric math theorems.
•  » » » » 7 years ago, # ^ |   +14 There is a lot of number theory problems in algorithm contest. Got an AC of most those problems only needed a few lines. Just because the number theory is more discrete than calculus? But no one promise that all the problems is discrete ? I stand ready to meet new challenges and adventures in contest.
•  » » 7 years ago, # ^ |   +5 I used ternary search on B. (I got WA because of a silly precision error not related specifically to using ternary search, after fixing it, I pass)
•  » » » 7 years ago, # ^ |   +5 just because x+y+z = S+1e-9 :(
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +5 I've also just managed to get my failing simulated annealing solution to pass, after changing the code to use iostreams instead of cstdio.
•  » » » 7 years ago, # ^ |   -8 Just because I output #.-INF when the a, b, c are all zeros.
 » 7 years ago, # |   -7 "Problem scores will be as always." is really misleading information, there are at least 3 score strategies — the one with constant score for each problem (defined by author), dynamic max scores and ACM scores. Also in constant score strategy there could be problems with equal max score (f.e. 500, 1000, 1500, 1500, 2500), so it's not always the same ;-)
 » 7 years ago, # |   +23 Must write 12 digits after decimal point in order to got problem B right :| I don't think we need this tricky in an easy problem. It took me a lot of time thinking why my solution is wrong, and I don't have time to work on the other (more interesting) problems. :(
•  » » 7 years ago, # ^ | ← Rev. 2 →   -6 I was looking for such case, where rounding is problem, do you have some? I'm sorry, wrong div again O:-)
•  » » 7 years ago, # ^ |   +11 Yeah I wonder how the tolerance for div1 problem B works... My wrong answer was because the outputs summed to 814.0000000010 when S was 814. I thought it would be fine since ln(814.0000000010) — ln(814) < 1e-6.
 » 7 years ago, # |   -17 WOW!!! BLAZING SYSTEM TESTS :)
 » 7 years ago, # |   +204 For Div1 problem C, what should the output be for the following input? 6 1 1 2 2 1 1 1 1 2 2 1 1 2 4 2 4 2 2 2 2 2 4 10 4 4 4 8 I thought the answer should be "Fat Rat", since all oats have to fall to the bottom to make the last scale break, but to make the two scales on the 5-th row both break, we need to have the 3-rd oat fall to (5,1) and 4-th oat fall to (5,2). But then (2,3) scale have to fall to both left and right, and doesn't satisfy the condition in the problem.BUT the judge solution outputs "Cerealguy" (I know this since I wrote a solution that pass pretest, and hack other people's code with this testdata). Is there anything wrong in my understanding of the problem?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +2 -
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I find no mistake in your explanation. Are you sure with your hack input?UPD : It turns out that judge solution is really wrong.
•  » » » 7 years ago, # ^ |   +37 My solution, which passes system tests, fails this test.
•  » » 7 years ago, # ^ | ← Rev. 2 →   -27 My understanding of this case is:(deleted wrong stuff that was taking up space).
•  » » » 7 years ago, # ^ |   0 2 0 2 2 2 | | | | | 2 4 2 4 2 Fourth 2 won't break the scales.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 sorry, it was wrong
•  » » 7 years ago, # ^ | ← Rev. 2 →   +58 I asked the admin about a similar test (attached) after the match. The conclusion was that the author's solution is wrong ( :( ) and they are now trying to find a fix for this. 6 1 1 1 1 1 1 1 9 1 1 9 1 1 9 1 9 1 1 1 1 1 2 9 2 2 2 4 
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -14 Edit: Sorry, I misread it.
•  » » » 7 years ago, # ^ |   0 Does anyone's solution return the correct answer for these two tests?
•  » » » » 7 years ago, # ^ |   0 Mine does: 1658921
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +16 61 0 2 4 0 11 9 2 4 9 11 9 1 9 11 1 1 1 3 4 1 3 5 8This test case should output Fat Rat, But your code output Cerealguy
•  » » » » » » 7 years ago, # ^ |   +5 Hack announcement ***** Unfortunally, your solution on C has been hacked :(
•  » » » » 7 years ago, # ^ |   +66 You know what? It seems like the best solution is mine. It's a coded in last minute and submitted for fun random solution, which got WA 49 (the same test as mentioned above). xDAnd here is the star: solution.But it is possible to hack it, of course :)
•  » » » » » 7 years ago, # ^ |   +5 Funny, I wanted to hack it, but didn't manage to do it in the last minute because of slow connection. Now that I tried it locally, it gave the correct answer on my case.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +30 I suggest you to replace 10024 with 7474, 7744 or some "lucky" numbers :)
•  » » » » » » 7 years ago, # ^ | ← Rev. 3 →   0 Your joke is not very funny, as well as this little statistic: Using 1 (one) iteration my solutions is getting WA 44; solutionUsing 47 iterations my solutions is getting WA 49, as well as with 10024 (or 7474 or 7744 like you said).Sad :(
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Mine does too: http://codeforces.ru/contest/185/submission/1659598 But it fails the test81 1 1 1 1 1 1 11 1 1 1 1 1 1 12 1 9 1 1 1 23 9 1 9 1 33 1 9 9 44 9 9 44 9 44 48 (returns "Fat Rat", and the correct answer is "Cerealguy")
•  » » » 7 years ago, # ^ |   +11 So as it seems this is going to be unrated? Strange — two consecutive rounds (#117, #118), both having wrong author solutions.
•  » » » » 7 years ago, # ^ |   -31 this should be rated for division 2. there were only two people who got this correct; also, they should fix the solution and redo the system test.it's highly disappointing otherwise; I think people in the community will start losing respect for CodeForces if the contest has problem, where the author's/test's solutions are wrong.
•  » » » » 7 years ago, # ^ |   -18 iff there is a test case in the system case that does not work using the judge solution should the decision of unrating the contest arise; even then, re-doing the system test may be a best option, to salvage people who did well in the contest.
 » 7 years ago, # |   +18 I got precision error in problem B even after printing 8 digits after decimal.I think in such problems the precision of output should be specified in the problem statement.
•  » » 7 years ago, # ^ |   -8 it was 'indirectly' given in the problem statement in terms of log; I calculated that printing 10 after decimal would be barely sufficient.
•  » » » 7 years ago, # ^ |   0 or you can say 'implicitly' instead of 'indirectly' :)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 How did you get 10 digits? Do keep in mind it's natural logs.
 » 7 years ago, # | ← Rev. 2 →   0 Hello coders,is there a good tutorial about matrix construction for computation of sequences as in div2 C problem? I tried to find the matrix, but failed, so I solved it later using formulae.Thanks ;-)
•  » » 7 years ago, # ^ |   +8 Let A and B be numbers of up and down triangles. Then the transformation after 1 year is (A,B) -> (3*A+B,3*B+A). It is exactly transformation given by matrix T = ((3,1),(1,3)). Now you can calculate T^n % p, and write out sum of it first row.
•  » » » 7 years ago, # ^ |   0 But I'm not interested in that one concrete case. I'd like to know how to find such matrix in the future for another recurrent sequence...
•  » » » » 7 years ago, # ^ |   0 You want to find y_n. You should introduce some additional variables x^1_i,..,x^m_i, so that you (y_{i+1}, x^1_{i+1}, ..., x^m_{i+1}) from (y_{i}, x^1_{i}, ..., x^m_{i}) is linear. Now you can write this dependence as multiplication by matrix, and use fast pow.
 » 7 years ago, # |   0 Many people enjoy hacking others..T^T I hate the input about “0”
•  » » 7 years ago, # ^ |   +21 Why? It gives you a chance to fix your code. I would have scored 0 points if yeputons hasn't been kind enough to hack my initial wrong solution :)
 » 7 years ago, # |   +7 Is the contest rated?
 » 7 years ago, # |   0 Could any one explain the logic behind the problem D Div-2 ???
•  » » 7 years ago, # ^ |   -13 do the calculus..
•  » » 7 years ago, # ^ |   0 For example, ternary search 1661095
•  » » 7 years ago, # ^ |   +11 @codeKNIGHT: You can use Cauchy Inequality One way to use it is to write x^a = (x/a)^a * a^a, and similar with y^b, z^c, then use Cauchy on P = x^a * y^b * y^c. We have the maximum value of P when x/a = y/b = z/c = (x+y+z) / (a+b+c) = S / (a + b + c)
•  » » » 7 years ago, # ^ |   +13 could you explain more deeply.Are you sure Cauchy Inequality. May be you actually meant Cauchy-Shwartz or Cauchy-Buniakovsky ?
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   +10 I don't know what it's called exactly in the world, but in my country we call this "Cauchy Inequality": ((a1 + a2 + ... +an)/n)^n >= a1*a2*...*an for all non-negative numbers a1, a2, ..., an. Equality is hold when a1 = a2 = ... = an. You can try to apply it here: P = x^a * y^b * z^c = a^a * b^b * c^c * (x/a)^a * (y/b)^b * (z/c)^c = a^a * b^b * c^c * x/a * ... * x/a * y/b * ... * y/b * z/c * ... * z/c <= a^a * b^b * c^c * ((x/a + ... + x/a + y/b + ... + y/b + z/c + ... + z/c) / (a + b + c)) ^ (a + b + c) = a^a * b^b * c^c * (S / (a + b + c))^(a + b + c)Edit: I think its name is AM-GM as peter50216 said in the post above :)
•  » » » » 7 years ago, # ^ | ← Rev. 5 →   +13 In my country (pele is from the same country as me) we use "Cauchy inequality" to talk about the inequality:(a+b)/2 >= sqrt(a*b)(and also its general form)I'm not sure about the international name of it :)Edit: sorry about the double explanation. I typed so slowly :(
•  » » 7 years ago, # ^ |   0 You can use Lagrange's method
 » 7 years ago, # |   +53 In problem B, I failed a case because the sum x+y+z exceeded S slightly.However, the statement explains how it will deal with precision errors. "A natural logarithm of distance from the center of the Universe to the given point in the metric of mushroom scientists shouldn't differ from the natural logarithm of the maximum distance by more than 10 ^- 6"IMHO, things should have been different. There shouldn't be a part that requires exact precision and another part that does not. It made me think that the only check I had to comply with in regards to precision was the logarithm one (and that case that my first solution fails, gives an answer with a logarithm that is within 10 ^- 6 of the optimum answer).Another thing I mentioned to organizers during the contest. In one part, it says that 0^0 = 1. And in the other, log(0) = -inf. This was quite an ambiguity, because 0^0 suggests you to use X=0 when a=0, but if log(0) is minus infinite then the logarithm of you using 0 would be -infinity.IMHO, instead of including arbitrary definitions for undetermined values, it was better to avoid a,b,c,s != 0 altogether. They did not really add that much to the problem (besides of the ambiguity).
•  » » 7 years ago, # ^ |   0 I agree to vexorian completely. And, there's one more thing I want to say.My first submission failed on pretest, and the Judgement Protocol says: Test: #7, time: 30 ms., memory: 1384 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER Input 7 8 2 2 Output 4.666666667 1.166666667 1.166666667 Answer 4.666666666666667 1.1666666666666667 1.1666666666666667 Checker Log wrong answer X+Y+Z should be <= S. Found 7.0000000010. Why 4.666666667 + 1.166666667 + 1.166666667 > 7 AND 4.666666666666667 + 1.1666666666666667 + 1.1666666666666667 <= 7?There's hidden output constraints? Or the judge's solution wrong?
 » 7 years ago, # | ← Rev. 2 →   -7 div2 problem d, just amazing! Who can explain why?int main(void){ int S,a,b,c; cin >> S >> a >> b >> c; if(a == 0 && b == 0 && c == 0){ printf("0.0 0.0 0.0\n"); return 0; } double x = a / (double)(a + b + c) * S; double y = b / (double)(a + b + c) * S; double z = c / (double)(a + b + c) * S; printf("%.20f %.20f %.20f\n", x, y, z); return 0;}
•  » » 7 years ago, # ^ |   +8 Arithmetic Mean >= Geometric Mean
•  » » 7 years ago, # ^ |   +14 so using Lagrange multiplier idea, we want to maximizef(x,y,z) = x^a y^b z^c subject to x+y+z<=S; so,we have Lambda(x,y,lambda) = x^a y^b z^c + lambda(x+y+z-S).Now, differentiate this with respect to x,y,z,lambda assuming none of a,b,c is zero (otherwise, it becomes equation in 1 or 2 variable, which is simpler than this problem).ax^(a-1) y^b z^c + lambda = 0 bx^a y^(b-1) z^c + lambda = 0 cx^a y^b z^(c-1) + lambda = 0 x+y+z-S = 0 (4)then,-lambda = ax^(a-1) y^b z^c = bx^a y^(b-1) z^c = cx^a y^b z^(c-1).now, factoring out x^(a-1) y^(b-1) z^(c-1), we observe that ayz = bxz = cxyso, setting xyz = P (and assuming x,y,z are non-zero), we can havea/x = b/y = c/zso, from here, it's obvious thaty = b/a x z = c/a xnow, notice thatx = (a/(a+b+c))S using (4); by symmetry, we deduce the other guys; when a+b+c=0, we notice that a=b=c=0, which means we can choose w/e respecting the constraint a+b+c<=S.
•  » » » 7 years ago, # ^ |   0 btw, for more variable, we have, obviously, xi = ai/(sum ai) S, which is really what this problem is trying to get at (at least I thought).
•  » » » 7 years ago, # ^ |   0 Thanks,
•  » » 7 years ago, # ^ |   0 lagrange multiplier method, try to google or baidu this.
 » 7 years ago, # |   0 hi i saw a solution accepted in problem A and i have a test with fail , what have to do in this case?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 Just resend newer solution.UPD: if it's your solution ;)If it's other's solution — you can double click on his solution, then press hack and send a test.
•  » » 7 years ago, # ^ |   +3 you should check it again and if you are sure post it here
 » 7 years ago, # |   0 i think something wrong with java compiler on codeforce. i get wrong answer on test 1 when in my compiler(eclipse jdk6) gives right answer. damn it :@ link to solution
•  » » 7 years ago, # ^ |   0 yor compareTo is incorrect. http://codeforces.ru/contest/186/submission/1662152
•  » » 7 years ago, # ^ |   +8 Your solution with modified comparator which gives the Accepted .Link
•  » » » 7 years ago, # ^ |   0 Oh..sorry I think I was a bit slow in typing :-(
•  » » 7 years ago, # ^ |   0 Thank you for your answers. i get finally : ) )) ) )
 » 7 years ago, # |   0 Hi I am seeing printf("%.16f %.16f %.16f", x,y, z); this is how people have solved the problemwhy this is wrong? printf("%f %f %f", x,y, z);I am talking about Codeforces Round #118 (Div. 2), problem: (D) Mushroom Scientists
•  » » 7 years ago, # ^ |   0 Insufficient precision.
•  » » » 7 years ago, # ^ |   0 But how was the precision decide in this case ?
 » 7 years ago, # |   +1 isn't the contest rated? why the rating doesn't update?
•  » » 7 years ago, # ^ |   -7 read the discussion above; the status, I think, is officially pending.however, you are right that division 2 SHOULD BE rated; to be strict, after rejudge; there aren't that many people who got affected by this fatal failure.
 » 7 years ago, # |   +1 What's up with the rating?
•  » » 7 years ago, # ^ |   +7 There are problems with Div1C/Div2E — jury's solution is incorrect. This problem is under investigation and round can be unrated.
•  » » » 7 years ago, # ^ |   0 So it WON'T be rated?
•  » » » » 7 years ago, # ^ |   +3 Probably it won't be.
•  » » » » » 7 years ago, # ^ |   0 Both divs?
•  » » » » » » 7 years ago, # ^ |   +2 May be no, because not so many people have solved E in Div2.
•  » » » » » » » 7 years ago, # ^ |   -8 I think that would be for the best :D
•  » » » » » » » 7 years ago, # ^ |   -14 I think this issue really only affected quite a bit in division 1, because many hackings and etc. failed and so on.Considering very small fraction of people solved it in division 2 (1 or less / room in general), I really think the effect of this problem is minimal when it comes down to even hacking, let alone getting the problem correct.Of course it'd be the best if the system test is re-run to make it perfect after getting the right solution out, I think division 2 should remain rated at the least.
 » 7 years ago, # |   -10 It's not rated in div2?
 » 7 years ago, # |   -7 So will it be rated?
 » 7 years ago, # |   +15 Please, stop worrying about rating. We are working under problem "C". But it seems, that it is NP-complete. But all tests was right, because of their simplicity — we check them out with brute-force algorithm. There is only problem with hacks.
•  » » 7 years ago, # ^ |   0 Please, stop worrying about rating. Contest will be rated anyway? o_O
•  » » » 7 years ago, # ^ |   -26 We are thinking now about it. But if it will be rated, we will return all the right solutions, that passed systests. (Because systests — are right.)
•  » » » » 7 years ago, # ^ |   +49 What are you thinking about?? All problems must have solutions! In other case contest must be unrated!
•  » » 7 years ago, # ^ |   +47 Don't you think that every problem must have reference solution which works correctly and fast enough for every test within given constraints? Otherwise it is unfair to the contestants.
•  » » » 7 years ago, # ^ |   -26 Yeap. I agree. And we are working under solution. And it seems, that brute-force algotithm works fine.
•  » » » » 7 years ago, # ^ |   0 do you mean Polynomial brute-force algorithm that will be TLE just to generate the outputs? It will be unfair to the contestants. (just like RAD has just said)
•  » » » » » 7 years ago, # ^ |   0 Nope. Which don't get TLE.
•  » » » » » » 7 years ago, # ^ |   +11 But you just said that this problem is NP-complete! How come it won't get TLE?
•  » » » » » » » 7 years ago, # ^ |   +11 Just good brute-force.
 » 7 years ago, # | ← Rev. 2 →   -10 And I think, people, who was minusing my post, don't understand how hard to make contest without collisions.Don't you understand, that other problems are high quality. Don't you?
•  » » 7 years ago, # ^ |   +29 We understand that the other problems are good (but still too mathy IMHO -- A, B, D are all about math). I also understand that it is hard to organize a contest without troubles. But you must accept that a fatal mistake on a single problem can ruin your contest and make people dislike it.
•  » » » 7 years ago, # ^ |   0 But it's very pitty, that they can't understand D and E, because of the problem in C.
•  » » 7 years ago, # ^ |   +50 It is just not very fair to rate a contest in which there was a impossible problem. In my case I am surprised that the rating is still being considered even after finding out that the problem is probably NP-complete. Just enjoying you had the luck that the system tests were weak to allow a very cropped bruteforce to pass does not really make it fine.And this is regardless of how well or bad the other problems were. The quality of the other problems was just ok and I liked the contest, but that does not mean it should be rated. There were even hacks with wrong outcomes. The existence of problem C/E has affected the contest results in a negative way.
 » 7 years ago, # | ← Rev. 2 →   +9 And do you want tutorial for this contest? (Without problem "C".)
•  » » 7 years ago, # ^ |   +8 I see no reason for not wanting to a tutorial.
•  » » » 7 years ago, # ^ |   -18 I think, because almost all don't like this contest. :-)!
•  » » » » 7 years ago, # ^ |   -15 I see that somebody doesn't want. Ok. I will not do it.
•  » » » » » 7 years ago, # ^ |   +16 No, no, everybody wants.
•  » » » » » » 7 years ago, # ^ |   -6 I see it by minuses. I'll do it anyway. Because D and E — very good problems.
•  » » » » » 7 years ago, # ^ |   +24 Not really. Some people "minus" your comment on "almost all don't like this contest". It may just mean that, they don't agree with this statement.And there are more upvote than downvote for "And do you want tutorial". So many indeed want to have it.Personally I wish to know how to approach D, E, and the tricks in implementing B (not using a closed-form) accurately.So please just let users some time to vote...
•  » » » » » » 7 years ago, # ^ |   0 There are no very special tricks in B for using, for example, ternary search. Except that you probably need to handle 0 cases separately and if you can predict that the check x+y+z is done without epsilons, you have to solve for S-1e-9 instead of S to avoid your x+y+z turning greater than S in the judge's comparison.I also checked against a*log(x)+b*log(y)+c*log(z) in the ternary search comparisons, but I am not sure this was needed.