Aksenov239's blog

Codeforces Round #118
By Aksenov239, 13 years ago, translation, In English

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.

  • Vote: I like it
  • +26
  • Vote: I do not like it

Comments Comments (137)
| Write comment?
»
13 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

And are there dynamic problem max scores used?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same question as Betlista. How about the scores and order of problems?

    → Reply
»
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it

What about the ordering of the problems? Are they arranged in the order of difficulty?

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hate hack announcement on prob A because of I misunderstanding with the problem :(

→ Reply
»
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I understood "A" from the very beginning. Also, didn't see any problem with description in "C". Seems that problems were with translation=)

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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.

      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -48 Vote: I do not like it

    You are looking answers for contest problems on google? Hm...

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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".

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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)...

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it +35 Vote: I do not like it

          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!

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it -15 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              13 years ago, # ^ |
                Vote: I like it -17 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                13 years ago, # ^ |
                  Vote: I like it +14 Vote: I do not like it

                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.

                → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it

          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.

          • How about contests like the one in which you had to learn how to code in INTERCAL before submitting something? You needed external help by default...
          → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I agree. So what do you think about this contest?

        → Reply
»
13 years ago, # |
  Vote: I like it +84 Vote: I do not like it

Problem B — this is programming or math contest?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Common, it was very simple formulae, you can ask the same for C...

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can somebody explain the solution of B?

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is binpow solution better ?

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          better than what? my solution is binpow, because you can calculate it for O(n)

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            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.

            → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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...

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        It feels that it is better to learn searching by Google instead of practicing on sport programming :)

        → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Or you can do it that way.

        → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      if you are referring to http://codeforces.me/contest/185/problem/B, it's just an application of Lagrange multiplier.

      very similar problem is given in Project Euler -- Problem 190.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
        ← Rev. 2   Vote: I like it +20 Vote: I do not like it

        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/c

        Edit: Thanks wack-a-mole for pointing out my error.

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)

          → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    but algorithm is a branch of math...

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      I respect math, but I find that algorithmic programming & logic tasks are different than calculating logarithms and using numeric math theorems.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        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.

        → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      just because x+y+z = S+1e-9 :(

      → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      I've also just managed to get my failing simulated annealing solution to pass, after changing the code to use iostreams instead of cstdio.

      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Just because I output #.-INF when the a, b, c are all zeros.

      → Reply
»
13 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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 ;-)

→ Reply
»
13 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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. :(

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it -6 Vote: I do not like it

    I was looking for such case, where rounding is problem, do you have some? I'm sorry, wrong div again O:-)

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
»
13 years ago, # |
  Vote: I like it -17 Vote: I do not like it

WOW!!! BLAZING SYSTEM TESTS :)

→ Reply
»
13 years ago, # |
  Vote: I like it +204 Vote: I do not like it

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?

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    -

    → Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I find no mistake in your explanation. Are you sure with your hack input?

    UPD : It turns out that judge solution is really wrong.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +37 Vote: I do not like it

      My solution, which passes system tests, fails this test.

      → Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it -27 Vote: I do not like it

    My understanding of this case is:

    (deleted wrong stuff that was taking up space).

    → Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +58 Vote: I do not like it

    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
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it -14 Vote: I do not like it

      Edit: Sorry, I misread it.

      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Does anyone's solution return the correct answer for these two tests?

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Mine does: 1658921

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
          ← Rev. 2   Vote: I like it +16 Vote: I do not like it

          6

          1 0 2 4 0 1

          1 9 2 4 9 1

          1 9 1 9 1

          1 1 1 1

          3 4 1

 3 5

  8

          This test case should output Fat Rat, But your code output Cerealguy

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            Hack announcement ***** Unfortunally, your solution on C has been hacked :(

            → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +66 Vote: I do not like it

        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 :)

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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.

          → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
          ← Rev. 2   Vote: I like it +30 Vote: I do not like it

          I suggest you to replace 10024 with 7474, 7744 or some "lucky" numbers :)

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            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 :(

            → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Mine does too: http://codeforces.me/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")

        → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      So as it seems this is going to be unrated? Strange — two consecutive rounds (#117, #118), both having wrong author solutions.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it -31 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it -18 Vote: I do not like it

        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.

        → Reply
»
13 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    it was 'indirectly' given in the problem statement in terms of log; I calculated that printing 10 after decimal would be barely sufficient.

    → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ;-)

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Many people enjoy hacking others..T^T I hate the input about “0”

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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 :)

    → Reply
»
13 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Is the contest rated?

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could any one explain the logic behind the problem D Div-2 ???

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    do the calculus..

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For example, ternary search 1661095

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    @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)

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      could you explain more deeply.

      Are you sure Cauchy Inequality. May be you actually meant Cauchy-Shwartz or Cauchy-Buniakovsky ?

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
        ← Rev. 3   Vote: I like it +10 Vote: I do not like it

        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 :)

        → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
        ← Rev. 5   Vote: I like it +13 Vote: I do not like it

        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 :(

        → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use Lagrange's method

    → Reply
»
13 years ago, # |
  Vote: I like it +53 Vote: I do not like it

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).

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

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;

}

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Arithmetic Mean >= Geometric Mean

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks,

      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lagrange multiplier method, try to google or baidu this.

    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hi i saw a solution accepted in problem A and i have a test with fail , what have to do in this case?

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    you should check it again and if you are sure post it here

    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Insufficient precision.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But how was the precision decide in this case ?

      → Reply
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

isn't the contest rated? why the rating doesn't update?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    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.

    → Reply
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What's up with the rating?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    There are problems with Div1C/Div2E — jury's solution is incorrect. This problem is under investigation and round can be unrated.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So it WON'T be rated?

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Probably it won't be.

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Both divs?

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            May be no, because not so many people have solved E in Div2.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              13 years ago, # ^ |
                Vote: I like it -14 Vote: I do not like it

              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.

              → Reply
»
13 years ago, # |
  Vote: I like it -10 Vote: I do not like it

It's not rated in div2?

→ Reply
»
13 years ago, # |
  Vote: I like it -7 Vote: I do not like it

So will it be rated?

→ Reply
»
13 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please, stop worrying about rating.

    Contest will be rated anyway? o_O

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      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.)

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +49 Vote: I do not like it

        What are you thinking about?? All problems must have solutions! In other case contest must be unrated!

        → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      Yeap. I agree. And we are working under solution. And it seems, that brute-force algotithm works fine.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Nope. Which don't get TLE.

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            But you just said that this problem is NP-complete! How come it won't get TLE?

            → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

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?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But it's very pitty, that they can't understand D and E, because of the problem in C.

      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    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.

    → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

And do you want tutorial for this contest? (Without problem "C".)

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I see no reason for not wanting to a tutorial.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      I think, because almost all don't like this contest. :-)!

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it -15 Vote: I do not like it

        I see that somebody doesn't want. Ok. I will not do it.

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          No, no, everybody wants.

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it -6 Vote: I do not like it

            I see it by minuses. I'll do it anyway. Because D and E — very good problems.

            → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it +24 Vote: I do not like it

          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...

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply