Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

_kun_'s blog

By _kun_, history, 4 months 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 senek_k.

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

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  

»
4 months 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) ??

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no way

    • »
      »
      »
      4 months 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.com/contest/458/submission/7416845

      • »
        »
        »
        »
        4 months 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)

        • »
          »
          »
          »
          »
          4 months 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

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

            oh i misread, sorry

            • »
              »
              »
              »
              »
              »
              »
              4 months 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 ?

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                i don't know any solution on high costs(

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months 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 :(

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months 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.com/contest/458/submission/41572445

  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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 ?

  • »
    »
    4 months 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.com/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...)

»
4 months ago, # |
  Vote: I like it +31 Vote: I do not like it

What a beautiful task div.2 E was.

Amazing!!!!

»
4 months 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 ?

»
4 months 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
  • »
    »
    4 months 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

    • »
      »
      »
      4 months 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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        no i mean can you add comments in your code

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Done, if you have any doubt ask me via Talks, I response to you

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

    Looking at it again and again, i finally understand.

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

A trivial doubt, if the constraints allowed, just printing the vertices which don't have an edge between them would have sufficed for Div 2 (E)?

»
4 months 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.

  • »
    »
    4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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).

      • »
        »
        »
        »
        4 months 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.

      • »
        »
        »
        »
        4 months 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.

    • »
      »
      »
      4 months 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).

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

    The graph is a DAG. So why wouldn't topological sort work? I mean, we first sort it topologically and then add the first node if it's not visited and start BFS from that node. We only add alternate nodes to our answer set. Shouldn't this work? eds467

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nevermind, it's not a DAG. I misread the question. It's graph without self-loops, not without cycles:)

»
4 months 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.

  • »
    »
    4 months 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.

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

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

      • »
        »
        »
        »
        4 months 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?

        • »
          »
          »
          »
          »
          4 months 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!

          • »
            »
            »
            »
            »
            »
            4 months 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.

            • »
              »
              »
              »
              »
              »
              »
              4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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);
      }
      
»
4 months 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?

»
4 months 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 ?

  • »
    »
    4 months 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.

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

What's the full form SIS in SIS Olympiad?

»
4 months 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

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Can someone please help me with div 2 problem E (Sergey's problem) I didnt understand the solution I got the induction proof but I didnt get the implementation.

»
4 months 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.com/contest/1020/submission/41604370 (it is a mess, but I will try to upload a better, cleaner one soon :) )

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

Please add source codes

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

Wait, does 1019E utilize convex hull trick, or just convex hull?