Блог пользователя kostka

Автор kostka, 4 года назад, По-английски

This is just to remind you that the second round of this year's Code Jam will take place today (5/16) at 14:00 UTC.

1,000 highest-ranked contestants advance to the third round and you will receive the famous Code Jam tee if you are within these 1,000 contestants.

https://g.co/codejam

Good luck, have fun!

  • Проголосовать: нравится
  • +116
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

The round starts in 45 minutes.

»
4 года назад, # |
Rev. 5   Проголосовать: нравится -50 Проголосовать: не нравится

Sorry ,just a little misunderstanding ..

»
4 года назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

The constraints for B were a bit unfortunate, I think it would have been preferable to include a second visible set with positive values of $$$X$$$.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +143 Проголосовать: не нравится

    It would also have been helpful to have a test case in D where some of the numbers were not 1 ...

    (I was super lucky in the sense that I was doing a problem quite similar to D just before the contest, and that I managed to catch an error 5 min before the end of the contest without actually constructing additional test cases...)

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve B2?

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
    1. Divide vertices on two sets: 1) x < 0 (for those vertices set x = -x); 2) x > 0.
    2. Sort both sets in non-descending order.
    3. Now we should add vertices to graph (which initially contains only vertex 1) and note time of its adding (initially 0). If value of next vertex from set 1 are less or equal to the number of currently added vertices (initially 1) than add it (increase time by 1 if value is equal to the number of currently added vertices) else add vertex from other set (set time equal to vertex's value).
    4. Continue until both sets become empty.
    My AC solution
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    The important idea is that, for a list of (numerical) latency, there always exists a way to set the weight on the edges conforming the latency requirement: for an edge (x-y), the weight is

    $$$|latency(x) - latency(y)|$$$

    if they are not equal, or any nonzero number otherwise.

    The rest is described as gultai4ukr

»
4 года назад, # |
  Проголосовать: нравится -92 Проголосовать: не нравится

Me waking up on 14:06 UTC

 (Thus, those who wear shirts are shameful)

»
4 года назад, # |
  Проголосовать: нравится +116 Проголосовать: не нравится

WTF, B has two samples? Don't do things like that...

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -43 Проголосовать: не нравится

    What's wrong with having to test your solution yourself?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +271 Проголосовать: не нравится

      What's wrong is putting the second sample at the end of the statement, way below the first sample, so that some people could have missed it (and some did).

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +34 Проголосовать: не нравится

        +1

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +111 Проголосовать: не нравится

        LOL, I didn't notice it too, until now.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +149 Проголосовать: не нравится

        Breaking news: According to Google UI/UX team working on the GCJ website, this is a great decision that will attract more people due to how user-friendly it is.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I did and it costed me the qualification because of a stupid mistake when copy pasting part of the code. This is so frustrating

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I still don't get it. I also didn't notice it until now but I don't know how it affected the competition.

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +95 Проголосовать: не нравится

    And no sample for D-hard. I would understand this from some random competition but I always treated GCJ as the best competition in the world and now this shit...

    EDIT: well, it's obviously a small detail in the whole competition but next time I would be happy to see useful samples. It makes the competition less random. (I had another opinion a few years ago btw.) It's just hard to imagine organizers deciding that it's better not to provide a test for D-hard.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Could you help explain me why uncommenting line 41 in this source code gives WA for problem C?

https://pastebin.com/JkaeuBRi

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone have an idea of what's wrong with my solution for C? I've tested this with tens of thousands of random inputs against Scott Wu's solution and I can't find a case that makes it fail.

Code

Edit: I got it to work after reading the analysis, but I'm not exactly sure why my solution is wrong.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Probably overflow.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Testing cases with large coordinates also doesn't seem to work...

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +49 Проголосовать: не нравится

    Random tests are shit in this problem, you won't get any special combinations of collinear points.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      I also did random tests with small coordinates to try to increase the chances of those. I figured with 7 points there aren't that many combinations and using points in a 20x20 square should hit at least some of them. Manual testing also didn't work.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    I Think this is wrong:

    if (one == 0 && even > 1)
    	{
    		total--;
    	}
    

    Try this:
    answer is 6

    1
    6
    0 0
    1 0
    100 10
    110 10
    1000 15
    1100 15
    
»
4 года назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Can someone help me to understand the following case for the third problem (Wormhole in One)?

1
7
0 0
0 2
0 3
0 4
0 5
8 8
11 11

I see accepted solutions printing $$$6$$$, but my solution outputs $$$7$$$ and here's how:

Connect points $$$(0, 0) - (0, 5)$$$.

Connect points $$$(0, 3) - (8, 8)$$$.

Connect points $$$(0, 4) - (11, 11)$$$.

Here is a figure to visualize the scenario. The same colored points are connected.

Now from the point $$$(11, 11)$$$, we hit the ball straight up. It first goes to $$$(0, 4)$$$ because they are connected, from there to $$$(0, 5)$$$, from there to $$$(0, 0)$$$ because of the wormhole, to $$$(0, 2)$$$, then $$$(0, 3)$$$ which teleports it to $$$(8, 8)$$$ finally visiting all the holes.

What am I missing here? Did I misunderstand the problem?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

    The ball gets stuck at $$$(0,2)$$$ for your construction. When a ball enters a hole that is not connected to another hole, it stops.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    The ball stops at (0, 2). Note they are holes, so once the ball hits a hole, it will stop unless the hole being connected to another hole via a link.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      Thanks FieryPhoenix and ll931110, my bad. This simple misunderstanding ruined the contest for me, should have re-read the statement again instead of trying to debug correct solution of a different problem.

»
4 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Have you noticed the second sample test in problem B?

strawpoll

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +43 Проголосовать: не нравится

Well, here is my screencast with some commentary. I tried to solve all problems and ended up getting the 525th place https://www.youtube.com/watch?v=kvzvsyUZp7Q

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +62 Проголосовать: не нравится

My solution in D large was similar to my recent problem: Giant Penguin

At first, we should note that we can change $$$CC$$$ to $$$(CC)$$$ by adding additional brackets with zero $$$l_i, r_i$$$ and infinite $$$p_i$$$. Like that, we can change $$$CCCCC$$$ to $$$(((CC)C)C)C$$$, so our "bracket tree" will be binary.

In this binary tree, we can find a subtree with the size $$$\frac{1}{3}n \ldots \frac{2}{3}n$$$. We can note that if we delete two border vertices of the segment corresponding to this subtree, we will get two independent problems with sizes $$$\leq \frac{2}{3}n$$$, so we can build something similar to "centroid decomposition," like in the problem that I've mentioned before.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Why did I get WA instead of RE for index out of bound issue in problem B?Such misguiding verdict cost me a lot of time.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    C++ arrays have garbage values in them outside the declared bounds. As far as I know, declaring arrays in C++ is simply allocating a bunch of memory (unlike Java, where arrays are objects and out-of-bound access is an undefined operation and will throw an exception). So if you don't go too far, the compiler may not even notice.

    I remember in problem B of round 1A (Pascal Walk) I had an int[500][500] and I went as far as index 1000 in the first testcase, but got AC (lol), so it is just something to pay attention to.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится

      In fact different compilers give different verdict on the same issue.I once got RTE for exceeding memory limit.But I wish GCJ compiler would have been advanced enough to catch index out of bound issue.I wasted 45 minutes only to find I didnt declare enough memory.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится -6 Проголосовать: не нравится

        Btw, have you stress tested your code? I mean, it's unlikely you would get AC with out-of-bound behavior, so......

»
4 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

My screencast without many commentaries, where I learn that non-ac verdicts on sample tests aren't accounted in penalty and that trying to read numbers eternally from an empty stream under their constraints causes MLE, not TLE

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

I don't like hidden verdicts :(. Failed A's second test case because of integer overflow and lost my shot at a t-shirt.

What's wrong with immediate feedback?

  • »
    »
    4 года назад, # ^ |
    Rev. 5   Проголосовать: нравится +5 Проголосовать: не нравится

    Me also, strongly don'e like it, as I always write buggy code.

    Set instead of multiset in B, and 1e9 instead of $$$\sqrt{2e18}$$$ in A were enough to fail hidden tests in both and to kick me out of qualification. Although, my time was very enough and good.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +51 Проголосовать: не нравится

      Tho I don't like hidden verdicts as well, A could have been easily tested by trying out max values (I myself caught about 3 bugs related to this), so I think it's kinda unfair to blame the hidden verdicts for that.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +31 Проголосовать: не нравится

    Who said there is some mistake in immediate feedback. Each contest(or better, website) has its own way. Its nice that there are different variants of contests so its not boring with a same ICPC format.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Yes. There's nothing like the awesome atcoder where you can see all tests. Then Yandex where you can see the number of first failed test in all tests. Then the codejam and codeforces, but codeforces is bit better as the pretests are diverse. Then, the worst topcoder, where I even can't guarantee positive score. IT'S PERSONAL OPINION.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +41 Проголосовать: не нравится

    I actually miss the days when a lot more competitive programming contests were evaluating the skill of testing your implementation. In the long run I feel that it certainly helped me to write working code on the first try more often.

    So the last 15 minutes of this round, for example, instead of focusing on D.small, I specifically was testing my solutions (1-line max test for A, multiple manual tests for B.large since B.small is useless for testing that etc.). Every contest has different rules and you have to be able to adapt your strategy to each one of them.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

That moment when your A is 1 character away from being correct, and you miss an opportunity to make round 3 :(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I know that feel bro: screencast. Fixed one char and got AC 50 seconds after the end

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      That screencast is so sad yet op. You should get a t-shirt just for being closest to deserve making round 3 but not with video proof. Rip. At least you can probably make a failure meme template out of that lol.

»
4 года назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

Another way how to think about D-large:

Construct the weighted directed graph $$$G$$$ which is naturally implied by the problem. $$$G$$$ has treewidth $$$2$$$. In other words, there exists a tree $$$\mathcal{T}$$$ ("tree decomposition"):

  • whose vertices are subsets ("bags") of $$$V(G)$$$ of size at most $$$3$$$,
  • for any $$$uv \in E(G)$$$, there exists a bag containing both $$$u$$$ and $$$v$$$,
  • each vertex $$$v \in V(G)$$$ occurs in bags forming a subtree of $$$\mathcal{T}$$$.

For instance, the example test:

(The graph on the left consists of bronze and blue edges (actually, pairs of edges); blue edges move between adjacent characters, while bronze edges move between matching parentheses. Tree decomposition on the right.)

Now, the main idea of the algorithm boils down to the centroid decomposition of $$$\mathcal{T}$$$. In each recursive call, we find a centroid bag in $$$\mathcal{T}$$$ run (at most) $$$3$$$ Dijkstras from and $$$3$$$ Dijkstras to each vertex in this bag, answer the queries we can do, and carefully recurse with remaining queries. We still solve the problem in $$$O(n \log^2 n + q \log n)$$$ time.

I figured it might be worth mentioning about this method as it works for any graph with bounded treewidth ("looking kinda like a thick tree").

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

    Why do you complicate things introducing treewidth even though you can say that removal of any pair of matching parentheses disconnects graph, so you can take centroid of the tree on the left and forget about the right one? Of course I am a big fan of treewidth but I don't see any profit here

    EDIT: OK, I understand, removal of any pair of matching parentheses indeed disconnects the graph, but not in the way as the left tree disconnects, cause brothers of removed vertex stay connected. Now I see the point.