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

Автор kingofnumbers, 9 лет назад, По-английски

Hello!

This is to remind you about second round of Croatian open competition in informatics will be held tomorrow Saturday 07.11.2015. 14:00 GMT/UTC

link for the contest: COCI

let's discuss the problems after the contest ends.

Good luck and have fun!

UPD: results are out!

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

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

Interesting problems.

How to solve VUDU ?

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

How to solve SAVEZ?

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

    I solved it z-function + hash.. But I don't know correct this solution or not.

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

      I did it with hash only, and a map to store the longest sequence at that hash.

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

        Yeah it's exactly what I did, but I'm afraid that ML is too tight for double-hash.

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

        Ooh, yes.. for nothing i wrote this z-function, it can be easily check with hash :(

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

          memory limit is too strict!

          it could be done with aho-corasick with 26*maxn memory, that it is a bit bigger than a memory limit(64MB) :(

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

            That's why we use unordered_map.

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

              shit!

              I was too newbie for that :(!

              but I had guessed that I can use map, but I wondered it well be memory limit exceeded like previous ones!

              WHY?!

              how ever, thank you, teacher :)

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

    I solved it using two Tries. One for the original strings, and one for the same strings but reversed. Not sure if my solution is right though.

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

    Dynamic programming.

    First observation. For a subset,the property stated has to be respected just for adjacent words,it's easy to prove. So for i1,i2,....,ik, word i2 has to end and begin with i1, i3 with i2.....

    dp[i]=maximum subset from the first i elements where the last one is word i.

    To calculate that,for every prefix of length x of word i which is also a suffix of word i ,you want those words j (j<i) equal to that prefix (so it respects the property).Those words can be hashed and put in maps. And also in M[word] you store maximum dp of words with that hash number,because you want to maximize your dp[i].

    So briefly,dp[i]=max(1,max(M[word])),word being a prefix that is also suffix of word i

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

    Without hashes:

    Use trie. Let's put strings one by one in it, solving the problem for the given string at the same time. Once we added the string and calculated the answer for it, we will remember this answer in the node of the trie that corresponds to the end of this string.

    Processing a string: mark all positions i such that the first i characters are equal to the last i characters of the string. You can do it with z-function (or KMP if you prefer so). While moving through the trie, take a maximum of all previously remembered answers that lie on nodes which correspond to the marked positions. The answer for the current string is this maximum value plus one.

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

      Won't this get MLE?

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

        I stored transitions in map<int, int> nx[1024];

        When I wanted to find a transition, I did:

        int ind = ((s[i] - 'A') << 21) | pos;
        auto it = nx[ind & 1023].find(ind >> 10);
        

        Memory limit was stupid though.

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

          I used Trie without any space optimizations and did not get MLE. Weak test data?

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

            No, it should work without any space optimizations even with 64MB ML. That is, if you are using map<char, int> nx[2000000] and not int nx[2000000][26].

            For some reason though, I got run-time errors on pretests with 2 million maps, even though on my machine the solution consumed around 35MB. So I wrote the above and it passed, thankfully.

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

    Z-function + trie. BUT if there was more memory, at least 75 MB, then it can be solved with ONLY trie (no hash, no zf). Hint: try to decompose all strings, s[0]s[1]s[2]...s[n] -> s[0]s[n]s[1]s[n-1]...s[n]s[0].

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

Did anyone solve F (drzava)? I could only come up with a conceptual solution using Delaunay triangulation (to compute euclidean minimum spanning tree). That can't be the intended solution though, right?

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

    I tried to use kd-tree, but it works too slow even on random tests. Maybe in C++ it would be faster.

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

    One observation is that we never need more than K closest neighbours of the city (is it even correct? I only had 30 minutes to solve this task, so I didn't have much time to prove things). What I did is I took K closest cities by X, K closest cities by Y, and then merged the two lists and took K closest cities overall.

    Then you can do binary search for the squared distance, finding the connected components using only edges found above, and trying to find solution for the problem for each connected component separately.

    This works in N * K * log(MAX_DIST^2). Could still be too slow for 1 second, not sure.

    Edit: looks like this solution is not fast enough, or my implementation is slow. 96 points

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

      Pardon me, but could you elaborate on the "K closest cities by X, K closest cities by Y" part?

      I do understand that no more than k cities are necessary (pigeonhole principle) — but how does taking the k closest cities by x/y help?

      Consider the following points, with k = 2:

      0 0
      0 100
      0 101
      100 0
      101 0
      1 1
      2 2
      

      When inspecting (0,0) the k "closest" (in your x/y kind of sense) ones are the ones with the other coordinate being  ≥ 100. Here (1/1) and (2/2) should be taken, right?

      I believe I'm missing something really obvious here. Still, would you mind to explain? :)

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

        You are right, my solution is wrong >.<

        I got lucky to not receive any WA. Spent too much time making other tasks work (especially fitting D in ML), which strangely ended up being beneficial as I didn't think this solution through, else I wouldn't have coded it!

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

    Here's my solution, which receives full points after a small bug-fix:

    We binary search on D, so now we need to solve the problem of finding whether a given value of D works. This is in two parts: joining with union-find all points within distance D, and then applying knapsack to each component to test if some subset adds to 0 mod K.

    Part 1: Scan by x-value, maintaining a set sorted by y-value of all points with x-value at most D behind the leading line. Now for each point (a,b) in our scan, we iterate in the set through all points in this set with y-value in (b-D,b+D), and join to (a,b) all points within distance D. These are the points in the rectangle [a-d,a]x[b-D,b+D]. Note that by Pigeonhole, if we ever find a component of size at least K, we may stop and return a YES. This short-circuiting means (I think) that there can only be ~180 points in this box without more than K points lying in close proximity, and in most cases there should be much less.

    Part 2 modulo knapsack is quite easy, so of course this is where I made a bug.

    This solution is O(N*K*log(MAX_DIST)) but runs in less than 0.5 seconds on the test data.

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

What was the point of 64MB memory limit in SAVEZ? It made usage of data structures hard and the only option was to use hashing — which is more boring than "real" string algorithms.

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

    Don't be silly. Hashing is one of the most fundamental and most flexible techniques; that's why, it's as "real" as it gets.

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

Inclusion&Exclusion Principle + BitMask in problem B?

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

    You can just increment the bitmask, I think that will pass. I tried to optimize mine by adding the lowest bit and clearing the rest when there is a mismatch.

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

Artur is geometry?

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

    yes, it is. For any two segment, you check whether a segment has to be after the other segment and then sort them.

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

      It is right? But relations is not transitive...

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

        I solved it using topological sort on a graph where an edge i->j means that I have to remove i before j. The long thing is to create the graph but it can be done in O(N^2) comparing every pair of segments in O(1) [ here is the long thing, you have to consider some corner cases where the segments are vertical lines ]. Relation is transitive, i.e. if i < j and j < k --> i < k , that's why topological sort works (where a < b means that I have to remove a before b).

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

for third problem , what is neatest way (and bug-free) to check which segment is above the other between two segments (or stating that no one is above the other)

many people got WA on this problem, and I think most of them failed because of bug in that part of their codes

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

    I think it's not that neat, but let me share my solution:

    I first check if their projections on x axis intersect. If not, then they don't block each other. Then I think them as lines instead of line segments and find their equations. Then I choose the bigger one of left ends of segments as common x value that both have y values. I plug that common x into their equations. The line segment with the less value is the one which blocks the other, so we should remove it first. The only tricky situation is when a line segment doesn't have a slope. In that case, instead of using equation, we can use any value between y1 and y2 of that line segment.

    My code

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

    Maybe your algorithm is still correct. But some ARTUR test cases (e.g 10a) make the sticks touch each others at beginning. Therefore, the topological order determination make WA. I already send a clarification and hope for their correction of test data

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

      It didn't get WA, but it's because of my luck. If they can touch, this solution is wrong.

      Didn't problem say they can't touch?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    double solvey(int p, int x) {
      if (x1[p] == x2[p]) {
        return min(y1[p], y2[p]);
      }
      return 1.0 * (y2[p] - y1[p]) / (x2[p] - x1[p]) * (x - x1[p]) + y1[p];
    }
    bool covers(int p, int q) {
      // requirement: x1[p] <= x2[p] and x2[p] <= x2[q]
      // x does not overlap
      if (min(x2[p], x2[q]) < max(x1[p], x1[q])) return false;
      int z = min(x2[p], x2[q]);
      double yp = solvey(p, z);
      double yq = solvey(q, z);
      return yp < yq;
    }
    
»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What do you think is the problem of my solution for SAVEZ?

It gets WA on 1C.

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

What is SIGABRT?