danilka.pro's blog

By danilka.pro, history, 8 years ago, translation, In English

Hello, Codeforces!

Today, 17th of October at 17:35 MSK Codeforces Round #377 for second division participants will take place. As usual, first division participants are able to participate out of rating.

The round problems are taken from the problemset of regional stage of the All-Russian school team programming olympiad which was taking place yesterday in Saratov. The problemset for onsite competition was invented and prepared by Mike MikeMirzayanov Mirzayanov, Ilya IlyaLos Los, Danil danilka.pro Sagunov, Vladimir vovuh Petrov and Roman Roms Glazov. We are thankful for pre-solving competition problems to many of Saratov State U teams' participants. One problem in the round will have a bit harder version than at the competition.

Nikolay KAN Kalinin and Tatyana Tatiana_S Semenova helped us preparing problems and translating for the round — thank you! Thanks to Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

There will be 6 problems and 2 and a half hours to solve them at the round. We wish you the best luck!

If you are a participant of the yesterday competition in Saratov, please, do not register for the round and do not participate in it, also do not discuss the problems before the round ends.

UPD Scoring: 500-1000-1500-2000-2000-2500

UPD2

Congratulations to the winners!

Div.2

  1. gxgod

  2. FizzyDavicl

  3. dothanhlam97

  4. ngkan

  5. Judy.Hopps

Div.1

  1. dreamoon_love_AA

  2. kmjp

  3. NVAL

  4. eddy1021

  5. pekempey

As soon as the time of registration to the round was a bit early, there may be some first division participants taking part in a line with a second division participants. There are not many of them, so (and due to technical problems) this will be left as is.

Due to NEERC subregionals in Saratov, rating will be updated tomorrow.

UPD3 Editorial

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

| Write comment?
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

A fibonacci number Round... 377 is 14th fibonacci number.

»
8 years ago, # |
  Vote: I like it +67 Vote: I do not like it

In the registrants list I see a few Div. 1 participants that are registered officially (there is no "*" before their handle).

Here's an example.

»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Today I will leave grey for good. ..... Or not XD

»
8 years ago, # |
  Vote: I like it -49 Vote: I do not like it

Please shift the contest timing by 10-15 minutes..

»
8 years ago, # |
  Vote: I like it -22 Vote: I do not like it

3 Rated contest in 3 days (Round 375,376 and 377 ) and (15,16,17).

375-15

376-16

377-17.

it's a record of codeforces 3days in a row reated contest and also interesting 5-5,6-6,7-7;

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

The Graduation Year field in the application form only accepts numbers under 2010.

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

    Fixed, thanks!

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

      The platform doesn't allow me select my country. Please resolve this issue. Thanks.

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

        Nigeria existed, why do you want to create a new Nigeria?

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

          After updating my country to Nigeria (in settings > social) and clicked "Save changes", that's the dialog that appears. If Nigeria already existed, then why pop out that dialog identifying Nigeria as a new country? Then since it is identified as a new country, I go ahead and fill in its 2-letter code and click "Save", then I get "Code is already in use". How does that tally? Hope you see my point.

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

            Change your country to "Нигерия"(copy this, its Nigeria in russian). It will help

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

      Why there is not rating update for Techno cup round for some Div 2 users who registered late?

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

One problem in the round will have a bit harder version than at the competition.

There will be 6 problems

*Grabs popcorn and get ready for a hell level Div2F.

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

    It's not necessary problems to be from A to F, it could be dobule D (as it was before (D1), (D2)) or any other problem can be doubled

»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Pay attention, Problems may be not sorted by difficulty.

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

Let is delay 10 minute as usual :)

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

Its showing i'm an official participant in this contest !
i had registered yesterday when i was still blue :p
Bug in CF ?

»
8 years ago, # |
  Vote: I like it +30 Vote: I do not like it

he could have had a breakfast and a supper, but a dinner, or, probably

what??

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

    Here the "but" refers negative.

    Such as: I will go anywhere but there.

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

    Not an old issue, but there should be more efforts on translating into English statements.

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

Round is very nice !

I only didn't realized that in second task case n=1 answer is always 0 :( Actually I thought it is special case and add one extra if :D You could put n>=2, that wasn't very clear.

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

    Same with me , got hacked , lost around 400 points -_-

    Anyway problem set were good this time

»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

RIP all C submissions with initialization of ans < 2e18, and then taking minimum.

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

    How do you solve C?

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

      Code
      Let M = max(b, d, s)
      If M = 1, answer would be 0.
      Now I considered all 9 cases, whether he enters before B, before L, before S and leaves after B, after L, after S. For each case, find what should the exact number of meals should be, and subtract the current value of (b, d, s) and take minimum.

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

        Not sure if my code is correct, but i take max(b,d,s) — 1, which is the number of days of maximum full 3 meals. From there just minus the rest if the number of meals is smaller than that

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

      Number of days is max(a, b, c), so you can calculate answer easily.

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

      take input in an arry and sort it.

      make 3 cases : 1. when all are equal 2. when only last 2 elements are equal 3. else and proceed. happy coding. :)

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

      This passed pretests. Not sure if it'll pass the full tests. http://ideone.com/EgztAG

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

      If there are numbers b , d , s

      then if mx = max(b , max(d,s));

      then, answer = max(0 , mx-1-b) + max(0 , mx-1-d) + max(0, mx-1-d) :)

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

    I initialized ans=-1 :'(

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

In B, what is the answer for the following testcase?

n=1, k=5 and a[1]=1

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

    should be zero as it was mentioned arr[0] and arr[n + 1] = K

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

      Missed that part. :(

      I will get a wa for handling the case n=1 separately.

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

    Almost all Hacks for B is n=1 ! :) The answer should be 0...

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

For task C, why is 3 1 2 = 1?

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

    the extra breakfast is from the last day. you have 2 days of full 3 meals, and 1 day with only breakfast

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

      But if you have 2 days of three full meals, won't you miss dinner twice?

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

        For 3 1 2 Come before breakfast today and go after breakfast on 3rd day(day after tomorrow ) ,In this way only one lunch is missed.

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

        so it looks like this day 1 : b d s day 2 : b d s day 3 : b

        sum up 3b 2d 2s, so you miss dinner once

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

Hack case for C ?

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

can someone help me understanding the output of 4th sample case of problem C ?

input

1000000000000000000 0 1000000000000000000

output

999999999999999999

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

    You can go into the sanitorium just before the supper and leave just after breakfast.. This case is similar for cases like N M N where N > M.

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

      okay.. I guess I was moving in the wrong direction I guess.

      thanks for the explanation.

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

Approach for problem E?

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

    I am pretty sure greedily finding matches for the next smallest adapter works. Keep computers in a set/dictionary that you can do O(1) lookup on, and remove them when an adapter matches with them.

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

    My solution goes as follows:

    Sort all the computers and sockets. Then, find all the pairs where socket power is the same as computer power. Because of the sorting, this can be done in O(n+m) time with two indices. (By moving an index forward when its power is smaller than the other's, and skipping if the socket/computer is already in use). Then I add adapters to all of the sockets and repeat, finding all the matches. You only need to do this around 31 times until all socket powers will become 1.

    My code was the 5th fastest overall.

    Edit: An identical solution is proposed in the editorial.

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

      Can you prove this greedy solution please?

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

        Sure, I'll try.

        Because one socket can only be used once, and a computer only requires one socket, there is no situation where we shouldn't join a socket and a computer if we can.

        The task description also defines that we should use as few adapters as possible. This is accomplished by checking smaller amounts of adapters (starting with 0) before trying more. It is always better to connect a socket to a computer earlier, when there are fewer adapters, than later. So a socket with a smaller power will be connected to a computer before trying a socket with more power and therefore more adapters in between.

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

          Thanks a lot, I don't know why I found that hard to prove that during the contest (Maybe due to pressure).

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

How to solve C ?

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

    let n=max(a,b,c)

    now depending on his arrival and leave time, there can be seven possiblities for number of breakfast, dinner and supper available. they are:

    b=n,d=n,s=n b=n,d=n,s=n-1 b=n,d=n-1,s=n b=n-1,d=n,s=n b=n,d=n-1,s=n-1 b=n-1,d=n,s=n-1 b=n-1,d=n-1,s=n

    for each of these cases , find the minimum number of foods he can miss

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

    Number of days in sanatorium = max(a, b, c).

    Then you have 3 case: 1. max = a, it means that you came in morning, also it means that you leave morning (you miss dinner and supper in last day because it's optimal)

    Then easy to calculate answer = max(0, (a — b) + (a — c) — 2)

    The same logick for other case.

    Sorry for poor english.

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

    Suppose the given values are a[0], a[1], a[2]. Sort a and subtract a[0] from all the elements. Now the answer is

    This is because any triple b, d, s where difference of any pair is at most 1, is valid.

»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

I tried F using Bridge Tree + Euler Tour got MLE
I saw people getting AC using the same ! can someone help ? here's the link to my code
http://codeforces.net/contest/732/submission/21541116

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

Problems difficulty is perfect.

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

What's the idea for solving F ?

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

    if u remove all the bridge edges, u'll get different connected forests. Choose the forest with maximum number of nodes as the center and direct all other forests towards this since there is only one way to orient the bridge edges. So choosing the largest forest will maximiize the minimum sum required.
    Then Do a euler tour to give the orientation by adding edges between nodes that have odd degree. Nodes having odd degree are always even.
    similar concept was use here : http://codeforces.net/contest/723/problem/E
    The overall complexity is of the order O(n+m).

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

    My idea on F.

    We can see that it is optimal to let every biconnected component to form a directed cycle as this won't affect it's potential on other biconnected component. So we should always try to form a cycle for every biconnected component first.

    Then we contract all biconnected component and this would form a tree. Now we can do binary search for answer.

    Every cities's ri will have at least x. As every node in tree represent a biconnected component in the graph, ri will initially be no. of cities in biconnected component i. Lets consider node u, if it's ru is more or equal to x, it should let the edge between u and its parent and direct it to u. So its parent's r value will be increased by ru. Else, the edge should direct its parent.

    Now dfs again and for every edge that are directed to its child, we can increase its r value.

    So if every ri is >= x, x can be obtained.

    edit :

    lol I failed system test because I read the problem wrongly and thought ri is the number that cities can go to city i. But the idea is still the same for the problem.

    ac code : http://codeforces.net/contest/732/submission/21563511

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

    Well I passed the system testing with a pretty simple solution. First of all we should notice that the answer of the problen is the maximum size of a bicconected component. Then to get how the edges will be directed, first you convert each bicconected component into a strongly connected one and you are left with the edges between the strongl/bi-connected components. It's simple to see that the compressed by strongly connected component s graph is a tree. So you make the component with the maximum size as a root of the tree. Then you make all edges between the components to go to their parents so that you can reach the root from each one of them. In this way you get alogN (N+M) solution.

    PS: I wrote an O(N+M)logN one because I used a map to easily access edges but this can be done in O(N+M) too.

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

    I am surprised that no one mentioned tarjan algorithm, I think that's the most straight forward way to solve it as you may have already a template coded.

    All you have to do is to find the minimum among the most compressed node in each connected component, and memorize them as roots. Initialize them as the root and reverse all the edges, there's your answer.

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

For E, why is a solution, that iterates through the number of adapters on all of the sockets at once, assigning greedily to each socket whenever a PC with the same power exists, wrong?

I can't find a bug in my code so I guess it's in my approach.

Code: http://codeforces.net/contest/732/submission/21541488

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

    When you sort pc[], you lose the ordering of the computers. There is no way to output the computers in the right order in line 3 of your output.

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

Can anyone explain how to do D? Was it dp?

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

    Binary search

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

    Binary search. It's easy to verify if the first x days works by choosing the last test day for each exam in those x days and seeing if there are enough days to study before them.

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

    Do a binary search over the number of days starting from day one to day X

    To ace M exams you need at least M days + the required days to prepare, i.e. lower bound L = M + sum of required times

    Now, to check if it's possible to do so in X days, start from the last day and do the following:

    tests = 0

    days_needed = 0

    if it's a day off OR we took the test already:

    decrement days_needed by one if they were > 0

    else:

    increment tests
    
    increment days_needed by the days you need to prepare for current subject

    After last (which is the actually the first) day, check if tests is equal to number of subjects AND days_needed == 0

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

    You can binary search the answer. To check if a particular number N of days works, we can assume we take every test at the latest possible opportunity (within the first N days). If not all the tests can be taken in that time, or we don't have time to study for all of them (and this is pretty easy to determine), then N is too small.

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

Have any bruteforce solution of D(without binary_search).

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

    Here's my bit complicated approach : Iterate on the exams, and maintain count of total free days available till now, which are not assigned.

    When an exam comes that has not been taken, if its required days are <= count, then mark this exam as done(for now), otherwise, we have two choices, either forcibly take this exam on this day by marking some of the previously done exams as false and adding (their preparation days + 1 exam taking day) to count , or just not assign this exam for now.

    We will try to do the first choice if its possible by cancelling some previous assigned exams first. And also take care that any exam that we are cancelling, its next occurrence exists and is before next occurrence of our current exam, otherwise we can just wait to assign current exam on its next occurrence.

    To get next smallest occurences of previously done exams, i have used a set. As we are cancelling exams, we remove them from the set. Also, when assigning an exam, insert its next occurence in the set.

    Code

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

      The same approach can be taken to linear complexity:

      In the binary search idea, we first guess the answer (the earliest day when we can pass). Similarly, in this approach, we guess the first day we can pass, except we guess sequentially.

      Suppose day D is the first day in which all subjects have appeared. Then to check if we can pass everything by day D, for each subject, we take note of its last exam date. (It can be proven that it does not hurt to take any exam late) For each day G (for guess), we check whether we can pass every exam we sit for up to that day. Specifically, the number of days required to pass every exam before a fixed day is the number of exams before the day + the number of days required to study for those exams. If we are able to pass every exam up to day D, then we output D. Otherwise, there is a certain earliest day, say D2, for which we are unable to pass every subject before that.

      The problem at D2 may be resolved if G increases: since we always sit for the latest possible exam, we might shift an earlier exam to after D2, hence solving the problem at D2. Specifically, for each exam we shift to after D2, we are reducing the number of days required at D2 by the number of days required to prepare for the exam + 1.

      Whenever D2 is no longer a problem, we can check in constant time whether D2+1 is problematic (if we maintain, for the current G, when the exam for each subject is). When D2 is G+1 (i.e. D2=G is not a problem), then it means we have found the smallest G in which we can pass all exams.

      Since every increment of G also takes constant time, this algorithm is linear.

      Submission no. 21537091. I think this is supposed to link: submission:21537091

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

    That's my solution:

    1) Let's create deque[m + 1] byExam, where byExam[i] contains days (in asc order) where we can pass exam number i
    2) Check whether byExam[1..m] has at least one exam (otherwise it's unable to pass everything)
    3) Create array exam[] where exam[i] = 0 if we don't wanna pass exam at day i, otherwise it contains exam number. At first, iterate over all exams in byExam array, poll last day for each exam and set exam[last_day] = exam_number
    4) Create partial sums on exam array. ps[i] = ps[i-1] + (is_exam_at_day_i ? -exam_cost[exam[i]] : 1); We add one to ps if we are free, otherwise we spent exam_cost[exam[i]] at this day
    5) Iterate over days in reversed order.
    5.1) if (exam[day] == 0) just continue
    5.2) if we have an exam at this day (exam[cur_day] is not 0), do the following:
    5.2.1) check, whether we can try to take this exam earlier. Just check whether byExam[exam[day]] has elements. If it has, set exam[day] = 0, exam[prev_possible_day] = exam_number, otherwise print day number and exit
    5.2.2) Iterate from prev_possible_day to cur_day, do ps[day] -= (1 + exam_cost[selected_exam]). If we have on any iteration ps[day] < 0, it's unable to take current exam earlier, so the answer is cur_day, print it and exit
    

    In other words, at first we choose the safest variant. Then we greedy try to pass last exam earlier.

    You can see my solution here: 21584671

    Also, the same idea is used in 722D - Generating Sets

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

    Failed in the system test though :p

    But the feeling was awesome for sure.

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

      Yeah, it was awesome, but this feeling is gone now :(

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

How to solve D

I first verified if it can be done in n days by taking last possible day for each test then iterating in reverse from nth day to 1st day and checking if ith day had an passed exam in my solution the can we pass that exam in any previous option i used segment tree + lazy for this can someone please tell me where am i going wrong

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

    binary search on the number of days . If you want to check if its possible to pass all exams in X days , find last occurence of each subject in [1,X] and take exam of each subject on its last occurence .

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

    Binary search!

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

This is interesting. Eveng though problem D and E worth the same amount of points, each minute problem D decrease its score by 6 points and problem E by 8 points.

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

I wonder how to write a checker for problem F???

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

    Build the directed acyclic graph of the strongly connected components and take the minimum size of a sink connected component.

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

    Just finding all strongly-connected components having no outcoming edges to another SCCs, and determining minimum between their sizes.

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

in problem B, when n=1 : (input) 1 3 1

can i get your guessing output?

i believe : 2 3

why system said? : 0 1

i think some mistakes in problem B description ..

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

    Empirically Polycarp learned that the dog needs at least k walks for any two consecutive days in order to feel good.
    There is no 2 consecutive days here.

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

      i cant disagree your reply !

      objectively i didnt understand problem fully :D thx for your reply :)

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

system test taking alot of time.

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

Solved D using binary search in contest.
But I guess O(n) should work.
Let extra be a variable that stores how many days we have to spare. Traverse from 1 to n.
If d[i] = 0 or vis[d[i]] = 1, extra+=1,
otherwise extra -= a[d[i]] and mark vis[d[i]] = 1
If at some i, extra ≥ 0 and we have visited all m subjects and d[i] ≠ 0, print i. AC

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

    Nice idea!

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

    Can you please explain what the checking function is doing ?

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

    Wouldn't it fail on sth. like this?

    5 2
    0 2 1 0 2
    2 1
    
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    you are assuming that we need to do an exam whenever it is possible to do it. But this is wrong, be cause you could save those days for some other exam which has to be completed first. I hope you understand what i said.

    counter testcase: 10 3 0 0 1 2 3 0 2 0 1 2 1 1 4

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

    6 2 1 0 0 0 0 2 1 1 I think the answer should be -1 in this test (your code output 6)

»
8 years ago, # |
  Vote: I like it -30 Vote: I do not like it

Simplest Solution for problem 'C':

public class C { public static void main(String args[]) { Scanner sc = new Scanner(System.in);

    long b=sc.nextLong();
    long d=sc.nextLong();
    long s=sc.nextLong();  

    long max=Math.max(b,d);
    max=Math.max(max,s);

    long ans=0;
    ans+=Math.max(max-b-1,0);
    ans+=Math.max(max-d-1,0);
    ans+=Math.max(max-s-1,0);
    System.out.println(ans);
}

}

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

Why am I hacked?It gives me right answer: http://codeforces.net/contest/732/submission/21523956

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

    ans wasn't given an initial value to 0 It outputs a random number if the program didn't enter your second loop

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

      It would give random number in any case, because ans=random ans=random+something Output:random+my_answer But it passed pretests

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

      :| ans is global, so it is initially 0.

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

    I ran your code on codeforces's custom test and it is answering currect to the hack!!!

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

      Maybe they check only the last solution (this is not my last) ?

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

C had an O(1) solution :

  • fr(i,0,3) cin >> a[i];
  • sort(a,a+3);
  • Long ans = max(0LL,(a[2] — 1 — a[1])) + max(0LL,(a[2] — 1 — a[0]));
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain it?

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

      lets denote t[0], t[1] and t[2] as total number of meals of type breakfast, supper and dinner that vasily was present at the Sanatorium and a[0], a[1] and a[2] as the number of meals he ate.

      My ans is (t[i] — a[i]) for i from 0 to 2.

      I claim that

      1. For any i,j : abs(t[i] — t[j]) <= 1 (convince yourself of this)

      2. Atleast one of breakfast, supper and dinner will not be skipped at all (Since we need to find the smallest bracket when vasily was present at the Sanatorium)

      So atleast there will be atleast one i such that t[i] == a[i] is true

      i set the t values for other two meals equal to t[i]-1 and found the difference with a[i].

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

        I am sorry, but I don't fully understand the meaning of t[i]. Shouldn't they all be the same?
        I mean
        t[0] = t[1] = t[2] = max(a[0], max(a[1], a[2]));
        ?

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

          Hey, Let me explain. First, the use of sorting is to find the maximum number of days, that are possible. Suppose, If the number of dinners are maximum, then we can enter just before dinner on a day and leave just after having maximum number of dinner. This leaves the possible consumption of other meals to be Total dinner — 1. If you think carefully, you'll see that the same would be for breakfasts and supper as all the things are circular.

          So, if m is maximum of (supper, breakfast, lunch), assuming all to be different, this leaves maximum of m — 1 days for other two types.

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

Hey, my submission for D is wrong but Accepted.

http://codeforces.net/contest/732/submission/21545380

because in this test case,

5 2
0 2 1 0 0
1 1

the answer is -1 but my program out 4.

What should I do?

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

    Your program actually gives -1 on the Codeforces Custom Invocation.

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

      Oh..., true.

      I beg your pardon.

      So, is my program right? Hmm...

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

http://codeforces.net/contest/732/submission/21523845

Any idea why this fails for Div2 B ?

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

    Because in your template:

    #define rep(i,x,y) for (__typeof(x) i=x;(x<=y?i<=y:i>=y);i=(x<=y?i+1:i-1))
    

    It also loops from reverse to start incase x > y i.e. at pos 1 and 0

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

    your rep(i,x,y) is defined in such a way that in this case it runs from 1 to n-1 i.e from 1 to 0.

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

    would be nice to be a specialist i guess :/

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

Can anybody help me plz? for problem D, i think my program isn't working right but it was accepted by main tests! here is the code :21544206

»
8 years ago, # |
  Vote: I like it -55 Vote: I do not like it

worst problem set and description ever

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

    one of the worst i think :)

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

    you are enjoying your right to downvote right? Downvote me then. I have nothing to do with my contribution. You better tell your friends to upvote you.

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

    C was the worst .

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

      I am a native English speaker and this contest is the first time I realized dinner != supper. Had to look it up to confirm. (Problem was clearly stated though)

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

Waiting For Rating Changes...

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

Wow, my E got TLE on the largest case

http://codeforces.net/contest/732/submission/21540600

I was using cin/cout so i tried changing to fast i/o.. was not enough...

Then I went back to the original submission and only changed stl::map for stl::unordered_map and it got AC...

http://codeforces.net/contest/732/submission/21548475

Seems that it is true that hash table are O(1)... I thought the hidden constant would not make it actually faster... sad to learn it this way, but better for next time!

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

Does round is Rated ?

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

Waiting for the RATINGS!!!!

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

was it an unrated contest? 377(div-2)

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

!!! Waiting for the rating change....

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

Is it rated contest or NOT?

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

round rated or not ????

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

Not specify in blogs that round is rated or not ? even round taker was not online till last 5 hours.

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

    regular CF round is always rated. foolish like you always makes it complicated

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

      bro, one regular CF round of div-1 was declared unrated after contest end due to some problem in test cases of one proble.

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

        If a regular round is declared unrated, you will surely get an announcement then during the contest

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

    "As usual, first division participants are able to participate out of rating."

    If they say that div1 participants are out of rating, that means div2 participants are in rating :)

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

why new rating didn'y apply yet?!!

»
8 years ago, # |
  Vote: I like it -9 Vote: I do not like it

why it will be unrated? I think rating will be given quickly. Plz------give the rating as quick as possible. After a long time awake for rating.

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

http://codeforces.net/contest/732/submission/21527638

http://codeforces.net/contest/732/submission/21540134

The two codes above got accepted on problem D, but in this case

8 3

0 0 1 2 0 0 0 3

2 2 1

the first one answers : -1

the second one answers: 8

the correct solution is -1.

Am i understand wrong the problem?

»
8 years ago, # |
  Vote: I like it -24 Vote: I do not like it

some people just comments for up vote(contribution)

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

Is it unrated contest?????

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

    The author of this contest is not announce it is unrated.So everybody waiting for their annouce.

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

    8 3

    0 0 1 2 0 0 0 3

    2 2 1

    this test case gives different answers for different solutions. but the correct answer is -1

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

    Due to NEERC subregionals in Saratov, rating will be updated tomorrow.

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

      how did you came to know that ? is it confirmed? why they hadn't posted this? and last, what is relation between both(neerc and cf rting)?

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

Maybe data set for problem D is weak.. Accepted output for the following test is -1. 16 3 0 0 0 1 2 3 0 0 0 0 0 0 0 0 0 1 3 3 3 But many accepted solutions are giving other outputs.

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Due to NEERC subregionals in Saratov, rating will be updated tomorrow.

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

Can any body tell me why i took TLE in problem D :\ 21538484 it is n log n

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

    21538484 is a "compilation errored" code and it's on problem 732E

    yours is : 21538383 :)

    and I'm kinda sure that the problem is your binary search.try to return your function when l==r.and in the last line of function I guess it should be bs(mid+1, r);

    I didn't read the whole code so I might be mistaken.

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

    I think it's better to implement binary search like this BS f(n) is a boolian function.

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

How to solve E? I see some greedy solutions but don't know how they work correctly. :/

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

After the round was over i was going through the solutions of some of the people to problem D and found one of the solution inspite of being wrong is accepted. Solution number 21543232 is wrong. For the test case 10 3 2 2 2 2 2 2 2 2 2 2 1 1 1 The solution gives the answer as 6 but the answer should be -1. Sadly the test cases are not strong at all.

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

I think that it is not fair to get a TLE in Problem D using Java , and an Accepted using C++14 with the same code.

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

Will it be rated for the 3-4 div1 participant that were considered as official participants ?
I was trying F thinking i am an unofficial participant instead of trying E, making it rated for us (atleast for me) won't be a fair !

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

    why they're not fixing your bug? really unfair for you

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

      I posted about it !! lets see if it gets resolved.

»
8 years ago, # |
  Vote: I like it +22 Vote: I do not like it

i suggest that MikeMirzayanov should give every contestant +50 for nothing , thanks

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think Codeforce should re-judge problem D. And if you do,please include the test case below:

10 3

0 0 1 2 3 2 0 0 1 2

1 1 4

Just a slight modification of first test case.

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

Question. Problem B.

_

if n=1 , Haven't I to satisfy the dog? I guessed, when I have input 1 10 1, I should walk 9 to satisfy the condition (to make total walk 10), but jury's answer is 0 1 Please let me know why..

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

On the last Intel contest i've done 1311 points and then i got more 31 rating points, on this contest i've got 1314 points but i've lost 75 rating points. Why?

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

    Look what rank you got last time and now. There is a big difference between 1402 and 2874.

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

      What about the fact that now may have more people which can be better than me? Instead of getting worse i just keep on the same level, but there are better people now. The rating should be about me not about the others.

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

        rating about you but hard level of problem about the other =))

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

Was Problem D Rejudged?

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

    NO

    Rating changed with all of wrong accepted solutions :(

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

For problem E I got the right idea but forgot to sort the sockets by its value, so sad.

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

I think in this round solutions don't checked with good tests, I found two accepted solutions in D problem, but solutions was wrong. Sorry for my poor english! My tests: 6 2 0 0 1 2 0 0 2 2

7 2 0 0 0 0 0 1 2 2 2

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

    This comment is right. Why is my solution Accepted? My solution is wrong.

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

    first solution is -1,second is 7,right ?

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

      My solution: in: 6 2 0 0 1 2 0 0 2 2 out: 6 //this is wrong in: 7 2 0 0 0 0 0 1 2 2 2 out: 7

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

I want to aks what is the meanning of d[i] in the question D ?

It is the number of subject or the sum of passed subject ?

(eg: if d[1]==3, it says that 1st day could pass 3rd subject or 1st could pass three subjects no matter whatever the number of subject ?)

plesase test this: 10 3 0 0 1 1 1 0 1 0 1 0 1 1 4

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

    The number of the subject which could be passed on day i.

    Answer is simply -1 since 2nd and 3rd subjects cannot be passed on any day.

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

In B I was considering n=1 case separately and was printing k-a[0] if a[0]<k. I later realised my mistake and hacked 3 submissions.

My first hacks :D

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

When I waked up and opened CodeForces website, I was so excited to find I turned purple :D
It's interesting and a pity that I have never got a 4/5 or 5/5 after 29 rounds, maybe I will jump back to div2 soon and get my first 4/5.

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

Can anyone explain to me the greedy approach of E and why does it work? and also F please :D

»
8 years ago, # |
Rev. 9   Vote: I like it 0 Vote: I do not like it

In problem E, I don't understand why my solution is using a lot a memory.

My solution is simple, first I sort all sockets, so for each socket e reduce it (ceil(x/2)) trying match it with a free computer.

to do it, I use a map <int, vector <int> > (vector of indices of PC's with power X). So, all memory that I use is O(n) in map + (n+m) of the input.

Link of Code

»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

when will the editorial be posted?

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

hello, I have participated in contest #377 Div. 2 I have One test for Problem D, many of codes can't pass this but they are still considered as right, please check it. 10 3 0 0 1 2 2 0 2 0 1 3 1 1 4 the answer is 10 but some codes that passed the testes are bringing 9 ^_^

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

    you make mistake 10 3 0 0 1 2 2 0 2 0 1 3 1 1 4

    day 1 preparation for first exam day 2 preparation for second exam day 3 participate in first exam day 4 participate in second exam day 5 to day 8 preparation for 3rd exam day 9 participate in 3rd exam.

    Now how you are true?

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

      day 9 participate in 3rd exam.
      How?

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

        cause in day nine you can participate at least in one subject. if i ask you why he cannot take part? don't get me wrong. if you show me the point why he can't then it will be easy for me to explain. within first 4 days you can complete first two exam. then 5 to 8 (4 day) for preparation for third exam and day nine 3rd exam. 1 indexing

        UPD:" it is not necessary to prepare continuously during ai days for the exam number i. He can mix the order of preparation for exams in any way." from problem statement

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

          first day you take preparation for first exam. since in day second you can't participate in exam; you can prepare for 2nd exam rather than rest.

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

            You can only take exam ai on day i.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    I vote to extend testing package too.
    In the name of Truth, those coders must not sleep well.
    
    There are such solutions which are certainly wrong:
        for(i=m+sum_of_a;i<=n;i++)
            if(d[i])
    		{cout<<i; return 0;}  
    
    Test 1 "one exam cannot be passed in [1,m+sum_of_a]":
    5 2
    0 1 0 0 2
    2 1
    answer: 5, correct answer: -1
    
    Test 2 "not all exams exist within [1,m+sum_of_a]"
    6 2
    0 0 0 0 1 2
    1 2
    answer: 5, correct answer: 6
    
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Where is the tutorial?

»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Am I the only one still waiting for the editorial?

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

Auto comment: topic has been updated by danilka.pro (previous revision, new revision, compare).