cdkrot's blog

By cdkrot, history, 6 years ago, In English

Thank your for participation!

Problem D2A (New Building) was authored and prepared by Burunduk2.

Problem D2B (Badge) was authored and prepared by me, the version in SIS's olympiad contained the version with n ≤ 105.

Problem D1A (Elections), D1B (Hat), D1D (Large Triangle) were authored by achulkov2, with D1A prepared by Schemtschik, D1B by achulkov2 and D1D prepared by achulkov2 and craborac.

Problem D1C (Sergey's Problem) was authored and prepared by Morokei.

Problem D1E (Raining Season) was authored and prepared by izban.

Editorials were written by izban and VArtem

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +89
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

problem elections can be solved using ternary search, how ??

i already solved it in O(n2) how to solve it in nlog(n) ??

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

    no way

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

      this is one of the solution for same problem but in another contest http://codeforces.me/contest/458/submission/7416845

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

        This problem isn't the same. that problem is like problem from round 503 with m = 2, but with m up to 3000 there are no such solution (i think)

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

          what m = 2, look read both problems carefully they match!!! in old elections problem number of parties and voters are much bigger but with less constraints on cost

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

            oh i misread, sorry

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

              i understand a solution using fenwick tree but based on low constraints on cost. but i can't understand any solution on a high cost like 1e9. please if you know can you explain it ?

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

                i don't know any solution on high costs(

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

                could you tell me how i can solve it in O(nlgn) with fenwick tree?i am weak in data structure :(

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

                  you use two fenwick arrays,

                  fen1[i] is how many voters exist with cost  ≤ i.

                  fen2[i] is what is the total cost of all the voters that have cost  ≤ i.

                  now as editorial said, iterate through all K from n to 1, select every party that has voters  ≥ K and add them to your party and make the following

                  fen1[cost[i]] -  = 1;
                  fen2[cost[i]] -  = cost[i];

                  now if you still have less than K just make binary search on fen1 to find needed voters with least cost

                  look and trace my submission http://codeforces.me/contest/458/submission/41572445

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

                  Harolinch, your solution won't work in this problem as the cost can be upto $$$10^9$$$, and you can't make an array that long.

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

                  yes, sure, this solution works for the exact same problem with different constraints..

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

    For Div2 C, one can also see this editorial also(round 2(c)). nlog(n) solution is described there. link to editorial

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

      i don't understand the editorial, if you understand it, can you please make it clear here ?

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

    It can be solved in by priority queue.

    The main idea is to enumerate the vote of party 1 as k, then all voters whose ci's rank in party pi is not less than k should be selected, and then select some minimum ci until voters are selected. Increasing k and use a priority queue to maintain the latter part.

    https://codeforces.me/contest/1019/submission/41524142

    (In the contest I came up with a wrong solution and found it wrong while testing samples, then I deleted the whole code and wrote O(n2) solution, after debugging I cost 28min to pass A...)

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

      thanks so much, this was so helpful for me

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

      consecutivelimit, I don't understand your code. I understand what's happening (somewhat) in your code, but I don't understand the "why". Especially the second for loop, which has intertwined relationships between i, tot and pos. Both pos and tot depend upon i, which I think represents the number of unprocessed non "our party" voters (not sure if correct). So

      Can you explain the working of the second for loop?

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

What a beautiful task div.2 E was.

Amazing!!!!

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

I don't understand the logic begind "A. Elections". Could someone explain it to me please ?

»
6 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

By the way I solved the B problem in O(N) time, the solution I use was:

If a node belong to a cycle his end in himself. If a node does not belong to a cycle ends in the first cycle node his traverse visit.

So I did something like Topological Sort and DSU to get the answer in O(N).

My code solution for Div2 B.

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

    hey can you please comment out your code that would be very helpful

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

      mangat my code is commented, under the code spoiler. For space safe reasons.

      You only have to click in the Code part. Thanks

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

        no i mean can you add comments in your code

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

    your res() function may run in linear time in worst case...so overall complexity may be quadratic in some case but I can't think of a test case right now... can you provide the proof that:-

    Your code here...
     //and finally the funny part print your solution
            for(int i = 1; i<=n; ++i)
    		cout << res(i) << ' ';
    
    this above part of your code run in linear? if yes. how??
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is linear cause res func ask if calculation on I is done if is it he answer in O(1) now with that and dsu you can prove that you won't visit a node twice so overall O(n)

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

Div.1 C is really a good problem.

In the contest, I thought about some greedy algorithms but they failed on my stress test, then I thought about solution on DAG, on SCC, or inserting the vertices one by one, but no one works.

After the contest more than 50 people passed C except me, however, most of people who passed C FST, at last only 7 people passed, so I didn't lose my rating accidentally.

Some contestants in National Training Team discussed about this problem, but no one found the right solution. Even fateice, fjzzq2002, yjq_naiive didn't pass C either.

It's very amazing that such a hard problem can be solved by a simple algorithm, with about 20 lines' program.

I like this type of problems, which is hard to think and easy to implement. I'm curious about how problem C is created.

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

    I have tried to solve this problem by 2-sat for a long time during the contest. But I finally found 2-sat is wrong after the contest.

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it -25 Vote: I do not like it

    No! I think C is bad. It is an implementation version of a graph theorem. Even very high rating users can't come up with during contest. Especially, in the IOI style, it should never appear.

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

      It just means it's a hard problem... I think it could be a fine D or E, it's not like people have seen the theorem (or else they would have solved it).

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

        I'm uncomfortable when can't solve a problem, then it turns out to be a theorem.

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

        I think it is hard or not depend on where it place. In programming, people will try some ways like SSC, greedy, ... While in mathematics, induction is straightforward then it maybe easier.

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

      In IOI there are many hard problems which can be solved by a short code, for example, IOI2017 D1T3 (Toy Train), IOI2014 D2T2 (Friends).

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

Regarding E: This might be a bit pedantic, but I'm surprised no one seems to have mentioned it. When you add 105 points with coordinates (105, 109), the sum looks like (1010, 1014). If you then multiply the two coordinates, you get 1024, which overflows a long long. So a solution that computes convex hulls by checking something like ll(a)*d - ll(c)*b > 0 will behave unpredictably on some test cases.

In particular, this generator seems to hack Radewoosh's solution.

code

(It's a tree with only 3 leaves and vertex 1 in the middle. The distances are chosen to be large enough to result in overflow, and such that at t ≈ 104, the node which is actually furthest from 1 might be missed, since it is between to other nodes on the convex hull of distances.)

To fix this, you could either use higher precision arithmetic when calculating a*d and c*b, or you could use long longs to compute the continued fraction expansions of a/b and c/d, and then compare the expansions.

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

    Yes, I thought that I need numbers up to A·B·n (that's why I have unsigned long longs in one place in code), but I need numbers up to A·B·n2. Good that codeforces is modern programing site and have int128.

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

      Oh, wait... Nevermind, at least rand() generates numbers up to 231.

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

        Hmmm, maybe just there isn't a penalty for WA on sample other that the first one?

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

          I'm not sure what you mean. I think the reason that you got AC is that for overflow to occur, there needs to be a very long path in the tree, and even then, you might well get the right answer by chance anyway. I would guess that the test data wasn't generated with overflow in mind, and that the constraints should really have been a bit lower, so that we wouldn't have to worry about overflow.

          Anyway, good job on solving this problem so quickly!

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

            I was joking with second and third commend, but the first one was about the fact, that I wasn't able to use int128, because codeforces doesn't support them.

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

              I was like wtf! since when does codeforces support int128 it wasn't available the last time I checked.

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

    So I wrote an "int96" to deal with multiplication. I want to know if there is a more convienient way to deal with it.

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

      I have a trick, can one verify that:

      int cmp(long long a, long long b, long long c, long long d) {
          long double dif = (long double) a * b - (long double) c * d;
          if (abs(dif) > 1e18) return sign(dif);
          return sign(a * b - c * d);
      }
      
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In large triangle can someone explain what they mean by radius vector of third point?

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

Could anyone write the optimized solution O(n) of problem B div 2 ?

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

    Construct the graph, it will be some amount of cycles and trees that grow from some vertex of cycle. If the vertex is on the cycle , then anser for this vertex is this vertex. If the vertex isn't on the cycle, the answer for it is the nearest vertex on the cycle, it can be precalculated in O(n) time.

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

What's the full form SIS in SIS Olympiad?

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

can anyone help with explanation of div 2 c for easily understanding, got stuck in this problem for 3 days

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

Another solutions for div2 C:

Set Up:

First, let me describe the set up. We create a 2D array where we store the voters' costs of each party in descending order (big to small) (partyVoters) and a single array where we store pairs of a voter's cost and the party they support and we sort it based on costs in ascending order (small to big) (moneySorted).

Task:

We need to get more voters (not equal!) than any other party. Let's say there are three parties with the following composition:

  • 1 -> 0 voters
  • 2 -> 3 voters
  • 3 -> 5 voters

In our case we need to get more voters that parties 2 and 3. Please note that when we buy a voter from another party, the number of voters of that party decreases, while ours increases (always by one). So, if we buy 4 votes from the 3rd, we have the following:

  • 1 -> 4 voters
  • 2 -> 3 voters
  • 3 -> 1 voter (that means we won!)

Solution:

I solved the problem using a greedy algorithm. First of all, I created the arrays that I describe on the Set Up section as well the following variables: - curr -> it stores our current number of voters and - target -> it stores the number of votes we need to get in order to win the elections (note that this — variable stores the number of voters of the largest party(s) )

After that, I created a while loop. On each iteration, after we check if we ensure that we have not reached the target yet (if we have, we just show the result!), we find all the parties (let's call their amount numParties) that have the most voters (equal to target) and we store their indexes. Now it comes the greedy part. We always have 2 optimal choices: 1. Either we can buy the cheapest voter from those parties. (and the target will be decreased by one and our votes are increased by numParties) 2. Or we can get numParties + 1 voters (note that from above that the fact that the target is -1 is equivalent of getting one more voter).

So, we calculate the costs of both of the two cases the we choose the cheapest one. If the optimal choice is 1, we get rid of the last element from the 2D array for each party). On the other hand, if optimal is 2, we get rid of only the cheapest voter among all of them, as there is a possibility that on the next iteration the other option to be the optimal one and therefore we don't want to buy all of them now! :)

And we repeat until the curr reaches the target! :)

Solution:

http://codeforces.me/contest/1020/submission/41604370 (it is a mess, but I will try to upload a better, cleaner one soon :) )

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

Doing random old contests, I happened to find another very different solution for Div1 C.

First, if the graph was a DAG, then we could solve the problem using a topological sort. Actually, we can guarantee that each vertex is either in the chosen set or can be reached in one edge (this is important). Just sort the vertices topologically, and for each v we test if any vertex u that has an edge (u, v) has been included. If so, we don't do anything; otherwise, we add v to the set.

However, the original graph is not a DAG. But it can be made one if we remove edges that form cycles. We run a DFS and for each back-edge, we remove that edge from the graph G and put it in another graph G2.

Now, we solve the problem for our new DAG G using toposort. The problem is that we might have chosen vertices that are adjacent in G2, since we ignored those edges. The key observation here is that G2 is also a DAG. To see why, consider the DFS tree which we used to construct G2. The edges we picked only go up in the tree, so they cannot form a cycle. Thus, we can also solve the problem separately for G2, only caring for the vertices that conflict in G (both have been chosen but they have a direct edge in G2). For both separate solutions, we have a set in each graph that allows us to go to every vertex in at most one edge. If we get only the vertices that have been chosen in G and, among the conflicts, only the vertices that have been chosen in G2 as well, by transitivity we get a solution for that reaches every vertex in at most 2 steps.

Code

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

O(N) solution for problem B div 2 (1020B - Badge) for those interested:

code
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please define where my mistake is in problem B in O(N) Solution

Here's my submission: 221630255