Блог пользователя ItsNear

Автор ItsNear, история, 4 месяца назад, перевод, По-русски,

UPD: обратите внимание, распределение баллов изменилось

UPD2: LHiC нашел ошибку в авторском решении на div1-F. Мы исследуем вопрос.

UPD3: мы нашли правильное решение для div1-F и оба решения отправленных на контесте проходят все тесты против правильного решения => раунд по прежнему рейтинговый.

Всем привет,

Время старта Codeforces Round 488: 16.06.2018 19:35 (Московское время). Это будет раунд для обоих дивизионов. Раунд будет длиться 2.5 часа (это на пол часа больше чем обычно).

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

На контесте будет предложено по шесть задач в каждом дивизионе, 4 задачи из которых общие.

Почти все задачи взяты с тестовых раундов, которые проводились на JavaBlitz в прошлом году. Если вы участвовали в одном из JavaBlitz раундов, то этот CBR, к сожалению, придется пропустить.

Распределение баллов в первом дивизионе -- 500-1000-1000-1500-2250-3000

Во втором -- 500-1000-1500-2000-2000-2500

Раунд в обоих дивизионах рейтинговый.

Все задачи написаны мной, Александром "ItsNear" Скидановым, и Никитой "neckbosov" Босовым. David "pieguy" Stolp, Александр "AlexFetisov" Фетиско, Marcelo "MarX" Fornet, Николай "KAN" Калинин и Михаил "cerealguy" Кевер оказали неоценимую помощь в подгтовке раунда и тестировании задач.

В завершении хочется в очередной раз напомнить, что мы постоянно ищем людей, которые помогут нам с разметкой данных с архивов по спортивному программированию. Больше информации здесь.

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

Div. 1:

  1. Um_nik
  2. Errichto
  3. scott_wu
  4. Reyna
  5. matthew99

Div. 2:

  1. FiveAtomTree
  2. shayan.p
  3. gauss148
  4. kessido
  5. codejudge

Разбор опубликован тут. Спасибо за участие!

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

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

Where is this:"Thanks to MikeMirzayanov for the platform"? :)

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

Which one is true ??!!

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

Как понять, не знаю ли я задачи? Я в тех раундах не участвовал, но вполне мог обсуждать их.

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

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

    Если хочется быть уверенным на 100%, то прочитай в начале раунда просто задачи в середине (C или D например), на предмет того знакомы они или нет, прежде чем что-то отправлять.

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

Wtf,Who the hell is this Near??He oesn't have even a cf handle??

UPD:ITsNear :P

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

So fast problem distribution :)

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

Round in feast

»
4 месяца назад, # |
  Проголосовать: нравится -56 Проголосовать: не нравится

The round coincides with Peru-denmark match

Although it's not a very important match but please set the upcoming contests time in such a way that it doesn't coincide with other games

sorry for poor English:)

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

    Nobody cares about Peru-Denmark match ;)

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

      Really true

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

      Come on, man. I may be the only active coder on Codeforces rocking the Danish flag but did you know it is the oldest flag in the world? Give the country some credit!

      (I am not mad about the contest time fyi, I got work taking up my schedule anyway)

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

    Wanna watch this match ? Stop coding and start watching :) no one's gonna disturb you I think :)

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

Hope you spot the references :)

»
4 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

what is this codeforces arena in this video? :) https://www.youtube.com/watch?v=icoAK6yMCjg

Not released yet?

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

NEAR is the name of an anime.

»
4 месяца назад, # |
  Проголосовать: нравится -63 Проголосовать: не нравится

Who is excited for Russia fifa world cup 2018.

downvote if u r can't wait for it

upd:Messi is better Than cr7

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

Does nobody have a problem with the fact that apparently problems are recycled from JavaBlitz? For me I guess I can't compete in this round as I believe I did JavaBlitz practice rounds (although they were 1 year ago and at this point I don't have idea). But what about people who looked at problems a year ago but didn't compete, and don't quite remember what JavaBlitz even was. Seems like bad habit to me to post contests to Codeforces with problems, that are visible to anybody, and then reuse problems for contest a year later.

But maybe I misunderstand situation and it is not a issue for some reason.

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

    It is a reasonable concern. However the problems were not visible to anybody, we actually tracked all the problem views on JavaBlitz (only logged in users could see the problems), and the total number of people who saw at least one problem across the two rounds is 19

    We sent all of them to Mike, I assume they just won't have an option to register.

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

      So the problems are no longer visible on the Internet? What about the people who know them from word of mouth from th 19 who for sure saw them? Particularly those who will ask those directly to tell them what the problems were.

      Anyway, practice and fun should be the main reasons so I suppose the issue is kind of mute, but I just couldn't help notice than in CF rounds with "known" problems, there are a lot more accepted submissions, which of course disadvantages those who like me, didn't know the problems in advance.

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

It's Near for soo long

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

Задачи машина придумывала?)

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

Flood of contests Thanks MikeMirzayanov for contests.

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

to be Expert .. me not you :p

»
4 месяца назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

you should thank me for participing

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

What is the score distribution? and how does it relate to rating?

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

    Those are the maximum scores you can get for each problem (if you solve each in 0:00 time). The score gets decreased as the time goes on, and the final score you get is the sum of the scores of problems you solved (and hacks). It's not directly relevant to your rating, as the rating is affected by your rank in the contest, not the absolute score you got.

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

    not-important

»
4 месяца назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Контест див.2 будут решать те, у кого рейтинг ниже 2100 или 1900?

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

    Как написано здесь, для совмещенных Div. 1 + Div. 2 раундов распределение по дивизионам остается без изменения, то есть в Div. 1 редакцию раунда будут попадать участники от 1900 единиц рейтинга и выше, поэтому Div. 2 будут решать те, у кого рейтинг ниже 1900.

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

Coderforces round > Peru vs Denmark

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

Wish you all a happy Eid Mubarak from Bangladesh

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

Chinese contestants will have to stay up until 3am :(

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

Brazilians contestants are going to miss half of Brazil vs Switzerland match :(

edit: Actually the Brazil match will be on Sunday. The conflict is in the Peru match

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

»
4 месяца назад, # |
  Проголосовать: нравится -35 Проголосовать: не нравится

who will win WORLD CUP ?

you are with ?

i support messi

»
4 месяца назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

No its far.

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

EID MUBARAK. Happy Coding.

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

6 problems total, 4 shared. So Div 2 C is Div 1 A.

»
4 месяца назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

The timing is shifted by 2 hours.

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

У Александра фамилия не "Фетиско", а "Фетисов".

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

hopefully have a world cup theme :)

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

Div.2 D and Div.2 E has the same score. weird

Same thing with Div.1 B and Div.1 C

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

ItsNear to the contest start!

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

Eid Mubarak to all contestants...

Good luck.

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

CF is working very slow. I'm getting 502 gateway error.

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

Contest on Eid-Day ^_^

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

Oh yeah

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

wtf says in the statement of D, it is impossible to understand

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

    then you should try E, its statement is most ambiguous

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

    I still dont get how D works. Worked a solution based on the explanations. (Though got WA because of weak pretests even though there was 20, but after getting wa, found my mistake)

    Anyway still dont know why i did what i did.

    Maybe it said, there are random pair of points. Find the common number in the pairs that was given to both of them. If there are more than one common points but those 2 persons can still differentiate those then ans is 0 else -1.

»
4 месяца назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится

What's the pretest 4 in Div.2 B?

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

А падение баллов по задачам адаптировано под то, что контест длится 2,5 часа?

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

the end is near ..

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

IMHO, this problems is not about hard interesting ideas, math, algorithms, data structures. It's about clear coding, being very careful, being able to find all cases and being able to test your programm well. It's not bad problems, I just really think it's not codeforces or competitive programming style problems, it should be educational problems for software developers or something.

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

    There was a post a while back about what the best CP sites are, and for me this is why CodeForces is not top. I think this is regularly a problem with CF rounds, just more accentuated in this particular round (at least for Div 2).

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

Что делать, если на компьютере один ответ, а у проверочной системы другой? Входные данные одинаковые

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

Is rate of fall of points for a question reduces? As some contestants got odd number of points which I haven't seen before!

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

сорян, но полностью отбитые условия div2D

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

Well, the most boring contest I have ever seen. Left after reading E. Standard ABCE (just coding problems), couldn't understand what D says.

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

Tfw educational round is more creative than this.

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

How to solve E ? I think about 2 hours for E :|

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

How to solve Div2-D? I didn't even understand it.

»
4 месяца назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Most boring 2.5 hours ever :v

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

Contest of short consntrains!

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

How to solve div2 -c ?

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

    what is pretest 4 of div2 C???

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

    Just IF ELSE will DO

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

    First I checked every vertex and the center point of the oblique square, if it is contained in the other square then the answer is YES.

    Then I rotated the coordinates axes of 45 degrees ( https://en.wikipedia.org/wiki/Rotation_of_axes ) and did the opposite.

    It probably isn't the best way

    EDIT: Fuck yes it got accepted

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

      No need to rotate though! Just use a different equation for the rotated square: |x — cx| + |y — cy| <= d/2 where (cx, cy) is the center of the square, and d is the diagonal length.

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

        Yes I know, I couldn't figure the equation. Where did you get it? Because I would have used something with Pythagoras. I don't understand why it works in your way.

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

    Iterate through all integer point in the parallel square, and check if it is in the rotated square (can be done by calculating mahhattan distance to the center of the rotated square).

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

    I tried this and got WA on pretest 10:

    Let the square be ABCD, and we iterate over the points P in the other square. Calculate AB × BP, BC × CP, CD × DP and DA × AP; P is inside ABCD iff all of these complex cross products have the same sign, at which point print yes and exit.

    Swap the squares and do that again. This was all inspired by 29.2 in the PDF in this blog post.

    EDIT: Does not work because doesn't account for the case where the squares intersection region does not include any vertices of the squares. Same is true for my other post below :(

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

    Also, calculating the areas of the four triangle formed by a point P and the sides of ABCD and comparing this with the area of ABCD should work.

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

    Checking if a point is inside a rectangle/square is a standard problem ( check this https://www.geeksforgeeks.org/check-whether-given-point-lies-inside-rectangle-not/ ). Now for all x,y co-ordinates possible from -100 to 100, check if a point lies inside both the squares. If yes, they intersect.

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

    My solution:

    1) Mark all integer points on the edges of a second square.

    2) Iterate through all points inside the first square, check if point is marked.

    3) Mark points in the first square and check second square.

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

      step 3 is not required.

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

        Step 3 is the case when the first square is inside the second one. If you omit it, you will get WA 5.

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

          You marked all the points inside second square, so while you iterate through all points inside first square, you'll find points already marked, since first square completely lies inside second square.

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

            Oh sorry, you are right. I marked points on the edges of a square.

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

    In Div-2C You can also use point in polygon algorithm to check whether any point from any square is inside or on the other square.

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

    for all (x, y) iterate from -100 to 100 and see if any point is found in both square.

    Complexity O( 200 * 200)

    or u can find minX, maxX, minY, maxY and some if else's.

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

share a hack data for problem C 1 1 1 1 just for the people who are too rigorous

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

It is obvious that we should use FFT to solve div1.E, right? I am so regretful that I don't have FFT code...

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

How to solve Div2-D? Thank you.

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

    For each pair of each person, we will find out the list of pairs belonging to the other person, that two pairs only have one common number.

    The answer will be:

    • A digit from 1-9: only when all possible sets of 2 pairs have similar common number.

    • "0": Both players can determine the number (since they know their own given pairs, while you lack such informations), but there are different digits that could be the answer (which you cannot decipher, since you lack the aforementioned info).

    • "1": Other cases. Technically, at least one player cannot determine the common number.

    The determination can be done by brute force. From a player's pair, iterate through all pairs of the other player. That pair won't cause ambiguity when either no pairs from the other player have exactly one common number with it, or every pair that does returns the same number.

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

in problem B ,, who else missed that the answer was the maximum number of coins ?

»
4 месяца назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

was this a rated contest??

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

Что делать, если на компьютере один ответ, а у проверочной системы другой? Входные данные одинаковые

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

Today my solution for Div1C was hacked. Then I wanted to know if it was hacked because of what type of error (like wrong answer or TLE). To know this I had to make a dummy wrong submission. Doesnt it make sense to also add what type of mistake the hack exploited(Like WA or TLE or maybe RE). Or is there anyway to know it without a dummy submission??

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

damn. For problem D, I thought the first condition was "if you can determine that number, print 1" for some reason. rip. How did I get 10 pretest cases?

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

    I had to read the statement 10 times to understand it. For me it was very confusing.

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

    Omg, same as me.. I kept thinking for 40 minutes until I saw it.

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

    Yeah, same. As always, reading turns out to be the hardest part of problem solving... .-.

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

What's pretest 8 of D?

I tried to solve D by sorting by descending power-requirement, then doing dp, storing amount of computers with exactly one task currently assigned, and total amount of processors in use. If multiple have the same power-requirement, handle them at once. This has time complexity O(N * N * B), where B is maximum amount of processors a task uses. However, this fails to pretest 8.

Edit:

Participant's output

1289043069

Jury's answer

1289043070

Nice, I somehow managed to misunderstand what it means to round up, I rounded (for example) 0.3 to 0 instead of 1. Quick fix and AC :P

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

I've got WA on Pretest 7 in Problem D. Does anyone know the test?

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

Why the hell there's All pi's are distinct condition in Problem B? I lost time implementing without that condition.

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

    To make coding easier?

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

    noooo;(, I never read that, god i spent so much time , i did it for that condition and still got wa on C and D;(

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

    stl map

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

    I also didn't read that line and skipped it because C looked more promising. :(

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

    Same here @asgar, didn't even know all pi's were different until i read your statement. Lost 10+ minutes there, plus the drain on every other question after that :'(

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

    Yeah, coding is easier; sort from small to large powers, then iterate over the knights, each time tossing the previous knights' coins into a priority queue.

    Without that condition it's much less clean to add things to the priority queue.

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

When you read Div2B and all the contest you think you need to choose a subset of k killable elements to maximize the sum less than P[i]... and it turns out you ONLY need to choose the k maximum elements under P[i] :( ... What the hell happened to my brain ?! :'(

Solved Div2C and didn't solve the easy peasy Div2B ...

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

The contest of invisible corner cases. Bye-bye rating, hello attention.

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

    You know, I made a lot of incorrect submissions (five, to be precise), and still got my rating increasing from ~1700 to ~1800. A particularly nice thing about CF is that it values correct submissions a lot, even if they are made after many wrong submissions.

    My point is that you should try hard to solve as many problems as possible, even if you have already made some wrong submissions, and never ever give up!

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

    I've come here to look the same 'why' up. You inspired me to figure it on my own

    UPD: Done. Apparently, I've just misread the statement... I's trying to find out the pair instead of the common number (and second thing, I's printing 1 instead of the number). Yep, gotta be more careful

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

Silly solution of div2A. 39292471

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

That moment when you realize in problem D you should print the correct number instead of 1......

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

How to solve div2-E?

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

    To make an enemy spaceship destroyed, one of our ships must stand at the middle point between them.

    Technically, there are 40000 possible positions. But we're not iterating through all of them (It will guarantee a TLE verdict at large tests).

    Let's iterate every ship from the left side, then with each ship iterate every ship from the right side (or you can choose the vice-versa order, doesn't matter).

    Denote the left ship's y-coordinate as y1i, the right ship's y-coordinate as y2j, to destroy both of them one friendly ship must stand at the y-coordinate of (y1i + y2j) / 2 (for simplicity, you might consider only caring about the value (y1i + y2j)). Add this pair of enemy ships to the list of possible takedown pair if standing at the aforementioned y-coordinate.

    Keep only the y-coordinates that if standing there, at least one pair of enemy ships will be destroyed. From this point, you can simply do a quadratic-time-complexity iteration to find out the answer (since the maximum number of valid coordinates cannot exceeds nm).

    Total time complexity: O((nm)2).

    Update: There are times when there exists exactly one y-coordinate that if standing there, a positive number of enemy ships will be destroyed (technically, every enemy ship from both sides would be destroyed). You can handle this case exclusively — the answer will always be n + m. Thanks AeonHQ for pointing that out (in his reply below). ;)

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

      Actually your solution works at least O(n2 * m2), because you iterate 2 times over all pairs of intersections. And moreover, it will fail on test 1 1 1 1

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

Hey,can a knight in problem B kill a knight with the same power? 3 2 1 2 2 2 2 2 This test i test on my friend and he got ac while i got wa,wtf?

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

Problem B clearly says "Determine if you can with certainty deduce the common number, or if you can determine with certainty that both participants know the number but you do not", although you actually have to determine that number if you can, not just determine if you can do this.

Coordinators and authors, please, I think it's very important to formulate question correctly, what the hell. Never saw this on CF before.

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

    That's one small thing that I think really made me believe I was supposed to print either -1, 0, or 1. Although I can't complain for not carefully reading the output section, the statement definitely could have been clearer.

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

      I actually never read the output section carefully — I have samples for that. That never failed me before.

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

        Yep, I inferred everything from the samples too. They really covered all three possible scenarios (well, according to the misleading problem statement).

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

    This is maybe the hardest thing to do for an author. I know myself how hard it is to avoid words like that. That being said, of course they should try to watch out for that and it is a bad thing.

    My advice is to read the output section anyway and not care much about wording like "you want to find this" in the middle of the statement. Authors often describe the story and only at the end they say what they really want.

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

      I understand that it's hard for the author, I know this myself too and I don't have much complains to him. But there is more than one persons who prepare the contest, they should check things like that. And, yeah, for me it's lessons learned.

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

        It's easy to check if there is a max test for example, or to remember to stress test the intended solution with slower ones. It's harder to watch out for things like this in the statement because it's vague.

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

          Don't agree. They have testers and people who just read their problems and check tests\solution stuff. I'm sure some of them misunderstood statement after reading it, some maybe understood it after a while by themselves, some maybe experienced WA trying to solve it, some maybe understood it after reading authors tests. It's just important to not ignore this, but to tell author: "Your statement is unclear fsr". Maybe I'm wrong because I never prepared CF round by myself, but that's how I see it.

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

            Why are you sure about this? There is some small chance to understand the statement in a wrong way and it's perfectly possible (maybe even likely) that ~5 people that test it understood it correctly.

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

IMHO Div1E is more about having prewritten FFT code rather than good idea

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

how to solve div2B?

UPD: Got mistake, used set instead of multiset.

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

My head started to spin after reading Div2D. What was that! :O

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

I don't like this round.

E is obviously FFT. B + C = 2000 score, E = 2250. If I have templates, I can solve easy ABC, and E, and get good rank. Unfortunately I don't have it so I wasted a lot of time to write by myself.

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

    I don't like,too. I use int to print ans (void write(int x)),so it failed system test 43. It make me have low rating.I think it's unfair.

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

    Why there aren't large ans in pretests?

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

    I do not agree that having templates make problems B and C easy

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

      I wasted time to solve E. It's quite easy to know get an AC with a FFT templates. I want get the AC. Unfortunately I didn't. I should spend my whole time on ABCD, not only on fft.

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

Div2B is so difficult for Div2B =(

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

    Swapping div2B and div2C might have been better. div2 C was pretty straightforward given that you know basics of axis rotation. Moreover, B was a bit more Data structure or rather STL intensive.

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

Who else got WA for DIV2 B on testcase 54?

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

    Instead of set I resubmitted using multiset and it got accepted :'( Just difference of "multi" lead to WA.

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

When you forget to remove % mod from your FFT implementation :/

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

80% of the submission of div2 C are Wrong answers !?

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

When you get AC in E with runtime of 1996ms

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

One hell of system testing, Seeing such dynamics in system testing after a long time.

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

For Div2C the maximum area of the square is 200*200 = 40000

You can try all points from the first square and check if a point is on the second square the "YES".

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

So many Div2 guys with only 2 problems accepted out of 5 with pretests passed. Pretests sucked this round :(.

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

The weakest pertests ever...

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

Systests failed for Div2B because I forgot to add the case for k=0. Could have turned Expert today. Life is not going good.

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

What is so magical about test 78 in Div2-E?

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

Why does this code give WA on pretest 6 for Div2 B? my solution

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

Editorial link redirects to this blog itself, please update it itsNear

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

The link for the editorial is not working.

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

How can this solution pass for div2b as I am iterating over all the powers greater than current power, so looks like N^2 to me.

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

    You break the loop if cnt[it->ss] < k and you increment cnt[it->ss] in each iteration, so you make at most k iterations for each knight. The complexity is O(n*k), but remember that k <= 10. That's why you got AC :)

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

My solution for Div.1D failed on test #11 because the answer is not rounded up. I don't see the point of not including such a test in the pretests or even in the samples, it's just about the format!

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

    I felt the aim of it was to solve the problem using longs instead of doubles.Anyways it was also unclear to me, I had to ask a clarification.

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

Could anyone explain more about the solution of Div2B? (I read the editorial, but still can't grasp the underlying algorithm.) My solution gets TLE for test #52.

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

    Now I think I understand the algorithm that the editorial describes. The central idea is to begin with the weakest knight and iteratively add coins the current knight has, to the list if it has more money than the least element of the list and keep at most K-elements. I used priority_queue for the purpose of keeping K elements.

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

    Maybe the problem is that you sorting the knights on the number of coins. The test 52 can be specific for your algorithm, like this:

    9 1
    1 2 3 4 5 6 7 8 9
    1 2 3 4 5 6 7 8 9
    
    The same:
    9 1
    9 8 7 6 5 4 3 2 1
    9 8 7 6 5 4 3 2 1
    

    k = 1, for each of 100000 knights you are looking to the first knight with less power. And you are going from the very beginning. So it's too long.(near 10^10 / 2).

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

      Thank you for your detailed analysis. In the worst case like ones you pointed out, O(N^2) computation is required. I see.

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

Div. 2 B has all pretests have the knights' power sorted except test 1.

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

was not interisting 0..

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

What was the point and use of this line in D div2?
if there is a pair (1,2), there will be no pair (2,1) within the same set

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

Tasks like div1B are definitely not my thing, but at least I'm happy that there was no stuff like "Print -2 if you don't know the number and participants don't know the number, but participants will know the number once you tell them that you don't know the number".

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

    Hold your horses. This is an actual problem statement:

    • Two players are given numbers in the form a - 3 - b - 3 - (b + c + 1) by a GM. Each player only knows his own a, b, c and that their numbers aren't equal.
    • Player 1 says: "Cool. But I don't know if my number is larger than yours."
    • Player 2 says: "Neither do I."
    • Player 1 says: "Neither do I."
    • Player 2 says: "Neither do I."
    • The GM says: "You can keep saying that forever, neither of you can find out which number is larger."
    • Player 1 says: "That's an interesting piece of information, but I still don't know which number is larger."
    • Player 2 says: "Neither do I."
    • Player 1 says: "Neither do I."
    • The GM says: "Again, you can keep saying that forever and neither of you can find out which number is larger."
    • Player 1 says: "Well, I still don't know."
    • Player 2 says: "Neither do I."
    • Player 1 says: "Neither do I."
    • Player 2 says: "Neither do I."
    • The GM says: "We can even keep having the conversation we've just had forever, with me telling you that you can't determine which number is larger from time to time, and you still won't find that out. Actually, I could repeat saying this sentence I just said even a thousand times (at appropriate times) and it would still be true."
    • Player 1 says: "That's really awesome. I still don't know."
    • Player 2 says: "Neither do I."
    • The GM says: "And it still doesn't matter how many times you tell this to each other, you still won't know which number is larger. Not even if I told you this sentence I just said 2017 times, you still wouldn't know."
    • Player 1 says: "Interesting. But I still don't know which number is larger."
    • Player 2 says: "Neither do I."
    • Player 1 says: "Neither do I."
    • Player 2 says: "Neither do I."
    • Player 1 says: "Ha! Now I know which number is larger!"

    (The task is to determine all possible values of player 1's number.)

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

      This is hilarious, who made this problem XD

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

      Is this an actual solvable problem or something you made up specifically for this post? If first option then what are precise conditions on a,b,c?

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

        Actually used in a competition, then in another competition. And it's solvable.

        It's not even that hard, the worst part is comprehending what's going on in the problem statement. a, b, c are positive integers.

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

I declared two arrays like this in the WA code : int a[n], b[n];//n was taken as input before

And changing it to this I got AC : int a[n], b[k];

I got AC here : 39321053 but WA here(on system test) : 39293460

Can anyone please tell me the reason behind this error...? thanks!

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

I got WA on test 37 for Div 1 B and its test data looks like this: Input: 4 7 9 2 4 1 2 3 2 7 6 1 5 4 7 5 6 3 1 5 8 1 1 4 Output: -1 but if the first player get (2,3) and the second player (3,6) then they should know the answer while we don't know the answer, so we should output 0?

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

    you must print -1 if, for any of the first participant pairs, there are two o more distinct pairs of the other guy that share the same repeated element, because the first participant would not know which one is the other guy's pair (remember you should check the same condition for the second participant pairs).

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

Since there were some people with TLE at E, I decided to share with you a method of writing a good FFT (works even for people who don't even know what FFT is):

  1. Open Codeforces

  2. Find a recent contest in which tourist has participated, 485 (Avito for NTT) fits this criterium.

  3. Copy his namespace

  4. Be happy

Let's practice this method from on so that the problems won't get super-ultra-mega (div 1 E!!!!) complicated because they use FFT.

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

    Nice method, but you shouldn't use foreigh code without author's permission. :)

    But, of course, it's some FFT realizations under public domain anyway.

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

Your text to link here... above is my code for question- Your text to link here...

can someone say what is wrong in it, i was unable to get it?

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

    You have ignored the fact the coins array can have multiple instances of the same element. To be specific,

    if(s.size()>k){
    sum-=(*top);
    s.erase(top);
    }
    

    Lets take the coins array in the test case 10 8 4 8 4 5 9. It goes fine till 10 8 4. When the second 8 is inserted, set.size() does not increase greater than k=2, but this 8 is added to sum.

»
4 месяца назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Final contenders for major upsets in the 21st century:

  1. Donald Trump becomes the 45th president of USA
  2. Test case 54 Div2 B
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Horrible problems :'(

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

I solved E by using divide and conquer and FFT that is O(nlog^2). FFT solution : http://codeforces.com/contest/993/submission/39324259. And I get TLE by using NTT instead of FFT. NTT solution(TLE) : http://codeforces.com/contest/993/submission/39317762. Can only body explain why there are so much difference between these two solutions?

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

Someone please explain solution for Div2 C

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

    Read the editorial please

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

    I have a cheater solution for that: because all vertices are integer points, the intersection of our two squares will contain an integer point if it is nonempty. Therefore, we can simply check if any of integer points in (-100,-100)..(100,100) lies inside both squares using areas (P is in ABCD iff S(ABCD) = S(ABP) + S(BCP) + S(CDP) + S(DAP), and an area of triangle can be calculated via Heron's formula).

    Take a look at my code if you want to

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

      Hi, thanks for the approach, After considering that there must be a integral point common to both the squares,I tried for each -100<=i<=100 and -100<=j<=100 and checked whether (i,j) is inside both of them by putting the point in the equation of lines of the sides of square, but I am getting WA on test 42. Can you spot the mistake in this approach of checking the existence of common point?

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

        TMHMR, testcase #42 is a corner case when squares intersect at only one corner point. I think that you check if the integer point is strictly between two sides of each square. You should also consider cases when it lies on one of the sides.

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

          Yeah I got it, I had done a very silly mistake while calculating correct coordinates bounds. Thanks

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

      It is enough to check only 5 points from each Square, The 4 corners and the center, this will handle all cases , Thus we can solve it with this algorithm for larger x and y. Here is my code :) http://codeforces.com/contest/994/submission/39318762

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

        ofc we can, but this is a solution from the tutorial. I wanted to share another approach.

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

My submission http://codeforces.com/contest/994/submission/39327746 is wrong on test case #93 on codeforces, but it is correct when I run it on my PC and on ideone. https://ideone.com/ksKfLZ

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

Your crafting.oj.uz ratings are updated! (Sorry for the late update, we were waiting until the round was declared rated :p)

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

Geometryforces Round #488 (Div. 2)