csacademy's blog

Round #28 (Div. 2) + Special Prizes
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 #28 will take place on Wednesday, May/10/2017 13:00 (UTC). This round will be a Div. 2, meaning that the rating change will only affect users with a rating below 1650. 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.

Special prizes

This round will have 3 special prizes consisting of private coaching lessons with our contest coordinator, wefgef. Each lesson will be conducted on Skype and will last for 1 hour and 30 minutes. The topics approached during the lesson will be the choice of the winners. The prizes will be distributed as follows:

  • 1 random prize for the top 20%
  • 1 random prize for the next 30%
  • 1 random prize for the bottom 50%

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 changes

  • CS Academy is now a single page application.
  • New activity section below the global chat
  • Division cutoff changed to 1650

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

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

Comments Comments (13)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a reminder, the round starts in 4 hours.

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

    round is showing as already finished on clist.by.

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

The website is down for me at the moment

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

Can't even run example on the website and then got stucked :(

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

Its up again.

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

How to solve D using Binary Search? I couldn't find a way to check if a particular difference is valid or not?

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

    The way my official solution works is the following:

    Binary search the level of the water you want to reach. Let's call it L. For each bottle, if L is in interval [min, max], the level is L. If L > mx, the level is mx, else it is mn. This way you can compute the how much water do you need for a set L. If you increase L, the water will increase, but probably not by how much you want it to increase.

    After you found a valid water level, fill the bottles using the above rules and compute the mx — mn water level for each bottle. Watch out for the case where for a level, you still have some water left. You need to redistribute it. This is not a real concern in most of the testcases, but watch out for this one.

    2 11
1 20
1 20

    The answer should be 1 The way is to put the water [5, 6]. You can't put [5.5, 5.5].

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

    My solution used 2 binary searches. The first binary search found Max_level where Max_level is the least number such that if all water levels are bounded above by Max_level, the total sum of water levels is greater or equal to L.

    The second binary search found Min_level where Min_level is the greatest number such that if all water levels are bounded below by Min_level, the total sum of water levels is less than or equal to L.

    The final answer is Max_level-Min_level

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

      Can you put some more light on these conditions :

      • if all water levels are bounded above by Max_level, the total sum of water levels is greater or equal to L

      • if all water levels are bounded below by Min_level, the total sum of water levels is less than or equal to L.

      I am unable to understand these two conditions :(

      Thanks!!

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

        The first condition says that I am allowing at the maximum, Max_level liters of Water in any bottle. Basically I am filling bottle number 'i' with water level = min(maximum[i],Max_level). Then I check if this distribution of water levels makes the total sum of water levels >= L. If it does,then I can always remove few liters of water from some bottles to get the final sum to be L. Since I pick the least such number as Max_level, I guarantee that the chosen value of Max_level is definitely the maximum attained value in the optimum distribution. (Because if it were not, I could have reduced Max_level even further).

        The argument for the second condition is exactly symmetric to this and finds the minimum attained value in the optimum distribution.

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

Can someone explain the problem statement for the last problem.Unable to understand what the problem is asking.

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

UPD: Got it. I had to enter the new bottles to fill set after(and not before) checking for the current bottles in fillset.
Hello,
I have doubt in Water Bottles problem.
I have implemented the solution in Archive section.
The same solution can be seen on CSA site with Job ID: 212983 Click
I have received WA on TC 7, 12.
I do not know what's wrong in my code. Can someone help?
I also do not know how to provide a link for your submission on CS Academy. If anyone knows that too, please tell.

→ Reply