Блог пользователя i.e

Автор i.e, 4 года назад, По-русски

Мы с blyat рады пригласить вас на Codeforces Round 669 (Div. 2), который пройдет в 08.09.2020 17:35 (Московское время). Он будет рейтинговым для всех участников, чей рейтинг ниже 2100.

Задачи были придуманы и подготовлены blyat и i.e. Мы хотим поблагодарить всех, кто оказался причастен к этому раунду:

У вас будет 2 часа на решение 5 задач, одна из которых будет интерактивной. Вы можете ознакомиться с руководством по интерактивным задачам здесь.

Отдельное спасибо хочется сказать моему замечательному минипигу Швайне, который вдохновлял нас в течение всего времени подготовки задач.

хрю

Разбалловка будет ближе к началу контеста.

UPD1: В условиях не будет картинок с минипигом. :)

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

UPD3: РаЗбОр

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

Div1 + Div2:

  1. ksun48

  2. WZYYN

  3. tribute_to_Ukraine_2022

  4. neal

  5. jiangly

Div2:

  1. Hoxilo

  2. deep_fake

  3. GiannisAttemptafreethrow

  4. watemus

  5. wasureta

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

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

Автокомментарий: текст был обновлен пользователем i.e (предыдущая версия, новая версия, сравнить).

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

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

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

As a tester I would say that, the contest is really well prepared and the questions are awesome.

antontrygubO_o orz.

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

Why is LordVoldebug mentioned as a tester twice?

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

i have a night now i scared about picture))))) thanks)

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

My EYES, My EYES !!!

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

Why is Putin2024 a tag?

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

Why is Putin2024 a tag?

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

No such pics in problem statements plz

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

To be honest, I was scared by the minipig Schweine when I opened the website. Will he be the hero of the problems? I'm looking forward to it(I love interesting background)!

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

what a terrible day to have eyes.

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

istg if you look straight into the eyes of the amazing minipig Schweine you'll have goosebumps.

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

I peed myself looking at that

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

Можно эту свинью вставлять вместо скримеров, такой ужас

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

    сам свинья это минипиг сказали же что за неуважение.....

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

Is this pig the protagonist of the stories in the oncoming round?

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

Please don't put a picture of the minipig in every problem statement.

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

I hope we don't have a picture of the minipig in every problem statement.

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

My new sleep paralysis demon Boy-scared-of-man-in-door.jpg

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

Opening the site and this minipig is the first thing that comes out to eyes lol. Really looking forward to see him as the theme hero if turns to be so!

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

That picture is terrifying,please no such pictures in problem statements.

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

Can you please put your amazing minipig under the spoiler?

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

Why people are being dumb and stupid, and overreacting to the picture??

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

Good ideas of problems you've prepared! Each is worth tasting.

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

A very cute pig =))

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

Get a good night's sleep after look the amazing minipig #_# 1h a.m here

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

Can someone please explain to me why my friend who had rating 1479 before contest got +37 after achieving 3025 rank, and I only got +10 since I had lower rating (1470) than him, and got higher rank than him(2744). This thing is not letting me sleep. Please respond if anyone knows about this ??

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

    Maybe, this post can help you.

    If your friend new on codeforces, then his principle of rate-counting may vary with your for some rounds.

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

    That because the predictor not computes your result right away. 2 minutes per time may be.

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

      I don't understand. Can you please explain?

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

        There is an extension for browsers called cf predictor. It is useful to know your approximate rating change before the actual rating change. NeiH thought that you're talking about its results.

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

          But still I didn't get why I have less rating change then my friend?

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

            I think it is only because it is his 5th contest. Same happened to me and my senior (although on Atcoder). If both of y'all had 15+ contests then i'm pretty sure he'd get a lower delta than you.

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

MikeMirzayanov I think this pic is too much...

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

i.e's comeback after their drop to specialist is my motivation.

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

Can somebody tell me what is an interactive problem?

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

    those problems in which the code interacts with the in real time. When we develop a solution for an Interactive Problem then the input data given to our solution may not be predetermined but is built for that problem specifically. The solution performs a series of exchange of data with the judge and at the end of the conversation the judge decides whether our solution was correct or not.

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

    You may look here............
    This link was in announcement section....

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

Is number of user increases or the people uses multiple account ??

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

I was going to participate in the contest, but now I've seen that pig I'll better lock myself in my bathroom

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

It will be another nice interactive problem :))

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

Thanks for Reference of how to deal with interactive problem

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

    to learn more about interactive problem see the question of long contest in codechef that always have 1 interactive problem.

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

We want to know.

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

.

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

scary pig

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

As a minipig, give me contribution

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

the contest is really well prepared and the questions are awesome. :)

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

The pig makes me want to skip the contest...

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

Good luck!

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

![ ](b02acad31d9104ae6c2b82f4478eb7a9741ba34b.jpg)

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

as coautor and creator of deleted offensive meme I want dislikes and harassment charges on twitter

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

"UPD1: There will be no pictures of minipig in the statements. :)"

So sad. I think I'll have to skip the round then.

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

I hope I would become expert in this contest :)!!

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

That pig looks hideous.

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

This picture is so scary!

I was so scared!!

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

MikeMirzayanov This is too much.Please delete this pic.

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

Sorry for off-topic but why hasn't ratings for the last round been rendered back again yet?
PS: Ratings are back now

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

No scary pic in problem statements plz.ToT

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

Why is this picture here??

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

i fear the demons that possess the problemsetters.

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

This pig is causing PTSD.

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

The picture should be removed imo. Maybe it's some kind of meme and maybe it's funny for some people, but I don't get the picture of the pig. I might be overreacting, but it's extremely disturbing to have to see it every time I scroll through codeforces home page. After all, this isn't creepypasta.

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

I was not sure about registering for the contest but after the pig appearing in my dreams for two days straight I am glad to say I'll be losing my score today :/

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

Thanks for putting the pig picture in Spoiler, that's so much better!

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

Oh, thanks for delete the pic.

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

You should have also added, "Resemblance to any living or dead person is purely coincidental." Unless I am mistaken in identifying.

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

 

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

I hope interactive problem will be nice :) and good luck everyone for the contest.

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

After so many ups and downs i am hoping that my rating increases. :(

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

I made the mistake of clicking on the spoiler 10 mins before the contest. Now, I just have to hope that it won't haunt me during the contest :/

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

First problem is literally laughing at me

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

Is it just me who is feeling the questions to be more difficult than usual?

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

When I start practising 1500 rated problems then I'm unable to A,B problems in contests, When I practice A,B level problems then I'm unable to do 1500 or more rated problems. Any solution anyone? :/

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

Unclear question 1407B - Big Vova , I couldn't understand what lexicographically maximal is.

In the clarification, it says "a is a prefix of b, but a≠b" I don't know when a is called a prefix of b. It would be great if Authors could give example to make things clear. Long and unclear question.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    4 3 1 is lexicographically maximal than 4 2 1..
    If have a way to make c array 4 3 1 then we don't try to make c array > 4 2 1 ..so answer(b array) will be will result which made the c array 4 3 1..
    
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is D DP?

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

Even if solution of A is $$$O(n)$$$ why constrain is so low?

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

I love so much when I understand the exact task just 5 min before the end

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

How to do problem C?

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

    Keep the index that corresponds to the highest value among the numbers you looked upto now. Send two queries "? i biggestIdx" and "? biggestIdx i". If the result of first query is smaller than the second, you should update the biggestIdx and before doing that you should update A(biggestIdx) with the result of second query. Otherwise, update A(i) with the result of first query. Finally, you know that A(biggestIdx) is equal to N.

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

    if a % b > b % a, then a % b equals a, otherwise b % a equals b. it also tells you which one is bigger. any time you ask you save the one you got and compare the next you don't know with the one you are left. so you can do this n — 1 times, the position you are left corresponds to the number n.

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

    if you pick two distinct numbers a and b, and ask a mod b and b mod a,you can find the smaller of the two numbers.keep repeating this until you find n-1 numbers and the final unknown value would be n;

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

      Why only N will be the remaining value?

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

        because you always find the smaller number when you compare both the mods,and N is the largest number in the permutation.

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

          Ohhhh... Nice observation... I got all the idea but was not able to observe that N would be the last remaining number.... Did a O(N) loop to find out :)

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

Similar problem to today's problem E: https://dmoj.ca/problem/ioi11p4

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

Should have not attempted this contest....Bad Day :(

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

Personally this is the hardest contest I ever had.

Can some one tell how to solve A and B after the contest?

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

    For A if the number of zeroes is >=n/2 then just type out n/2 zeroes.Otherwise it means that the number of 1 is greater by at least 2 than the number of zeroes so you write out n/2 ones or n/2+1 ones depending which of those is divisible by 2.

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

Problem A is very nice for its position. Well done.

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

    If constrain for n were of order $$$10^{5}$$$ then would be more nicer.

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

    i smell the sarcasm here and totally agree

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

      I guess sarcasm is hard to convey in a comment. A is truly one of the better problems I've seen at its position because I had to think for more than 15 seconds to solve it.

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

Smn plz check my solution on B https://codeforces.me/contest/1407/submission/92280369 I don't know why it fails on the second pretest

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

The interactive one was nice...

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

Nice Problems

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

Problem A killed me, 3 WA and 22 minutes to get it passed. It was my mistake thought :\

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

Someone has hints for D?

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

    There are only $$$O(N)$$$ possible transitions, find them by placing building in increasing/decreasing order then the DP/BFS is trivial.

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

      Shouldn't there be C(n,2) transition while it's only possible to move forward?

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

        No, place the buildings in increasing order and consider the closest building to the left and to the right. It can be proven that every transition will be found by this constructive algorithm. So there are clearly at most $$$4N$$$ transitions.

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

        If you have for example 4 2 2 2 2 4 4 4 4 4 4 4 2 it is faster if you move backwards, you can reach the end in 3 steps.

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

          No, as much as I have understood the problem for an input like 4 4 4 4 the answer must be 3. You can only jump between i & j if and only if the middle elements are strictly greater or smaller.

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

    I kept two stacks where one of them shows the indices of increasing sequence and the other showing decreasing sequence. Then, made binary searches over these stacks and used Segment Tree to get best option among them. However, I got WA at the 5th case and I don't know why...

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

    I used two monotonic stacks to record the indices of increasing sequence and the indices of decreasing sequence, respectively. Iterate height from n-1 to 0.

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

    See this

    For DP in O(N) with increasing — decreasing sequences.

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

problem A is too hard

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

Anyone willing to help my submission for div2 qns C. Did the flush and follow query format but still cant pass. Thanks

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

    I think you messed up with indices when assigning arr[idx1] = smth. That should be arr[idx1-1] right??

    Idk but that's what ig is wrong as I hv the same soln in C++.

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

Hmm.. Now, I'm interested to know how Mr. Kinky Pig inspired this conspira- um.. contest.

Nice problemset btw.

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

Round gave me PTSD.

Took 36 minutes for A, 8 minutes for B. Life's weird.

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

    kinda same with me, 28 mins for A and 11 minutes for B.

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

    Story of this contest:

    • Spent an hour in A, didn't solve with a couple of wrongs.
    • Went to B.. Got a way to solve it in ~10 minutes but WA because of simple small mistake (literally had to change position of variable declaration) but ofcourse I panic-ed and went back to A leaving B for a bit.
    • More 20 minutes on A.
    • Jumped back to B, immediately realized the small mistake and boom AC.
    • Remaining time of contest in A with no luck..
    • Contest ends so I look at submissions of A and realizes I don't need an even sized array as output.......
    • Facepalms and laughs.
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Has anyone solved D with $$$O(n * log(n) ^ {2})$$$ solution. I got TLE.

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

    Can you tell me your idea. I tried to solve using binary search and segment tree, my solution complexity is also $$$O(n*log(n)^2)$$$ but got not getting correct answer.

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

      Actually I thought like $$$dp[i]$$$ is the minimum steps required to reach $$$ith$$$ index. Now there are cases if $$$h[i] > h[i - 1]$$$, $$$h[i] < h[i - 1]$$$, or $$$h[i] = h[i - 1]$$$.
      $$$ Let$$$ $$$dp[i] = 1 + dp[i - 1]$$$
      if $$$h[i] = h[i - 1]$$$, then do nothing
      $$$if(h[i] > h[i - 1])$$$ then, find the first index $$$i$$$, let's say $$$j$$$ such that $$$h[j] >= h[i]$$$, and also find index $$$k < j$$$, such that $$$h[k] < h[j]$$$.
      $$$if(h[j] == h[i])$$$ then $$$dp[i] = min(dp[i], 1 + dp[j])$$$
      $$$else$$$ $$$dp[i] = min(dp[i], 1 + min(dp[k + 1], dp[k + 2], ..., dp[j]))$$$
      similary handle for $$$h[i] < h[i - 1]$$$.
      I think this is correct but IDK why I got TLE.

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

Is it just me or the implementation for Problem B was very hard?

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

https://www.youtube.com/playlist?list=PLBqHLq3IFiRLBB96TUEoxBvP80s73uSPo

Do visit the editorials of all the problems given .

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

I'm really sad I got C solution idea but couldn't code it in time :(

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

A is cool, but cursed

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

Pupil to Specialist...Great Contest.

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

https://www.youtube.com/channel/UCBStHvqSDEF751f0CWd3-Pg/

Subscribe to this channel for all editorial videos .

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

Missed that the length of the array is even in A, wasted 30 mins. Maybe authors should bold important info in the question itself rather than in the constraints section.

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

Am I the only one who thought problem A required an output of even size... My mistake ofc but just wanna know if I'm the only dumb here lol....

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

Today's div2A problem was the most perfect div2A problem I have ever seen in any CF div2 round.

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

My rating after me solving A after fourth attempt:

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

    You are not alone, for betterment of my mental health and physical safety of my laptop i headed out of the room after first WA.

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

In today problem C I have submitted O(n) solution in pypy3 it got TLE in tc 6 . Again I have submitted almost same solution and got an AC in 997 ms . I have seen most of the pypy3 codes getting execution time above 900 ms .
But then I have coded it in c++ as it may get TLE again in the systests and got AC in around 300 ms. This is not only today that I have faced this kind of problem , I generally switch to C++ in case of any problem involving recursion . But how may I know that an O(n) can also get TLE .
So to all the respected problem setters please check if the python solution is accepted with a considerable margin or just increase the time limit.

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

    The issue with python is that it never take a fixed amount of time for running a piece of code, running the same code multiple time can sometimes yield different results. This is not just on codeforces but many other platforms also faces criticism for uneven time limits of python but you see its really not in their hands because increasing time limit can make unintended brute force solutions pass the system tests. You can correct me if I'm wrong.

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

      I am not blaming them . I just want to say they should check if the python solution is getting accepted with a considerable margin . If not they can just increase the time limit by some milisecond . 1 to 1.5 or something like that.

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

    They clearly can set TL by language which they dont

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

    Problem with python programmers (who do CP) is they only know how to whine about time limit. First of all, you use not the best tool for a task(python instead of c++/java) then you complain about things not being same for you, like WHAT?

    Also there are many high rated python coders, so clearly things haven't really been unfair, you just don't know python enough for CP. Either learn python more indepth, understand all intricate and subtle things about it then use it for CP (you won't need to complain then) OR use a more appropriate tool(C++/Java/Rust/..)

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

    I agree with you that this interactive had kind of a tight time limit.

    It is possible to pass just using the default PyPy IO 92228274 (951 ms), but the TL is tight. Important to note is that the built in IO in PyPy is far slower than CPython IO. The same code in CPython runs in 655 ms 92292022. The work around for PyPy is to use a drop-in fast IO template 92308464 (670 ms).

    About your code 92261279, there are two ways you could improve it.

    1. Don't import a crap ton of stuff that you don't need/use. Your unused imports at the top take like 150 ms in PyPy3. Also by doing from math import * you are overwriting the very useful built in pow function.

    2. You can make use of fast IO templates like this to greatly speed up the IO in PyPy.

    With both of these improvements your TLE code runs in 748 ms in PyPy 92307825.

    As a final remark, it is possible to get below 300 ms even in PyPy 92288195.

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

Edit: case was wrong nvm

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

In question A div 2 We can not remove consecutive elements so for case 4 1 1 0 0 Why answer's (1 1) and (0 0) are getting passed , Since in both cases consecutive elements are getting removed.

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

    Statement says "The elements that you remove don't have to be consecutive."

    They might or might not.

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

This was my first interactive problem which i had tried and got wa only for using long long variable..Is there any restriction about using long long at interactive problem???

Sorry i don't know about that matter.

Thank you kindly for any good response. @realhype

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

Who could tell me the correct algorithm to solve Problem.D ? Thanks!

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

What to do if one dosen't get the logic, like me in problem A.?

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

    Skip the problem.Do the others and comeback.Each person can probably solve questions upto slightly above their rating. By that logic I usually try up until D, many a times skipping questions I didn’t get in 10 min.Today is a good example. Didn’t get A in 10 min, so skipped it, did B and C, came back to it, it worked out.

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

In div2C, I got system test failed, submitted in C++17 and now even sample test is not passing for that solution(if it was shown during contest, I could have tried to correct it). While when I submitted the same code after contest in C++11, it got Accepted. Why is this weird behaviour? i.e, blyat

Link for WA(C++17)

Link for AC(C++11)

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

I don't know good or bad but why was Problem A laughing at me :sob:.

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

Good problems on math.

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

Bye, my rating..Even if we know each other for less than a day, I still miss you from time to time.。

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

Hello everyone,

I received a strange runtime error on TC 10 in today's Problem B — "Big Vova" in pypy2.

Here's the link to simplified code, 92298672

But after adding a useless line to the solution it got accepted. Which was:

if pos == -1:
     print(1/0)

Link to the accepted solution, 92298831

If you read my code, the above snippet never gets executed according to my logic.

I am confused if this is pypy2 fault or cf. There were few other python submissions that had the same problem like this one for example 92244789. If anyone of you knows what's happening please do let me know.

Link to my original submission during the contest 92248591

I would like i.e blyat to see the submissions. Thanks in advance!

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

So,when will move the cheater and change the rating?

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

can i get input and output files for q1 and q2 because i am not able to find my logic anywhere wrong for q1 and in q2 when i checked for wa for input2 it is showing same same as answer and also check my code for q1(https://codeforces.me/contest/1407/submission/92244915) and q2(https://codeforces.me/contest/1407/submission/92258924)

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

    In B(q2) you are sorting based on best gcd value with only the maximum element this won't work since we need gcd of all elements upto i for each value of ci.

    Instead you need to keep choosing the element that gives best gcd value with gcd(all chosen elements till now). And initially choose only the maximum element.

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

Question D. Discrete Centrifugal Jumps With explanation.

I hope my comments will help others to underastand the solution :)

// vrkorat211 - Vivek Korat

const int N = 3e5 + 5;
 
int n;
int a[N];
void GO()
{
    cin>>n;
    for (int i = 1; i <= n; ++i)
    {
        /* code */cin>>a[i];
    }
    std::vector<int> dp(n+1);
    stack<pair<int,int>> st1,st2;

    st1.push({a[1],1});
    st2.push({a[1],1});

    // dp[i] = minimum step to reach at index i with given two jump properties.
    // pair.second in stacks will store index of pushed element.
    // it will be used to access dp array.

    /**Algo.**/

    // st1 will keep elements with strictly decreasing order.
    // st2 will keep elements with strictly increasing order.

    // for both sequence, if the sequence is broken then pop some elements
    // to get sequence property(strictly increasing or strictly decreasing) back. 

    // when we pop element than one of the jump properties will be followed so update dp[i]
    // accordingly.

    /**\Algo.**/

    // Above comments may help to understand the code :)

    dp[1]=0;

    for (int i = 2; i <= n; ++i)
    {
        //one move always possibee from index (i-1) to index (i) in 1 step;
        dp[i] = dp[i-1] + 1;

        if(a[i] > a[i-1])//st1 property violates.
        {
            //pop untill strictly deacreasing property follows with current element
            while(!st1.empty() && st1.top().first < a[i])
            {
                st1.pop();

                if(!st1.empty())
                {
                    //a[i] and top element follows jump property.
                    //update dp[i]
                    dp[i] = min(dp[i],dp[st1.top().second]+1);
                }
            }
        }
        else if(a[i] < a[i-1]) //st2 property violates.
        {
            //pop untill strictly increasing property follows with current element
            while(!st2.empty() && st2.top().first > a[i])
            {
                st2.pop();
                if(!st2.empty())
                {
                    //a[i] and top element follows jump property.
                    //update dp[i]
                    dp[i]=min(dp[i],dp[st2.top().second]+1);
                }
            }
        }

        // remove top equal elements from both stacks.
        // Because they violates sequence property of both stacks.
        while(!st1.empty() && st1.top().first == a[i])st1.pop();
        while(!st2.empty() && st2.top().first == a[i])st2.pop();

        // Now current element is in proper sequence for both stacks.
        // So push it in both stacks.
        st1.push({a[i],i});
        st2.push({a[i],i});
    }

    //finally d[n] is minimum step to reach at index n.
    cout<<dp[n]<<endl;
}

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

Why I was the last but still give me points?

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

    This is caused by the way new accounts have a "special" calculation of rating. After like 5th contest that effect should be negligible.

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

in problem D what is the problem if I get the minimum of going to {current index + 1, the first number bigger than me, the first number lower than me, the biggest number less than me, the lowest number bigger than me} using dynamic programming???? my code

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

92240790 1407A - Ahahahahahahahaha I did pretty much what the question asked for. Coded the brute force approach, but I cant seem to find where I am going wrong ?

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

    What is the idea of that code?

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

      to calculate sum of odd positions and even positions. then checking whether oddSum — evenSum is > 0 or < 0 or == 0. then accordingly removing 1s from either the odd positions or even positions or removing nothing (== 0 case).

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

        If you remove an element, the remaining elements switch group. Previously, all those that are odd indexed after that element become even indexed and vice versa.

        Hence it is easier to just keep all the same digits (either all 1's or all 0's).

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

          oh okay thanks!

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

            There is another simple strategy: We can group the input in groups of 3 elements.

            In such a group there is allways either at least two 1 or two 0. So we output foreach such group "11" or "00".

            The case that length of input==2 must be handled separate.

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

thanks for nice contest :)

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

I really enjoyed Problem D, thanks!

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

Such a nice D and E. Wow.