lperovskaya's blog

Third elimination round Yandex.Algorithm-2015
By lperovskaya, history, 9 years ago, translation, In English

Round 3 will start on schedule at 13:00 on June 6, 2015 and will last 100 minutes.

Participation might bring to you one of the 512 competition t-shirts!

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

Comments Comments (33)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C: can you help me to find my mistake in my code(easy code)

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

What is the solution for C (Oceanic Battle) ?

and if anyone wants the solution for "A" , it is :

double a,b,c,d,e,f;
cin >> a >> b >> c >> d >> e >> f;
double theta = atan(a / b) * 180 / PI;
double s1 = (c + d) / 2.0;
double s2 = (e + f) / 2.0;
double ans = theta * s1 + (90 - theta) * s2;
ans /= 90.0;
printf("%.9lf\n" , ans);

The problem description (english) of "A" was not that good. I doubt how people got AC in 4 mins :O

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

    you should find the largest empty rectangle!

    and you can solve it with stack : code

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

      Does that code work? For this test case:

      5 5
1
0 1 5 4

      your code prints 15 (on my computer), but there are just 10 empty cells, the other 15 are covered by the given ship.

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

        It works correctly, because you are required to calculate "the maximum possible value of a single ship in the final arrangement". The only ship given in your testcase has area equal to 15.

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

          [insert facepalm here]

          So it seems I failed 2 problems because of trivial mistakes that have nothing to do with algorithmic part of the problems. I need to pay more attention to problem statements...

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

    what's the description of A? I still can't understand the falling process?

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

Are participants from other countries eligible for t-shirt prizes. Also how do they filter out top 500?? Any help will be appreciated.

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

    I think Indians are eligible. But isnt it cumulative of the 3 rounds ?

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

EDIT: resolved.

Can anyone tell me what's wrong with my F? Still feeling stumped...

If some w_i<0 or c_i=0, then answer 0. Otherwise, find the shortest path (by short we mean sum of w_i) from s to everywhere and from t to everywhere using Dijkstra (which works since w_i>=0).

If the shortest path from s to t is at most b-a, answer 0.

Otherwise, there are 2 options, take the cheaper one:

Option 1: Make some edge negative at cost (w_i+1)*c_i.

Option 2: Only reduce the cost of some single edge i (say, from a to b) and take the shortest path that uses that edge (shortest from s to a, shortest from b to t, w_i). The cost is (weight_of_this_path — (b-a))*c_i. Of course, check for overflow before multiplying (It's easy to prove that the answer is at most 10^18+10^9).

Getting WA8.

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

    Did you check the "s=t" case?

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

    Consider a simple case: two vertices connected by an edge. You need to go from vertex 1 to vertex 1 (note that this works both for indexing from 0 and from 1 :D). The initial and final annoyance is the same. You pass through the only edge twice, so the weight of that path is 2w, but you only need to pay wc, not 2wc.

    Since you need to take at least one edge, it may be worth it to take one edge twice; you pay c for that edge to decrease the annoyance over this path by 2, not 1. There may be other weird situations...

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

      Huh, where does it say I need to take at least one edge?

      Task statement says: "A path of length (l — 1) is a sequence of intersections..." and "The number l is considered to be positive.".

      So, a path of length 0 means l=1, which is positive, so it's fine. Right?

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

        Shit, that's what caused my solution to fail. If I add one line checking if I can make a 0-vertex path, it passes.

        You can still be in a situation where you want to take an edge twice, for example for a graph with edges 1-2 (w=0, c=inf), 2-3 (w=0, c=inf), 2-4 (w=0, c=1). If you want to go from 1 to 3 and a-b is -2, you want to take the path 1-2-4-2-3 and decrease the weight of edge 2-4. It's sufficient to decrease it to -1, with cost 1 and not 2.

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

          Yep, one option is to make any w negative and then just go back and forth on that edge many times. Option 1 in my OP.

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

            I see, it does fall under that case when paths of length 0 are allowed. I solved it the same way, then, so you probably just have a different trivial mistake.

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

              May you please explain, why this solution is OK? What if our current edge v1-v2 is a part of the shortest path from s to v1 or from t to v2?

              I used the same approach during the contest, got WA 3, and I thought that the reason is the above case. But it turned out, that I had some other stupid bugs (s==t and long long overflow)

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

                If there are no negative cycles (after decreasing weights), the optimal "path" doesn't contain an edge twice.

                Suppose that we went s-...-v1-v2-...-v1-v2-...-t (we traverse that edge at least twice in the same direction). Then, s-...-v1-v2-...-t is sufficient and doesn't have a bigger weight, so we can take this shorter path instead. After repeating this as long as necessary, we can be sure that no edge is traversed twice in the same direction.

                If we traverse it as s-...-v1-v2-...-v2-v1-...-t, we can take s-...-v1-...-t instead. We can again replace paths by shorter ones and after this, no edge is traversed twice.

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

        Yes, you are right. Test number 8 is the test with answer 1e18 + 1e9, are you sure you are not using infinity 1e18 ?

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

    did you swap u and v while checking the edge? you have to check it from both ends

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

OK, so what's the formula in E? I hate such problems.

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

    For odd N, when (N + 1) / 2 is full square, answer is sqrt((N + 1) / 2) / (N! * 2 ^ ((N — 1) / 2)). Otherwise answer is 1. For even N, when (N + 1) is full square, answer is sqrt((N + 1)) / (N! * 2 ^ (N / 2)). Otherwise answer is 2 ^ (N / 2) / N!. Here is AC solution http://pastebin.com/Zsi2m9Qw

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

"Participation might bring to you one of the 512 competition t-shirts!"

Does that mean I'll get a T-Shirt even if I did not get a single solution correct, since the number of participants was less than 512?

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

Is there any way to see/edit the address I used in the registration? I moved recently and would like to make sure there's my new address in case I win a T-Shirt.

Thanks.

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

On T-shirts:

a) to see if you are eligible for T-shirt — check this link:

https://contest.yandex.ru/algorithm2015/results/

if you are in first 512, then you should be eligible.

b) An hour ago I've got e-mail from Yandex, confirming that I've won the T-shirt. E-mail also contained link to special page where you can provide your address for delivery.

→ Reply