Автор KAN, 7 лет назад, По-русски

Всем привет!

Завтра, 24-го марта 2018 в 18:35 по московскому времени состоится второй отборочный раунд чемпионата VK Cup 2018! В нем сразятся 450 команд, которые стали лучшими в первом раунде и первом уайлд-кард раундах. Лучшие 100 команд в завтрашнем раунде выйдут в раунд 3 напрямую и получат футболку чемпионата, остальным же можно будет пожелать удачи во втором уайлд-кард раунде.

Для тех, кто не прошел в раунд 2 или просто не принимал участие в VK Cup 2018, состоятся параллельные раунды Codeforces как для первого, так и для второго дивизиона. Участвуют все!

VK Cup 2018 Раунд 2 и раунд для первого дивизиона будут содержать шесть задач, раунд для второго дивизиона — пять.

Авторами задач являются cyand1317, skywalkert, Claris и я. Большое спасибо fcspartakm и Tommyr7 за помощь в подготовке задач, а также PavelKunyavskiy, winger, AlexFetisov, Errichto, vepifanov, immortalCO и qwerty787788 за тестирование! Кроме того, огромное спасибо vintage_Vlad_Makeev за помощь в координации и тестировании раунда!

Удачи!

Обратите внимание, начало раунда 3 перенесено на 16:05 по московскому времени 29 апреля из-за того, что недавно было анонсировано соревнование Google Code Jam, в котором раунд 1B пересекается с изначальным время для раунда 3 VK Cup.

Опубликован разбор.

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

VK Cup Раунд 2:

  1. Нижний Магазин SU: BZ: LHiC, V--o_o--V — решили все задачи!
  2. Z: egor_bb, Nikitosh
  3. Road to the Gucci store: -imc-, Golovanov399
  4. Ананас: AllCatsAreBeautiful, arsijo
  5. я и моя девушка: aid

Div. 1:

  1. Um_nik
  2. Radewoosh
  3. ikatanic
  4. FizzyDavid
  5. jqdai0815

Div. 2:

  1. ltf0501
  2. Hyperbolic
  3. yongshiboshi
  4. emengdeath
  5. lmhoang
  • Проголосовать: нравится
  • +209
  • Проголосовать: не нравится

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

Is it rated for div2?

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

I would suggest closing registrations for now and resuming it after system testing for Round 471 has been done. As otherwise, people currently in Div 2 (who are going to Div 1 after rating update) will register in Div 2 creating a messed up list.

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

Wow ,i had miss this , 3 contests in 3 days

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

I love Codeforces beacause of many contests these days! :)

I wish you successful submissions, many hacks and high rating.

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

Hopefully you'll enjoy these problems. Wish you a high rating!

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

Three in a row

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

Is it rated for VK Cup Round 2 participants?

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

another contest storm , almost everyday , i think it's gonna be contest overflow :D

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

It is raining contests...!!!

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

Can we expect 6000 participation today??

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

наверное, вы заметили, что на прошлом раунде CF-Predictor плохо справлялся со своей работой. так что сегодня я выпустил новую версию, она должна корректно показывать предсказания для всех команд (включая команды с русскоязычным названием и команды состоящие из 1 человека)

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

Is it just like the last contest, only has three problems in reality? Just be faster.

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

I was just wondering when the score distribution would come out...

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

For God's Sake , DO NOT UNRATE THIS CONTEST , I HAVE DONATED YOU CODEFORECES COMMUNITY

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

....

i can't access my codeforces for 5 minute it said server error.

and now the judge isn't working?

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

A lot of "in queue" submissions, yet no submissions are being judged. Something is going really wrong this time.

UPD: Just seen the announcement. Well, this is unexpected.

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

The Problem States:- "Two ways are considered different if and only if a segment is painted in different colours in them."

"Only if" and "a" ? Then how are CYCMY and CYMCY different? There aren't "Only 1" difference there? If what they are meaning is "Two ways are considered different if any segment is painted in different colours in them." then the problem statement is wrong.

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

    IMO "a segment" phrase has meaning close to "some segment", which is technically any segment

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

      How "only if a segment" and "only if any segment" are same?

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

        I think, when we use indefinite article a/an, we mean "someone", in contrast to "exactly that one".

        So when I was solving it, I assumed "if and only if" there means (ways are different -> some segment is different) && (some segment is different -> ways are different)

        Have you asked jury to clarify that?

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

    "Two ways are considered different if and only if a segment is painted in different colours in them." means "Two ways are considered different if and only if (at least)a segment is painted in different colours in them."

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

    The phrase "if and only if" is used to declare a coimplicative relationship. That is, ways are considered different if (condition), and only if (condition) they are considered diferent (if (condition) is not satisfied, they aren't different). Its meaning is not related to "only one segment".

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

Anyone knows the test case 5 for Problem C of Div2 / Problem B of Div1 ?

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

My hacks for B:

4 10000
1 10 11 100

Answer: 89/90, Wrong answer: 90/99

4 1
1 2 3 100

Answer: -1, Wrong answer: 0

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

    B?

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

    My hacks for Div2A. I managed to make 8 hacks in total. That includes hacking 3 people twice... Here my tests with correct answers.

    6
    Y?C??C
    Yes
    
    3
    Y?C
    No
    
    2
    YC
    No
    
    3
    Y?Y
    Yes
    
    100
    ????????????????????????????????????????????????????????????????????????????????????????????????????
    Yes   (Forces TLE)
    
    1
    ?
    Yes
    
    2
    ?C
    Yes
    
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Lo_R_D why Wrong answer : 0 ?

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

      E[i] = 2, E[j] = 3, E[k] = 3

      answer = (3 - 3) / (3 - 2) = 0

      j == k — wrong.

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

      All E_i are different, so in order to be able to pick three of them, E_k — E_i should be at least 2 (since E_j is between E_k and E_i). So all tests where U = 1 have answer -1.

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

me during the contest ...

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

one of my hacks is still showing "In queue" . Will it be counted?

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

How would I check for which planes could arrive at the same time if they came from the same direction?

Edit: This is for Div 1 D

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

    (X[i] * V[j] — X[j] * V[i]) / (X[j] — V[i]) <=W

    You can divide each speed by W, thus getting X[i] * V[j] — X[j] * V[i] <= X[j] — X[i]

    X[i]/(V[i]+1) <= X[j] /(V[j]+1)

    and the same for >= -w :)

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

    my idea was to find what will be the time taken if wind speed is -w and w and then if 2 planes can meet than time taken by one plane will be more than second for +w wind speed and less for -w wind speed.

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

    Let t(i, vair) arrival time for vair airspeed. If direction is same, it holds when xi < xj AND (t(j,  - w) ≤ t(i,  - w) OR t(j, w) ≤ t(i, w)).

    This reduces to finding a pair i < j such that xi < xj, yi < yj, zi < zj.

    Sort by x-coord, and do divide and conquer. Let L a set with Xi ≤ M, and R a set with Xi > M, then we should find a pair such that . This can be done with binary indexed tree. Thus, T(N) = 2T(N / 2) + O(NlgN) = O(Nlg2N)

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

    You can get minimum and maximum arrival time for each plane.

    Then they can arrive at the same time (if they go in the same direction) iff one [mintime,maxtime] is included in the other.

    I didn't manage to count inclusions in an acceptable time during the contest though.

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

    For each plane create a point (xi, vi). Sort all points by angle around point (0, w) and point (0,  - w). You get 2 permutations of points a and b. You need to find number of pairs of points such that in a the first point comes before the second and in b the first point comes after the second. It's the number of inversions in a - 1b, which is a classical problem. You also need to handle the cases when 2 points have the same angle accurately in the comparator.

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

Can anyone please see why my nlog^2n solution for D is giving TLE? https://ideone.com/WGUMhc sorry for bad indexing of part where 2d Fenwick tree is declared though u may skip it as i had directly copied an implementation

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

RIP T-shirt :(

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

will the round be semi rated or unrated because of the long queue?

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

    It really impacted some participants including me. I checked my solution of Problem C during the long queue.And finally I didn't have time to code Problem D which I think I can solve it during the contest.

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

I have solved problem B for Round #471 in a video , the link : https://youtu.be/IG88Al6fWec

and i will solve problems A and B of this contest in a videos

channel link : https://www.youtube.com/channel/UCmWvb73kIq_oRThWd05Mtfg

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

How to solve div1D. I think we can reduce the problem to count the number of lines that have abs(slope) <= w if each plane is converted to a point (1/xi,vi/xi). How to solve the reduced problem?

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

    if the wind power is -w and two plane meet at p1<=0 && if the wind power is w and they meet at p2>=0 then they are counted

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

Hello, I want to ask how to solve Div 2 C? My solution is: http://codeforces.me/contest/957/submission/36598579

Basically I fixed for all index k, I want to find the first index i where Ei >= Ek — U, then to maximize the answer obviously j is equals to i + 1. Does the greedy solution above not work?

Please kindly give me corner test case and explanation if you don't mind.

Thank you!

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

    Cant See your solution now but I did the same thing. Hope i pass the sys tests. Did you handle the case of -1?

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

    Noticed my mistake. I think in this case I should fix all index i, not k.

    Corner case:

    4 10000 1 10 11 15

    My solution answers: (15-10)/(15-1) = 0.357142857

    Expected: (15-11)/(15-10) = 4/5 = 0.8

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

del

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

how to solve div2d/div1c?

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

Does anyone know pretest #7 for Div. 2 D? Thanks

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

i think GreenGrape can learn how to make a round from you :V Good round guys

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

how to solve div2d/div1c?

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

    hint : you can draw a line between 2 already drawn lines.

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

    Don't add any new marks until you need to. Keep track of the records where you didn't create a new mark.

    Take this case: 0 0 0 1 0 4

    Before we see record of 4, ans should be 1. We only created a mark for the first 0 and the 1. Then we know we didn't create any new marks for the second, third, and fourth 0. Now when we see record of 4, we know we need to add 2 new marks on the previous records (not including the current 4).

    Now insight is that we should greedily add marks to the most recent records where we didn't create any new marks. This is because if we add a mark for some record, all records after it no matter what will have to contribute +1 to the answer. So we should add marks to the third and fourth 0. Adding mark to third 0 increases ans by 3 and adding mark to fourth 0 increases ans by 1. Now we can create new mark for the record 4 below all other marks, and will satisfy the condition of 4 marks above it. Thus ans is 5. Note that now we should get rid of third and fourth 0 from our list of where we didn't create any new marks.

    Since each record creates a mark at most once, complexity is linear.

    Maybe a little confusing, I can elaborate more. Also disclaimer I haven't passed sys test.

    Edit: passed

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

    you can keep track of the minimum number v of marks that appear after day i.

    You know that they are non decreasing, so you can build them from left to right as you read the vector.

    Then you need to go from right to left and make sure the increments of your list are at most 1 per day.

    With v and m, you can get the minimum number of underwater marks for each day.

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

In Problem A it states "You are to determine whether there are at least two ways of colouring all the UNPAINTED SEGMENTS so that no two adjacent segments are of the same colour". In case of NO unpainted segments, if the painted segments have no adjacent same colours, it should be yes according to this. Very incorrect and unclear wordings!!!

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

Why there is no penalty for WA on first test, but there is penalty for WA on other samples? :/

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

    i think the concept behind this is the problems that have multiple solution, so if one can't trace his solution he can submit it and see if it's right or not in the first case

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

    In order to give some mercy for people which submit wrong files, for example from different directory.

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

(I didn't calculate correct complexity, this code runs in O(n))

I think that the C test cases is weak.

Check this solution: 36587731

This get ACC, but is a O(n^2) solution.

I think that this test break:

100000 1000000000 1 2 3 4 ... 100000

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

It seems like we are going to get new top rated user after rating update :)

Congratulations, Um_nik!

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

Mystical Mosaic test cases are not appropriate. My wrong code has passed all the test cases. My code gives Yes for this input:- 2 5

...

.#...

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

Why is this running on pretest 1 ? http://codeforces.me/contest/957/submission/36588552

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

Hi, can some author pls check this my same solution got tle in contest and passes outside.
TLE(during system test):- http://codeforces.me/contest/956/submission/36596404
AC(same code after contest):- http://codeforces.me/contest/956/submission/36601475

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

What a code written by xepher52447 ! It takes 30 minutes to test it ! :p

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

Why is there such a large difference in runtime?

http://codeforces.me/contest/956/submission/36601805

http://codeforces.me/contest/956/submission/36601828

The only thing I changed was reading in integer instead of double. This cost me 30+ minutes and 5 resubmissions ...

P.S. My submission which got TLE on test 7 now passes ...

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

    'P.S. My submission which got TLE on test 7 now passes ...'

    You submitted it with different version of compiler

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

in problem c in div 2 how the answer of test 22 is 0 ?

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

    I'm sorry, but in test 22 answer is -1. It's impossible that the answer is zero in this problem, because all the energies are distinct

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

Когда ждать футболку?

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

WOW, first time I have full AC due to time extend. Want to say "Thank you" to your electricity supply. :-)

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

    Wow your submission passed in 998 ms :)

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

      Yeah, I'm very lucky at this contest. Instead of reading to an int and typecast to long double, I read directly to long double variables using cin. This process is very time-consuming and many submissions do like this had been TLE. :-)

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

cool contest... :)

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

Great... the contest made me need 8 point to 3 point...

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

.

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

Has somebody received a t-shirt? Or email about it?-