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

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

Привет, Codeforces!

27 января 2015 года в 19:30 MSK состоится очередной раунд Codeforces #288 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

Это мой первый, но, уверяю вас, не последний Codeforces раунд. Надеюсь, что все пройдет хорошо, и он вам понравится.

Хотелось бы сказать большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon и за идеи некоторых задач, а также моим дорогим однокомандникам Артуру Свечникову (ikar) и Илье Лось (IlyaLos) за прорешивание задач. Илья, не обижайся, в следующем моем раунде обязательно будет задача про тебя.

Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.

UPD Разбалловка стандартная 500-1000-1500-2000-2500. Всем удачи!

UPD2 Соревнование завершено! Всем спасибо!

UPD3 Разбор вы можете найти здесь.

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

  1. topcoder.2015
  2. KimJongUn_JBYongDongJI
  3. atatomir
  4. pankaj_gudlani
  5. egor_bb
  • Проголосовать: нравится
  • +223
  • Проголосовать: не нравится

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

Preparing for the battle..

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

Preparing for the battle...

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

Good Luck to everyone :). I request all Div-1 Participants to participate Out of Competition. Hope I become Div-1 Coder after this Round :).

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

Two consecutive Div — 2 contest. It's really frustrating for Div — 1 participants.

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

I remember that I saw Round 288 div.1 && div.2 about 5 days ago. But now there exist only div.2...Could I ask the reason why the div.1 is cancelled? Is it because the problems for div.1 are not prepared?

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

Div.1 users dont create new accounts please.

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

    I think that problem is separate rooms for div 1 users.Many of them want fun,hacking,and best place in their rooms. If that changes,contests would be more regular.

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

gl & hf )) PS: Good luck and have fun) PSS: I have 4 houres before CF. It's about 5 games in Dota 2. GG :D

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

Although it's a Div.2 only contest, but still it will be a good start for me! I'm sure I'll enjoy the contest!

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

I hope this won't be dynamic scoring in this contest :|

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

cheaters don't cheat!!!!

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

Update about the scoring system well before contest.. That's unusual.. but nice .. Gl & Hf

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

let the game begin :)

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

5300+ participants. That's amazing)
UPD: 5400+ :D

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

700+ unrated participants. Funny, isn't it?

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

What Does standarT in last line Mean Exactly?

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

not to prepare contest is much better than have a contest with many mistakes;

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

Doublepost, please delete, codeforces comment system is a bit hard for me.

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

triplepost, please delete, codeforces comment system is a bit hard for me.

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

Suspicious?

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

dreamoon_love_AA just might reach his dream of first place in a codeforces round !

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

how to solve E

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

Как решать D?

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

    Рассмотрим граф, в котором вершины — это пары допустимых символов. Тогда каждая тройка — это дуга между вершинами. Ответ — эйлеров путь в таком графе.

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

    Я написал поиск Эйлерова пути по графу, у которого вершины — пары символов, а ребра из вершины "ab" в "bc" идут тогда, когда в инпуте есть "abc".

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

    Каждые соседние две буквы искомого слова — вершины графа, а каждая данная тройка — ребра. Нужно найти либо эйлеров цикл, либо эйлеров путь.

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

omg im turnin greeeeeeen!!!!! ;(

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

How to solve D?

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

    I have an idea that "ABC" is actually an edge between "AB" and "BC". What we need to do is to find an Eulerian trail of the induced directed graph.

    (Yeah, I failed in the second part)

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

    Let's look on the graph in which each vertex is a pair of symbols. Then for example abc = ab -> bc. The answer is the euler path in such graph.

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

    Imagine a graph with 52 * 52 nodes.

    Each node represents a string like this "ab".

    Then each sub string means edge in this graph. Find Euler path.

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

      even more digits are also allowed .. I have not noticed this thing and start coding and later realised that this solution is of no use now ..

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

        I did not noticed digits. It would be nice if they were bold :(.

        Thank you, for pointing out my bug during contest.

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

      62 * 62 nodes...

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

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

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

Can someone tell me what's wrong with my solution here? for problem E? I used an O(n^2) method, but I still get TLE .-.

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

how to solve D and E ..

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

B is gonna have so many System Testing wrong answers :3

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

Пожалуй, самый простой контест на моей памяти. Несмотря на это, задачи отличные!

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

    Проще, чем предыдущий?

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

      В предыдущем у меня было несколько неверных идей по D. Сейчас над задачами практически не думал — просто реализовывал. Долго и криво, правда — но это уже мои личные косяки >_<

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

    Настолько простой, что D отправило всего 57 человек :)

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

      И правда, не посмотрел! А мне D показалась легче, чем C... Субъективность, однако =)

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

        C D, полагаю, у всех были проблемы с реализацией, а сама идея то по своей сути очень простая. Я сам 30 минут писал код, в котором сейчас уже разобраться и объяснить почему так написано — не смогу, да он и не работает.

        По мне так самый простой контест вот: 280 раунд, хотя тут в задачах нужно было чуть больше подумать над идеей решения и отловить частные случаи

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

It was very fun contest :D

I wonder how can solve C...

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

    Hello mhkim4886

    C can be solved using this idea that the candles required at the ith second can be burnt at i-1 , i-2 ,,, and so on second .. but after burning these candles check once whether you have achieved required number of candles or not .

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

I don't understand why this code couldn't pass the first pretest case about problem D, I did Eulerian Cycle and I got the same output in every pretest case, but I got WA in pretest one :Ssss ><

http://ideone.com/1RfNzu

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

Кому нибудь удалось взломать решение по B, где прям явно свапали символы в строке и сравнивали строки? И возможно ли это вообще? Я решил сначала локально посмотреть, сколько это будет работать, и оказалось, что почему-то не тлится. Возможно, я тесты плохие делал:)

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

    Я таких 2 на TL взломал. тест: string(1e5 — 1, 2) + "1"

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

    Мне удалось взломать таких 3, и одного неудалось.

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

    Был массовик-затейник, который на каждой итерации при лексации брал максимум из двух строк. Взял на ТЛ его.

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

I don't understand why this code couldn't pass the first pretest case about problem D, I did Eulerian Cycle and I got the same output in every pretest case, but I got WA in pretest one :Ssss >< http://ideone.com/1RfNzu

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

I solved A but couldn't submit...

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

 My first hack in codeforces is unsuccessful :P

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

Gray has been my favorite color.....since I started here ^_Q

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

D was a very interesting problem; can someone give the algorithm?

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

Just for fun !

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

Thanks for realy funny contest, with string problems! :) . And thanks for weak pretests! In problem B I've found some too slow submissions in my room, so need to generate maxtest for these submissions.

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

pending system testing 10 minutes @@

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

I submitted C in the last minute and didn't even get time for checking my A. After reading the editorial I found out what a foolish thing I did with A just because I thought I had to solve 3 this time.

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

Прочитал Б 3 раза, узнал все о бурлях, но пропустил главное — что входное число точно нечетное.. Анаграмма смешная, но почему-то сильно отвлекает.

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

didn't ever seen a problem 0.5 second!!! time limit during any contest!!! why so strict time limit is it a problem with only one solution, and any other solution would fail?!

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

    i believe this was done to avoid bruteforce solutions that try to compare every possible swap and output the best one. When it also can be done greedily.

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

    didn't use anything but swap and time limit!!!!!!!????

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

      Your solution is O(N2) because of string comparison. Calm down.

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

      I tried the very same thing as you but I got TLE in pretest 10, so i resubmitted with a greedy approach. Trying to generate the solutions with swap on a string seems to be too slow.

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

        i think it's luck that my solution passed pretest 10 and didn't think about the greedy one xd

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

          It's not :) If it got wrong answer, you could think of another solution and accept the code for real this time. Of course, it's good for the hackers, though :)

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

    The only one solution is very very fast than other ways.

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

Thanks for setting awesome questions . Though few were ambiguous, I enjoyed participating in this contest

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

Is it unrated contest??!!! I am in place 700 and still gray... hooooow!

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

Кстати, а почему в последней задачи изменили ограничение по памяти?

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

http://cfa.yuldashev.net/contest/508

Humble reminder in case if you missed the post

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

Very strange: during the round I was hacked by kgbugy659. She solved all the problems and was on the 2nd place before the end. But now she's out of scoreboard, her submissions are not listed in the room o_O Furthermore, her last rated round (before today) is not included in the graph. Weird %)

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

It may sound stupid, or rude, but I would please all the Div.2 / Div. 1+2 setters to announce the winners. I mean, especially for Div.2 contestants, who, some of them will never reach top 5 in a Div.1, it really makes them happy to see their names on the round post, and I consider it to be a nice thing. However, one will do as he wants, it was just an advice. :)

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

Why doesn't stoi() work on CodeForces? (C++11)

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

Can someone explain to me what could be so special about test case #40 for problem A. I tried to hack this solution during the contest: http://codeforces.me/contest/508/submission/9582562. I expected that if I had some moves 1000 1000, it would lead to RTE (as it must throw a segmentation fault) . But, my hack was unsuccessful.

I tried this test case: 1000 1000 4 1000 1000 1000 999 999 1000 999 999

Why did it fail to produce a RTE veredict?

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

    Array out of bound errors on C++ is undefined behaviour. It's usually impossible to know what the program will do in these cases.

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

    This hack would work:

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

Dang! I didn't check the time limit on problem B. My bruteforce solution got TLE :( I'd better check the time limit on each problem next time.

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

I am sad that my C(with set-stl),got TLE,but I am happy I became blue :D. That was my first goal,now it is division 1. I say that just because,I want grey and green users to know,that with 'correct' practise we can do everything :D