Блог пользователя danilka.pro

Автор danilka.pro, история, 7 лет назад, По-русски

Здравствуй, Codeforces!

Сегодня, 17 октября в 17:35 MSK состоится Codeforces Round #377 для участников второго дивизиона. Участники первого дивизиона, как обычно, смогут участвовать в соревновании вне рейтинга.

Задачи раунда взяты из комплекта задач регионального этапа Всероссийской командной олимпиады школьников, проходившем вчера в Саратове. Комплект задач для онсайта соревнования придумывали и готовили Михаил MikeMirzayanov Мирзаянов, Илья IlyaLos Лось, Данил danilka.pro Сагунов, Владимир vovuh Петров и Роман Roms Глазов. Благодарим многих участников команд Саратовского ГУ за прорешивание соревнования. Одна задача будет присутствовать на раунде в несколько усложненной версии.

С подготовкой задач и переводом к раунду нам помогали Николай KAN Калинин и Татьяна Tatiana_S Семенова — спасибо! Спасибо Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon.

На раунде вам будут предоставлены 6 задач и 2 с половиной часа на их решение. Желаем удачи!

Если вы участвовали во вчерашнем соревновании в Саратове, пожалуйста, не регистрируйтесь на раунд и не участвуйте в нем, а также не обсуждайте его задачи до окончания раунда.

UPD Разбалловка: 500-1000-1500-2000-2000-2500

UPD2

Поздравляем победителей!

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

В связи с ранним временем регистрации на раунд в раунде могут присутствовать несколько участников первого дивизиона, участвовавшие наравне с участниками второго дивизиона. Так как таких не очень много, а исправить эту ошибку представляется технически сложным, все решено оставить как есть.

Так как в Саратове проводится Южный четвертьфинал, пересчет рейтинга будет осуществлен завтра.

UPD3 Разбор

  • Проголосовать: нравится
  • +146
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -49 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

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;

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Fixed, thanks!

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

I feel that the round will be unrated!

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    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

»
7 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Pay attention, Problems may be not sorted by difficulty.

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Let is delay 10 minute as usual :)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

what??

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

    Anyway problem set were good this time

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How do you solve C?

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

      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. :)

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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) :)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I initialized ans=-1 :'(

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hack case for C ?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Очень много решений упадёт на С. Можно ссылку на FAQ по взломам ? Так и не нашёл в интерфейсе как это делать... Есть менюшка "Взломы", но там почему-то только мои взломанные решения

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

input

1000000000000000000 0 1000000000000000000

output

999999999999999999

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Approach for problem E?

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +14 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you prove this greedy solution please?

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C ?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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.com/contest/732/submission/21541116

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Problems difficulty is perfect.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's the idea for solving F ?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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.com/contest/723/problem/E
    The overall complexity is of the order O(n+m).

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    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.com/contest/732/submission/21563511

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.com/contest/732/submission/21541488

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Binary search

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Have any bruteforce solution of D(without binary_search).

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Всем добрый вечер! В задаче №2 возник вопрос. По условию сказано "Вы можете считать, что в день до первого и в день после n-го Поликарп выгуливал Кормена ровно по k раз." Подскажите пожалуйста, почему авторское решение выдаёт в тесте

2 5

0 0

ответ 0 5?

(из взломов участников)

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Очень жаль. :( В условие сказано, что для КАЖДЫХ двух соседних

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    а что не так? в -1 и 0 день 5,в 1 и 2 день 5,во 2 и 3 10

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    • 0 | 1 | 2 | 3 -- номер дня
    • 5 | 0 | 0 | 5 -- расписание прогулок у Кормена

    Можно заметить, что суммарно в дни с номерами 1 и 2 Кормен должен погулять хотя бы 5 раз, но гуляет 0 раз. Поэтому необходимо распределить эти 5 раз между этими двумя днями. Подходит любое распределение, например авторское:

    • 5 | 0 | 5 | 5 -- скорректированное расписание прогулок Кормена
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

где же системное тестирование...

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ..

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      i cant disagree your reply !

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

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

system test taking alot of time.

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

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);
}

}

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

Эм. У задачи D слабые тесты. Я увидел как минимум одно решение, которое упадёт вот на таком тесте:

6 2
1 1 1 1 1 2
1 1

Решение

Более того, моё решение по этой задаче так же является неправильным, но оно не работает уже на другом тесте:

6 2
1 0 0 0 0 2
1 1
»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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]));
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain it?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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].

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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]));
        ?

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          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.

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Hey, my submission for D is wrong but Accepted.

http://codeforces.com/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?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Any idea why this fails for Div2 B ?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -55 Проголосовать: не нравится

worst problem set and description ever

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Нашел дырку на задачке Д. В одном тесте два решения дают разные ответы, но при этом обе Accepted)

Вот сам тест: 10 3 1 2 0 0 0 0 0 3 2 1 1 1 1

правильный ответ: 10

но некоторые решения дают 8)

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    можно свести к более простому тесту

    10 2
    0 0 0 0 0 0 0 0 1 2
    1 2
    
    Корректный ответ: 10
    Некорректный вывод, который есть у некоторых решений: 9
    
»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Waiting For Rating Changes...

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

о, вижу не только я заметил.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Wow, my E got TLE on the largest case

http://codeforces.com/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.com/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!

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Does round is Rated ?

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Waiting for the RATINGS!!!!

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Is it rated contest or NOT?

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

round rated or not ????

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -14 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "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 :)

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Будет ли разбор?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why new rating didn'y apply yet?!!

»
7 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

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

http://codeforces.com/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?

»
7 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

some people just comments for up vote(contribution)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was it rated ? :-"

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it unrated contest?????

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 !

»
7 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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..

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Здравствуйте.

Если не ошибаюсь, то Codeforces Round #377 (Div. 2) рейтинговый только для участников второго дивизиона (Div. 2). Но если посмотреть : вторую и третью страницу изменения рейтинга, то можно заметить как у двух Кандидатов в местера ( это lollollol и MStrechen ) изменился рейтинг после этого соревнования. Это ошибка системы или я чего-то не понял?

Спасибо за внимание.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    В связи с ранним временем регистрации на раунд в раунде могут присутствовать несколько участников первого дивизиона, участвовавшие наравне с участниками второго дивизиона. Так как таких не очень много, а исправить эту ошибку представляется технически сложным, все решено оставить как есть.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was Problem D Rejudged?

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Всем привет ! Баг кодфорсес , этот парень -> lollollol был зарегистрирован неофициально в кодфорсес роунд 277 (div 2) , но у него прибавился рейтинг + 12 , не верите сами посмотрите :)

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    В связи с ранним временем регистрации на раунд в раунде могут присутствовать несколько участников первого дивизиона, участвовавшие наравне с участниками второго дивизиона. Так как таких не очень много, а исправить эту ошибку представляется технически сложным, все решено оставить как есть.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Всем привет, почему это решение работает? http://codeforces.com/contest/732/submission/21567805 Ведь на тесте такого вида должно валиться: 7 2 0 0 0 0 0 0 1 1 1 Этот код выводит 7, а ответ -1

»
7 лет назад, # |
Rev. 9   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

when will the editorial be posted?

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 ^_^

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      day 9 participate in 3rd exam.
      How?

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    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
    
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Where is the tutorial?

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Am I the only one still waiting for the editorial?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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