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

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

Hi.

4th Round of COCI contests take places at this time.

Contest site.

Note: You can discuss problems here, after contest end.

Update: Resault.

Winners

  1. fagu
  2. kennethsnow
  3. Xellos
  • Проголосовать: нравится
  • +49
  • Проголосовать: не нравится

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

Кто-то с Украины может зайти?

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

Can we submit our solutions after the contest?

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

Damn, got stuck for like 90 minutes on the fourth problem, while the fifth was a piece of cake to solve :(

How to solve it?

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

    Let the height of a strip be 1. The cuts are at heights , for 0 < ki < ai, and we want the number of distinct fractions among those.

    Let there be a fraction , with coprime x, y and x < y. If there's , then must be an integer; for coprime x, y, it means that y divides ai; this condition is also sufficient, and the number of satisfying x for the given y is φ(y).

    That means we need to sum up φ(y) for all distinct divisors y of at least one ai. For sufficiently small ai, computing φ(y) for all 1 ≤ y ≤ 100000 is easy, and to check a divisor's existence, we can use an array of bools denoting the existing values of ai and try the multiples of every y.

    But yeah, 4 and 5 should've been swapped. I think I spent about an hour or more on this.

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

      I also have similar solution, except when computing the number of distinct irreducible ( removed ) fractions, I just used O(N^2 * log N) precomputation and then just pasted the array in the code, since the limit is 1 MB.

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

        Coprime x, y means irreducible fraction.

        Precomputation: nice! It'd be funny if some future problem of COCI could be solved in O(1) like this :D

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

          Oh, OK, sorry, I misread the first paragraph, I thought it was needed mentioning there as well.

          But yeah, I was surprised when I found out the source limit is 1 MB, usually it's limited by 100 KB.

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

        Why can't we simply use this f(a * b) = f(a) * f(b) for coprime a and b? Am I missing something?

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

      Also we can count number of irreducible fractions using Inclusion–exclusion principle. My code

      I think this problem (problem D) is similar to SGU 370.

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

Oh yeah, 618 points! My best result so far, ever!

Short ideas of some tasks:

  • SUMO: binsearch the smallest k such that the graph formed by the first k edges isn't bipartite; bipartiteness can be checked with BFS

  • UTRKA: DP on (number of edges,vertex i,vertex j) gives the maximum advantage (can be negative) out of all paths from i to j, stopping the computation when there's a negative cycle and only adding edges to existing paths gives me 80% of points

  • COKOLADE: there only ways of how the array of "candies per capita" can look; iterate over the smallest k-s corresponding to them — for a given k, find the smallest k' > k such that some ; for a given k, only the tables with equal (candies per capita, integer division) socialize

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

    I have O(n3 * log2(n)) for last problem (pretty sure it is solvable in O(n3 * log(n))) time. I have 80% of points for this problem as well.

    Let i-th edge's weight be m[i]-s[i]. So we have to find shortest cycle with negative weight in this graph. Lets precalculate all minimal distances for n=1,2,4,8,16... edges using Floyd-Warshall algorithm. Then let's do binary search by the answer. Using precalculated information we can find shortest disctances between every pair of vertexes with exactly M edges between them in O(n3 * log(n)) time. If distance from i to i is negative for some i, than we have cycle of negative weight for current value of M.

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

      And for the reference, if you just use matrix multiplication, incrementing the size by 1 (so no need for binary search), you get 70% of points. Which seems quite a lot.

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

      How do you assume if there is a negative cycle with lenght M there have to be with lenght M + 1?

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

        There probably is some misunderstanding.

        If distance from i to i is negative for some i, than we have cycle of negative weight for current value of M.

        In this sentence I meant, that we have cycle with length not greater than M. If we have negative cycle with length M, than, obviously, shortest distance from i to i will be negative also for values bigger than M.

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

    Also, SUMO can be solved with DSU. For each component c, store the number of a component that should be colored in a different color than this component in adj[c]. Suppose an edge (a, b) comes in. If group(a) = group(b), then we output the number of the current edge. Otherwise merge group(adj[a]) with group(b), and group(adj[b]) with group(a).

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

      I think binsearch is the simplest solution for this. At least, I don't see any completely obvious greedy solution, although that was my initial guess. DSU is just unnecessarily much to code.

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

        No, not at all: http://ideone.com/OIgU8Y.

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

          Challenge accepted: http://ideone.com/wcbbCN

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

            You may have fewer lines, but those lines are much more complicated.

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

              It might look complicated, but it's based on a BFS, which is really simple to code when you know it (which probably anyone does before DSU). I also don't use typedefs and extensive defines, and don't put every variable in a static array, which would probably make it clearer, but I wouldn't be able to write it instantly.

              I'm not talking about lines — if I wanted to, I could cut down on them significantly, and so could gen on his. If you look at any BFS I've coded, it looks like this (with the "part" array and the few operations with it added). If you look at any binsearch I've coded, it also looks like this, and same with reading+graph construction in my codes. And I don't copy-paste.

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

                agree with Chortos-2 and besides it is also worth mentioning that at least I have DSU prewritten.

                upd: and also, BS is notoriously tricky XD

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

                  Imagine you go to a competition where pre-written code is not allowed. You can solve the problem in theory, but coding it takes too long or you make mistakes there, and so you can't solve the problem in question. Moral lesson: prewritten code = potential fail.

                  On the other hand, why not have pre-written binsearch, too, if it's so tricky? You pose a problem and one solution in your post. And once again, if you can write it quickly and correctly in any situation, it's not tricky.

                  I'm not saying people should write codes the same way I do. Everyone has their own style, but if you're able to instacode basic algorithms, it can give you a large edge.

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

                  Actually I have prewritten BS too

                  http://pastebin.com/MLXTSmuv

                  But, in fact I am not the "script-kiddie" kind of man :D. I don't use prewritten codes any more (excluding on CF and TC maybe where rating kinda matters). What I meant by my previous comment was that DSU is one of the data-structure you can type w/o thinking and quickly, while BS needs a special treatment (for me).

                  Lastly, I think ur right, for ambitious algorist implementation should be of no problem.

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

                  I guess it varies from person to person. Binsearch is just about getting the  ± 1 correct, which is easy if you use half-open intervals, and it's short. When coding DSU, I still need to think for a while sometimes.

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

                I agree with Xellos. By the way, I haven't thought about binsearch at all, so at the time was wondering why they have put DSU in the first place in a COCI contest.

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

                  Is DSU that unusual for COCI?

                  DSU was my second idea (first was an obvious greedy, which, as I soon realized, was obviously wrong :D), but it seemed strange for a 3rd problem, so I tried to find some other way to solve it.

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

                  No, I mean, it is only a 100p problem on a high school contest, surely it should not require any advanced algorithm. ;D

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

                  True that. DSU is not really hard, but still.

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

            i think gen's DSU solution is very shorter than your binary search code.

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

        I believe that binary search is the tougher way to go, I tried to think of a binary search solution in the beginning but I couldn't find any, thumbs up for your idea I really liked it! I ended up coding a DSU solution and I don't even complete scanning the input when I get the answer :D :D

        http://ideone.com/ud4foP

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

    UTRKA for 100%:

    Let D(i, j, k) be maximum advantage out of all paths from i to j using at most k edges.

    If we know D(i, j, h) for some h and each i, j and we also know D(i, j, l) for some l and each i, j, we can compute D(i, j, h + l) in O(n3) time.

    At first we compute D(i, j, k) for k equal to powers of two and after that we construct binary representation of the optimal k digit by digit (starting with most significant digits).

    Total time complexity is

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

      After computing D for all powers of two, how do you search for the optimal k?

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

        Got full score in upsolving with this idea:

        1) Calculate D for all powers of 2.

        2) Calculate D for all powers of 2 decreased by 1 (lets call this array Prefix).

        3) Find the smallest i, that Prefix[i] contains negative cycle. Out current answer is 2a - 1, where a == i+1

        4) Lets try not to use some particular bit in our current answer (from the most valuable to less valuable). For this we will keep track of our current suffix. Suppose we are looking for i-th bit. We need to join our current suffix and Prefix[i-1]. If the result of join contains negative cycle — we do not use i-th bit, otherwise — we use it and update current suffix.

        My code is ugly, but maybe it will be helpful.

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

        In fact, I search for optimal k - 1 (that is, the maximum number such that there is no negative cycle using this number of edges, or less). What I do is binary search, where I keep D for actual lower bound. In the beginning my lower bound is 0 and upper bound is the smallest power of two U, such that there is a negative cycle with U (or less) edges. Therefore the size of interval where I search is power of two and it always will be (as it halves in each iteration).

        The number W in the middle of my interval is lower bound + some power of two, so I can compute D for W in O(n3) using Ds for lower bound and for that power of two. If there is a negative cycle using at most W edges, we can set upper bound to W. Otherwise we can set lower bound to W. We have already computed D for W, so we still know D for our lower bound.

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

i think the problem Utrka was very similar to 147B - Smile House

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

    Yeah, it is. Just the time limit is larger. But that one seems quite difficult, too — less than 200 successful solutions.

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

      i don't solve this problem because i read the problem after the end of contest. :(

      in the next contest i will do what Sereja always recommend (reading ALL the problems)

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

Can anyone explain the solution of task "cokolade" ? My solution is sqrt(10^8) * 100, I simply consider all the divisors of the numbers, but this seems incorrect!

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

I'm not allowed to log in from my location. Is there any other way I might participate?

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

    I guess you are trying to log into "HONI 2013./2014. — 4.kolo". Try logging into "COCI 2013./2014. — Round #4".

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

i m asking this question to who used this idea(described below) while binary search. I and Fcdkbear could not come up with answer. Here is question :
Why dist[i][i] with using exactly M edges have to be less then using exactly M — 1 edges. I'm talking abouth coci last problem.

Could you please look that example :

if we have 4 nodes and this edges between them :

1 to 2 with -1 weight

2 to 3 with -1 weight

3 to 1 with -1 weight

2 to 4 with 1000 weight

4 to 3 with 1000 weight

when M = 3 dist[1][1] = -3 and when M = 4 dist[1][1] = 1998