kingofnumbers's blog

By kingofnumbers, 8 years ago, In English

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!

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting problems.

How to solve VUDU ?

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

    Translate average for a subsequence to difference_of_partial_sums/nr_of_elements.

    s[i]=sum of first i elements.(s[i]-s[j])/(i-j)>=P with j<i. It reduces to s[i]-P*i>=s[j]-P*j. So the problem reduces to finding how many elements <= x there are,which can be done with BIT and compression(because numbers get very big)

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

      To make things easier, you can sort the prefix sum array and work with indices. No need to compress the BIT now.

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

      Archazey My solution is the same as you the only difference is that I am using segment tree but my solution is giving MLE.

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

    I solve it with meet in the middle method. It came out very similar to merge sort.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve SAVEZ?

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

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

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

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

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

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

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

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

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

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

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

            That's why we use unordered_map.

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

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

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

    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.

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    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

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

    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.

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

      Won't this get MLE?

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

        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.

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

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

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

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

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

»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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?

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

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

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

    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

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

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

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

        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!

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

          Oh, I see. "Successful hacking attempt at HellKitsune's solution", I guess ;)

          Anyway, congrats on winning the contest!

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

            Thanks! It feels like cheating a bit though >.<

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

    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.

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

      Could you share your code on this problem please ? I've been trying to use your idea but cannot make it run faster than 2.6s.

»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

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

    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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Inclusion&Exclusion Principle + BitMask in problem B?

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

    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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Artur is geometry?

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

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

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

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

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

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

      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?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    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;
    }
    
»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

It gets WA on 1C.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is SIGABRT?