csacademy's blog

Round #82 (Div. 1 + Div. 2) with prizes
By csacademy, history, 7 years ago, In English

Hello, Codeforces!

We're glad to have Xahandd as a problem setter!

We're going to host a new contest at csacademy.com. Round #82 will take place on Wednesday, June 20th, 15:05:00 UTC. This contest will be a Div1 + Div2, with 7 tasks of varying difficulty that need to be solved in 2 hours.

Facebook event

We recently created a new Facebook event. If you choose "Interested" here, you will be notified before each round we organise from now on.

Contest format:

  • You will have to solve 7 tasks in 2 hours.
  • There will be full feedback throughout the entire contest.
  • Tasks will not have partial scoring, so you need to pass all test cases for a solution to count (ACM-ICPC-style).
  • Tasks will have dynamic scores. According to the number of users that solve a problem the score will vary between 100 and 1000.
  • Besides the score, each user will also get a penalty that is going to be used as a tie breaker.

Prizes

We're going to award the following prizes:

  1. First place: 100$
  2. Second place: 50$

About the penalty system:

  • Computed using the following formula: the minute of the last accepted solution + the penalty for each solved task. The penalty for a solved task is equal to log2 (no_of_submissions) * 5.
  • Solutions that don't compile or don't pass the example test cases are ignored.
  • Once you solve a task you can still resubmit. All the following solutions will be ignored for both the score and the penalty.

If you find any bugs please email us at [email protected]

Don't forget to like us on Facebook, VK and follow us on Twitter.

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

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

The contest starts in 10 minutes!

→ Reply
»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

On E, wqs binary search (popularly called alien trick) with some heuristic kind of thing (may be something meaningful) gave AC. is it just that tests are weak. Or can wqs binary search be applied here. If so Can someone give proper proof of how all the k can be achieved in binary search.Or what can be done if in binary search there is threshold such that k suddenly changes from say 4 to 7 (and our anticipated value is 5 say). So now how do we manage to reach the required k(does convexity or anything guarantee that everything will be reached). I seem to have a strong intuition that here all k cannot reached ,hence I had to add heuristic.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I've passed without any heuristics, and I thought it's expected solution during the contest. But only with intuition :)

    And it would be very strange if there have been the problem with weak tests, because this idea is the first idea came into my brain.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it +5 Vote: I do not like it

    If k suddenly changes from say 4 to 7, then we have 3 edges with weights equal to other edges weights. But we can add random EPS to their weights, and, obviously, the answer (total weight of min-span-tree) will not change significantly, but at the same time, we will no longer have a jump. That means, that if our limit is 5, we can take any 1 of that 3 edges into the optimal answer.

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

      Nice. So if I get it correctly.We can intially add some random different eps for each fountain edge. Then we binary search (this binary search must be based on doubles I guess not integers).

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        Ok, it seems to be true and can be implemented even in integers. No need to add random EPS, just take any edges that fit into the limit. https://csacademy.com/submission/1628391/

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

          My solution was somewhat similar. But I also did that stopping at k thing even as part of binary search so that we get even some information in that case(isn't it a heuristic kind of ).Also don't you think your solution is heavily depending on order of sort of the edges?

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

            I know it's not, but you may try to find counterexample, if you want :)

            → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    First lets notice that for fixed value of C you have two polar options: to use C - eps, considering all fountain edges first, and to use C + eps, considering all fountain edges last. In first case you will take highest number of fountain edges, in second case you will take lowest number of fountain edges.

    Now if we are working with C + eps, order of edges doesn't change if we'll work with C + 1 - eps, so min_taken(C) = max_taken(C + 1), therefore there are no "gaps" in between.

    What we want to check now is that we can actually construct ordering for which you will take some intermediate value between min_taken and max_taken, for any intermediate value.

    Let's take C - eps ordering; let's start changing used C - eps edges into C + eps edges. You can see that after every change number of fountain edges that you are going to take is either the same or it decreases by one (you can derive it by looking at number of components in a graph at C - eps and C cutoffs). This process has no jumps, and goes from max_taken to min_taken, therefore covering all intermediate values.

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

    This is a known problem, which is already discussed here: https://codeforces.net/blog/entry/51201?#comment-354630

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

    What is alien trick ?

    → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Any hint for Problem C, "City Break" ?

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

    Let's say for a current node,I go to nearest possible node.It could be clockwise or anticlockwise.If I move clockwise,update the minimum possible distance to the next node in anticlockwise direction and also it's nearest unvisited node in anticlockwise direction to the next node and if I move anticlockwise,update the min. possible distance of the next node in clockwise direction and also it's nearest unvisited node in clockwise direction.

    This may help:https://csacademy.com/submission/1623337/

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

    Just maintain a set that corresponds to the cities that are NOT visited yet..

    then just binary search .. you can either go in the forward direction (or clockwise) or backward direction (anticlockwise)

    Once you are done with the current city , delete it from the set...

    You can see my code --> (its ugly though) Code

    (( Note that I added 2 values in set , i and i+n .. that is because I wanted to convert the circle into a straight line ))

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

    My solution:

    First of all, run dfs from node s. When you've node u in your dfs, there will always be at most 2 unvisited neighbours of u. Lets call them v1, v2 and their distances to u w1, w2. Add edge v1 < — > v2 with weight w1 + w2 to the graph. Get one which have minimum distance to u, add its distance to the answer and run dfs from it, before running dfs. Print the ans.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When do we get editorials?I'm quite new to csacademy.

→ Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Any idea on D? (And why D on CSAcademy always make me become a fool?)

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

    The max value in B is the maximum value of number of distinct integers among all contiguous windows of size K in A. Let this value be x. Now when you're building the array, initially you have x elements to choose from. Increment/decrement the count of free elements to choose from, and multiply the answer accordingly.

    https://csacademy.com/code/xzoWtiby/ (logN factor can be removed)

    → Reply