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.
And are there dynamic problem max scores used?
Same question as Betlista. How about the scores and order of problems?
What about the ordering of the problems? Are they arranged in the order of difficulty?
Yes.
I hate hack announcement on prob A because of I misunderstanding with the problem :(
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.
I understood "A" from the very beginning. Also, didn't see any problem with description in "C". Seems that problems were with translation=)
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.
You are looking answers for contest problems on google? Hm...
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".
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)...
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!
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.
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.
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.
If you can come with a solution yourself, then does the problem really teach you that much?
If you search oeis and read the oeis explanation, does that mean you are not learning anything? oeis' entry about this seems quite interesting and you would be forced to learn a couple of things before implementing the formula.
Aren't you assuming that everyone's objective is to learn? In a contest with rating or prizes, sometimes the objective is do get a good performance. Because it IS a competition. And getting a good performance by using legal means makes you happy and proud.
Looking a sequence at oeis is actually quite a fair method to solve a problem. In fact, in the case of being a programmer, it is sometimes better not to reinvent the wheel. It is actually a skill to know yourself to be able to estimate when it is better to come up with a solution yourself, and when it is better to use a tool (oeis is a tool, as much as wikipedia and google).
I can assure you that a lot of guys had fuzzy memories about Lagrange multipliers today and used wikipedia to remember them. Hey, I actually did exactly that, but got confused when the Lagrange method in wikipedia used a = constraint instead of <= (Did not notice the obvious thing that in order for the result to be optimal then x+y+z=S). Without this confusion, I would have used wikipedia to solve D/B.
The ironic bit about this is shafaet_du's point is actually that problems shouldn't be googleable. Because he does not want anyone to be able to solve something by googling. So, in fact you two are arguing for the same thing. For a contest in which google isn't used to solve the problems.
But I do not really think the problem being googleable is a big issue by itself. It is a big issue when the problem is meant to be original. But this problem certainly was not meant to be original- just a linear recurrence, like any other.
Specially because oeis lists millions of sequences, and as such it is very difficult to make a linear recurrence problem that is easy and cannot be solved with oeis.
Is it really true that "At a certain level, browsing your brain is faster than browsing the web"?
I am not sure I would even remember STL syntax such as how to use upper_bound without google.
I agree. So what do you think about this contest?
Problem B — this is programming or math contest?
Common, it was very simple formulae, you can ask the same for C...
It's different. B is really about math
He meant problem B from div 1, not div 2.
Ou, I'm sorry, I didn't realize O:-)
Can somebody explain the solution of B?
Let
a_i
is number of /\ triangle, andb_i
is number of \/ triangle afteri
-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
Is binpow solution better ?
better than what? my solution is binpow, because you can calculate it for O(n)
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.
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...
It feels that it is better to learn searching by Google instead of practicing on sport programming :)
Or you can do it that way.
if you are referring to http://codeforces.net/contest/185/problem/B, it's just an application of Lagrange multiplier.
very similar problem is given in Project Euler -- Problem 190.
Or just use AM-GM inequality:
Assume that a, b, c are not zero:
Equality holds when x/a = y/b = z/c
Edit: Thanks wack-a-mole for pointing out my error.
Shouldn't that be
? (The difference is
1/(a+b+c)
instead of1/abc
in the RHS of the inequality)but algorithm is a branch of math...
I respect math, but I find that algorithmic programming & logic tasks are different than calculating logarithms and using numeric math theorems.
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.
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)
just because x+y+z = S+1e-9 :(
I've also just managed to get my failing simulated annealing solution to pass, after changing the code to use iostreams instead of cstdio.
Just because I output #.-INF when the a, b, c are all zeros.
Hi Aksenov239
"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 ;-)
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. :(
I was looking for such case, where rounding is problem, do you have some? I'm sorry, wrong div again O:-)
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.
WOW!!! BLAZING SYSTEM TESTS :)
For Div1 problem C, what should the output be for the following input?
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?
-
I find no mistake in your explanation. Are you sure with your hack input?
UPD : It turns out that judge solution is really wrong.
My solution, which passes system tests, fails this test.
My understanding of this case is:
(deleted wrong stuff that was taking up space).
Fourth 2 won't break the scales.
sorry, it was wrong
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.
Edit: Sorry, I misread it.
Does anyone's solution return the correct answer for these two tests?
Mine does: 1658921
6
1 0 2 4 0 1
1 9 2 4 9 1
1 9 1 9 1
1 1 1 1
This test case should output Fat Rat, But your code output Cerealguy
Hack announcement ***** Unfortunally, your solution on C has been hacked :(
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). xD
And here is the star: solution.
But it is possible to hack it, of course :)
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.
I suggest you to replace 10024 with 7474, 7744 or some "lucky" numbers :)
Your joke is not very funny, as well as this little statistic:
Using 1 (one) iteration my solutions is getting WA 44; solution
Using 47 iterations my solutions is getting WA 49, as well as with 10024 (or 7474 or 7744 like you said).
Sad :(
Mine does too: http://codeforces.net/contest/185/submission/1659598 But it fails the test
8
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
2 1 9 1 1 1 2
3 9 1 9 1 3
3 1 9 9 4
4 9 9 4
4 9 4
4 4
8
(returns "Fat Rat", and the correct answer is "Cerealguy")
So as it seems this is going to be unrated? Strange — two consecutive rounds (#117, #118), both having wrong author solutions.
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.
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.
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.
it was 'indirectly' given in the problem statement in terms of log; I calculated that printing 10 after decimal would be barely sufficient.
or you can say 'implicitly' instead of 'indirectly' :)
How did you get 10 digits? Do keep in mind it's natural logs.
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 ;-)
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.
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...
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.
Many people enjoy hacking others..T^T I hate the input about “0”
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 :)
Is the contest rated?
Could any one explain the logic behind the problem D Div-2 ???
do the calculus..
For example, ternary search 1661095
@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)
could you explain more deeply.
Are you sure Cauchy Inequality. May be you actually meant Cauchy-Shwartz or Cauchy-Buniakovsky ?
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 :)
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 :(
You can use Lagrange's method
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).
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:
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?
div2 problem d, just amazing! Who can explain why?
int main(void){ int S,a,b,c;
}
Arithmetic Mean >= Geometric Mean
so using Lagrange multiplier idea, we want to maximize
f(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 = cxy
so, setting xyz = P (and assuming x,y,z are non-zero), we can have
a/x = b/y = c/z
so, from here, it's obvious that
y = b/a x z = c/a x
now, notice that
x = (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.
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).
Thanks,
lagrange multiplier method, try to google or baidu this.
hi i saw a solution accepted in problem A and i have a test with fail , what have to do in this case?
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.
you should check it again and if you are sure post it here
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
yor compareTo is incorrect.
http://codeforces.net/contest/186/submission/1662152
Your solution with modified comparator which gives the Accepted .Link
Oh..sorry I think I was a bit slow in typing :-(
Hi
I am seeing
printf("%.16f %.16f %.16f", x,y, z); this is how people have solved the problem
why this is wrong? printf("%f %f %f", x,y, z);
I am talking about Codeforces Round #118 (Div. 2), problem: (D) Mushroom Scientists
Insufficient precision.
But how was the precision decide in this case ?
isn't the contest rated? why the rating doesn't update?
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.
What's up with the rating?
There are problems with Div1C/Div2E — jury's solution is incorrect. This problem is under investigation and round can be unrated.
So it WON'T be rated?
Probably it won't be.
Both divs?
May be no, because not so many people have solved E in Div2.
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.
It's not rated in div2?
So will it be rated?
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.
Contest will be rated anyway? o_O
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.)
What are you thinking about?? All problems must have solutions! In other case contest must be unrated!
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.
Yeap. I agree. And we are working under solution. And it seems, that brute-force algotithm works fine.
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)
Nope. Which don't get TLE.
But you just said that this problem is NP-complete! How come it won't get TLE?
Just good brute-force.
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?
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.
But it's very pitty, that they can't understand D and E, because of the problem in C.
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.
And do you want tutorial for this contest? (Without problem "C".)
I see no reason for not wanting to a tutorial.
I think, because almost all don't like this contest. :-)!
I see that somebody doesn't want. Ok. I will not do it.
No, no, everybody wants.
I see it by minuses. I'll do it anyway. Because D and E — very good problems.
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...
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.
Maybe I am writing this a bit too late. For the Triangle problem, you can solve without matrix exponentiation. Just form a recurrence relation in n of no of upper triangles. Solving it which is quite straightforward (but a little long) for anyone who knows basic math. The answer is 2^(n — 1) + 2^(2* n — 1). We can also think of a combinatorial argument for above answer which seemed to me a good exercise.