csacademy's blog

Round #20 (Div. 2) + Platform Redesign
By csacademy, 8 years ago, In English

Hello, Codeforces!

We are happy to announce that we're going to host a new contest at csacademy.com. Round #20 will take place on Tuesday, March/07/2017 16:00 (UTC). This round will be a Div. 2, meaning that the rating change will only affect users with a rating below 1600. Unrated users will also be affected. High rated coders can participate unofficially.

If you want to take part in this round you need to register before the contest begins. As this is a Div. 2, it will consist of 5 tasks of more accessible difficulty.

Contest format:

  • You will have to solve 5 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.

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.

Platform redesign

We have given the site an entire new look. The new navigation sidebar can be found by clicking in the upper left corner of the page, while the global chat and latest forum posts are easily accessible from the upper right corner. We also changed the front page and the blog. We hope you're going to like the new look.

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

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

Nice New Design!

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

Really nice design, but get back the logo! :)

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

Just a reminder, the contest starts in 2 hours.

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

How to solve second problem?

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

    Maintain BIT/seg tree as you iterate the array from left to right . When you are at index j , you want to find minimum i such that arr[i] < arr[j] and just update the maximum answer .

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

      How to solve with binary search?

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

        No need for any data structure even though it's very easy if you use one but kind of too much for B.

        It can be solved by preprocessing using a simple DP in O(N).

        Let DP[x] represent maximum index i such that v[i] >= x.

        Initially DP[v[i] = i, and transitions are looping from n — 1 to 1, and updating DP[i] with max(DP[i],DP[i+1]). You can see why transitions are valid if you trace it on small sample.

        Now for iterate over all v[i]'s, and take maximum of DP[v[i]] — i.

        Here's my code : http://ideone.com/7dgRoE

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

        Binary search method —

        maintain a stack, initially with just first element. iterate from index 1 to n-1

        if the new element is lesser than top of stack element -> push to stack. note that the stack contains elements in strictly decreasing order.

        else if the new element a[i] is greater than top of stack element -> apply binary search on the stack to find lowest index element smaller than a[i]. Maintain this maximum value.

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

        You can solve it by using sets.
        Initially maintain a vector<pair<int,int>> which holds the value and its index. Insert all the indexes into a set.
        Sort the vector according to the value in increasing order.
        Now,we iterate through the vector.
        In each step, we erase the index corresponding to that element in the set.
        Then find maximum index in set and subtract it with current index. Let this value be z.
        Then ans=max(ans,z).
        Code

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

    Store the permutation in a array of pairs {value , index}

    Sort the pair

    Now starting from val = 1 to n you just need to find the maximum index greater than index of current value in range from (val + 1 ) to n which can be done using max suffix array.

    See the code for implementation details : Code

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

    Thank you all. I like csacademy problems. Problem are short and hard problems

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

How to solve C?

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

    You can binary search on the answer. For validating the "mid", you can upgrade cities greedily. Iterate in increasing order of coordinates of cities. When you encounter a city whose max distance to an already upgraded city to its left exceeds the "mid", you need to upgrade another city to the current one's right. This can be chosen greedily, i.e. the farthest city to the right of the current one whose distance from it is <= "mid".

    Code

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

      Thanks for the Solution! Binary search is so versatile. I feel stupid for not being able to solve it during the contest.

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

    Here's how I solved it after the contest. We can see that the if our best distance is let's say D then obviously we can also upgrade the cities in such a way that the maximum distance between regular and upgraded city will be  ≥ D which means it will be monotonic and we can apply binary search on D. We sort the xi's first. Now to check if a particular D is valid, we can greedly start from first city and upgrade the city at distance D (We choose the last city with distance atmost D because it minimizes the number of upgraded cities). Now we start from this upgraded city and keep ignoring the cities to right which have distance  ≤ D. Now we can easily count the number of upgraded cities and compare it with K, and change our binary search limits accordingly.

    → Reply