Автор Dormi, 3 года назад, перевод, По-русски

Привет, Codeforces!

Присоединяйтесь к объединенному Div. 1 и Div. 2 раунду Codeforces LATOKEN Round 1 (Div. 1 + Div. 2), который будет проходить при поддержке LATOKEN и начнётся в 13.06.2021 18:35 (Московское время). Он будет рейтинговым и открытым для обоих дивизионов.

Все задачи были придуманы и подготовлены Aaeria, crackersamdjam, Dormi, Ninjaclasher, и Plasmatic при поддержке Codeforces, LATOKEN и Валентина Преображенского. Большое спасибо 300iq, arvindr9, crackersamdjam, Delmos, duality, coderz189, KAN, wxhtzdy, PurpleCrayon, kalki411, socho, wleung_bvg, Zeyu за тестирование раунда и отличные советы, а также MikeMirzayanov за системы Codeforces и Polygon.

Участникам будет предложено 8 задач и 3 часа на их решение. Пожалуйста, прочитайте условия всех задач. Всем успешного раунда и повышения в рейтинге!

Спасибо компании LATOKEN за подарки участникам! Призы для победителей:

  • 1 место = MacBook Air M1 + предложение работать в компании с получением акций
  • 2 место = Xiaomi Mi 11 + предложение работать в компании с получением акций
  • 3 место = Xiaomi Mi Notebook Pro 15" Enhanced Edition + предложение работать в компании с получением акций
  • 4-10 место = Предложение работать в компании с получением акций + Merchandise Pack
  • 11-55 = Merchandise Pack

Случайные 10 участников(из тех, для кого этот раунд будет не первым рейтинговым соревнованием Codeforces!, не вошедшие в топ-55, но решившие хотя бы одну задачу, получат фирменные футболки.

Несколько слов от команды LATOKEN:

Приветствуем Вас сегодня на Битве Сильнейших! LATOKEN — компания, которая стремится сделать криптовалюту более доступной чем социальные сети. Мы стремимся всегда брать лучших в команду и это видно по результатам компании: мы входим в топ 15 лучших криптобирж по версии Coingecko, у нас более 600 000 установок приложения за первый год его запуска, число пользователей — превысило миллион. Новая финансовая система, которая строится благодаря блокчейну, более перспективна, ведь криптовалюта, по-настоящему глобальна и мало зависит от государственных центральных банков.

Если ты чувствуешь, что достоин стать частью чего-то большего, удаленно работать со специалистами со всего мира и готов менять этот мир вокруг себя — пообщайся с рекрутерами и интернациональной командой LATOKEN. Напиши боту или заполни короткую анкету и расскажи о себе:

Bot→
Contact Form →

UPD: Разбалловка: 500 — 1000 — 1250 — 1500 — 2250 — (1750 — 1250) — 3250 — 3500.

UPD: Разбор.

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

  1. Benq
  2. tourist
  3. Radewoosh
  4. Endagorion
  5. ecnerwala
  6. heno239
  7. VivaciousAubergine
  8. gamegame
  9. Pyqe
  10. maroonrk
  • Проголосовать: нравится
  • +638
  • Проголосовать: не нравится

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

Do the contest or TLE real life

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

As a tester, the problems are great, as always. I hope you enjoy one of the first Canadian rounds!

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

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

Mandatory "tourist, What will you do with your MacBook Air M1?" comment.

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

I was just wondering why 1st-3rd placed participants are not being offered the job while 4th-10th are XD.

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

He is Valentin Preobrazhenskiy not Valentine.

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +17 Проголосовать: не нравится
"Random 10 participants outside of top-55, who solved at least one problem and participated in rated Codeforces rounds before, will get a t-shirt!"

Am I going to be the one of those 10 ? rounding up number of people solving atleast 1 problem to 20000 as we have 3 hours given probaility is ( 1/(20000)), . It comes out to be (0.00005)

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

    Well almost, you need to multiply 0.00005 by 10, because "Random 10 participants outside of top-55...". So that's 0.00005*10 = 0.0005. But I don't think it changes anything)

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

be annoy of the suck statement at last several round.

statements are short look forward to this round.

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

Unfortunately, the start time is 11.35 PM in my area :(

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

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

As a tester I must say the problems are nice and interesting. May you all get a positive delta.

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

If you forgot to see the prizes section of the post.

Do visit again!

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

very weird time :|

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

Just switched from Instagram to Codeforces, a few days back, and trust me Codeforces is much better.

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

note the unusual start time

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

4th-10th place = *Job offering* and Stock Options + Merchandise Pack

I want this level of confidence in my life.

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

I will sleep during the round.

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

Codeforces is the best ❤️

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

Is it rated?

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

Sorry I'm getting back to CF after many years and now I see there is also a Div3. Will this round also be rated for Div3 folks?

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

    Yes, there is pretty much no div3 as such. Anyone who's a div3 is also a valid div2

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

    As now there's also a Div4 you're Div4. But all contests of higher divisions than your division are rated for you. Unless round has separate contests for separate divisions. Because then you can only participate in your division contest.

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

Just switched from Instagram to Codeforces, a few days back, and trust me Codeforces is much better.

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

I guess top gear isn't popular here :/

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

wannahavealife 1000-7 ? ? ? ?

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

it will be unrated for div 3??

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

Screenshot-20210611220724-857x462

Seems codeforces finally realized nobody reads this rules anyways, so they just removed it lol

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

This contest is rated for division 3 or not?

Any please replay

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

    Yes

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

    Every div3 member is also considered a part of div2 too. So hopefully it would be rated for everybody

    It will be a combined rated round for both divisions.

    @authors can you please help with this ambiguous statment maybe write it "rated for everybody" ?

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

interesting interactive problem. I hopeeeeeee

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

RIP my hairs after 3 hours :(

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

Contest will clash with Roland Garros finals :(

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

    I mean, it's dealing with crypto, and crypto is highly unregulated...

    But anyways, free money for CF!

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

Is this contest rated?

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

The scoring distribution is 500 — 1000 — 1250 — 1500 — 2250 — (1750 — 1250) — 3250 — 3500

(1750-1250) means?? can anyone explain please.

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

    There will be two parts to the problem. One easier version(F1-1750) and one hard(F2-1250).

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

One More Macbook to tourist

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

For some reason there is a scoring distribution update in the English version of this blog post, but there is no one in Russian version.

UPD: It's ok now.

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

For real, what's the point of making combined round when there are enough problems to split round for both divisions? Nobody from div1 wants to solve first few problems as well as nobody from div2 even reads last few problems

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

Hope! this round will go better for me than the Deltix round

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

The entire comment section in one not-somewhat-related meme:

picsart-06-13-05-14-58

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

Most People: This is definitely my chance to prove myself and get MacBook Air!! Tourist: This is definitely my chance to be first again!!

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

I am betting that tourist will not win this round. It will be some other LGM.

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

it's div1 + div2 = div3 :)

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

today junior tesla is expecting to solve 4 problems and upsolve extra 1 problem. Lets see.

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

Thanks to Djokovic I can convince myself that my rating crashed because I was watching Roland Garros finale
while giving the contest.

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

Although the Problem C was very interesting here's a meme
IMG-20210613-220345

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

Div 1+2 = rating loss

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

It takes eternity for queue to end

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

queueforces

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

There are no running submissions.

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

Is this still rated because the queue has been stuck for a long time now ?

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

I'm waiting for the results of my submissions from last 10 min.

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

queue too long.

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

People who are in queue are gonna remain in the queue forever if the number of running submissions is zero.

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

I always wanted to do it, and today I finally did

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

If someone wrongly pastes commented solution of A in problem B's submission, and locks problem B alone, won't this be a problem as others in room who have not solved A can see solution of A by solving only problem B ? And what if someone has commented previous problems solutions for all submissions ? How does codeforces handle this ? MikeMirzayanov

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

    Do you mean that somebody uploads their solution for A instead of a solution for B by mistake? But a solution for A is very unlikely to pass pretests for B. And it makes no sense to show the source code of failed submissions to hackers (I don't know if that's how it really works, because I have never tried hacking other solutions in non-educational rounds yet).

    Or do you mean that somebody submits a valid solution for B, together with a commented out solution for A in the same source file? Is anyone ever doing something like this? I do sometimes use my A solution's source code as an initial template for B. But by the time when I'm ready to submit it, no parts of A remain there.

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

      Is there any difference between submitting code with commented solution of other problem in it and pasting it in an open blog ( or social media, IDE, etc. ) ?

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

Anyone else having difficulty to understand the Problem C? Or am I the only one?

UPD: I got it. And I'm stupid. :(

UPD2: I think, I solved it.

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

    I perfectly understand it, the only problem is I am stupid and cannot figure out how to solve it ;)

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

    I spent half an hour, read several times, and don't understand what it means by "only by swapping numbers in a column". and finally I ask a question to admin, and then I got it.

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

      Yes, I didn't notice the announcement first. I felt really dumb noticing it after few minutes.

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

interactiveforces...

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

ME: Get's TLE on D :( .No worries, let's stress test by generating some random trees. Google please give me a random tree generator?
GOOGLE: Sure

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

The person who explained B's sample test cases

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

How to solve E? I think the soln is something like, do individual blocks on k, for last (n % k), if (n % k) is:

  • 1 — then no answer exists
  • any even number — 2 more queries
  • 3 — 3 more queries
  • any odd number more than 3, remove 3 elements in 3 queries and remaining even in 2.

Is this roughly along the correct lines?

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

    You can think that you have n columns and in one operation you add +1 to exactly k of them. You need to obtain odd sum in each column.

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

    How can you go for 11 4? I couldn't get this.

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

      if n % k is odd and k is even, the answer wouldn't exist.

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

        Thanks, then why the hell my solution is failing. Btw this is the only case where answer ceases to exist, right?

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

          Not sure about when n % k is odd and k is also odd. How are you solving this?

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

            Just make a move on first $$$n - n \% k$$$ elements and last n % k elements and this is same as k -> odd and n % k -> even.

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

              you might save some moves by saving up n-(n%k) indices by repeating them in previous queries. like

              n=13, k=5

              q1 : 1 2 3 4 13

              q2 : 5 6 7 8 13

              q3 : 9 10 11 12 13

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

                Yup I know and implemented this too, the above move needs to be done when n/k == 1.

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

    Answer doesn't exist only when k has more powers of 2 than n I think.

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

    That's part of it, but note that it's not always optimal to do $$$\lfloor n / k\rfloor$$$ blocks, sometimes you might want to do more or less. When I say more, I mean you can wrap around and cover an index twice. As an example, the optimal strategy for $$$n = 10, k = 7$$$ might look like this:

    ? 1 2 3 4 5 6 7      
    ? 8 9 10 1 2 3 4     
    ? 1 2 10 9 8 7 6     
    ? 3 4 10 9 8 7 6
    

    EDIT: After reading other comments it seems I did E in a very jank way, I did some strange bullshit with blocks of size $$$k$$$ that passed pretests so pray no FST.

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

    Make a graph with N + 1 nodes.

    Node i represents a state where i indices are used odd number of times.

    Here Node 0 is our starting point, and Node N is our desired end goal.

    Make an undirected edge from i to j, if you can perform an operation move from state i to state j. (can be bruted).

    Answer is shortest_path(0, N).

    Since we can move from one state to another state easily (again, brute), we get the answer after knowing the shortest path.

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

      Edit: Ignore

      Could you elaborate on how the number of edges can be bruted? Can't the degree of each node be upto O(k)?

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

        For a state i, brute the number of ones being converted to zeroes. (zeroes_to_ones + ones_to_zeroes = K).

        This way, you get all neighbours of i in O(k).

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

          Sorry I just realized my question was utter nonsense. I was asking how this didn't become $$$O(n ^ 2)$$$ even though degree could be upto $$$O(k)$$$ per node. I forgot $$$n \leq 500$$$ in the problem.

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

    If n%k equals 1 and k is odd, then answer exist. For example, for n = 6, k = 5:
    1 2 3 4 5
    1 2 3 4 6
    1 2 3 5 6
    1 2 4 5 6
    1 3 4 5 6
    2 3 4 5 6

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

    Using bfs from the final state and keeping count of number of positions used odd number of times will suffice

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

Today I got one of the best feeling that is solution D got accepted in last minute.

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

what was pretest 3 of E?

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

Thanks for including some easy problems for amateurs like me. :)

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

https://codeforces.net/contest/1534/submission/119394653 — This same case passes in my machine in 2 queries, i tried multiple other cases too. But CF says here it took more than 2 queries. Did i miss something here?

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

D problem... Killed more dreams than Fear every will ... :(

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

Solved F1 two minutes before the contests ends, what an exciting contest for me.

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

Can someone tell me, Why I'm getting ILE in Div2D ?
SUBMISSION.
I mean, I literally tried every combination of printf and endl. But couldn't get it worked. I usually use endl as a flusher but here it's not working.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    vi query(int r) {
        // cout << "! " << r << '\n';
        printf("! %d\n", r);
    

    The query format differs from what you print here.

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

+0 delta GG.

Should have not given the contest in the first place :(

Screenshot-290

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

I feel the problem statements could have been clearer/presented better, especially those with large statements.

At first glance, I saw "It can be proven that that if it is possible to recover the XOR sum under the given constraints, it can be done in at most 500 queries. That is, d <= 500", and went to write a code for atmost 500 queries..

Didn't help it was an interactive problem, where, if there's a WA I don't know if it's my IO format, or my solution is actually wrong.

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

how to solve D?

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

    Every tree is bipartite graph. You can ask only about nodes in smaller part. To know if node is in smaller part u can use this fact: distance between nodes from different parts is odd. So u just ask about first node, counting (cnt) nodes that have odd distance, and if cnt < (n+1)/2, first node is in bigger part, otherwise it is in smaller part. And then just greedy alg.

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

      can u explain these smaller/bigger parts in more detail. And how you are representing a tree as a bipartite graph. Would be appreciated

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится
        1. So, in bipartite graph every node belongs to one of two parts. Part that contains more nodes than other is bigger part, other part is smaller part.

        2. So, as I said if distance between two nodes is odd, nodes belongs to different parts. So, ask about first node, every node that has even distance to the first one, is in the same part with first node, otherwise, if distance is odd, it is in different part

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

    Here was my approach:

    Arbitrarily choose some node to be the root. Query that node. That gives you the rank of each node in the rooted tree. Our goal is to find the parent of each node.

    Iterate over the nodes in any order. Query each node whose parent is not yet known. We can use the result of the query along with the rank information to find that node's ancestors, siblings, and children.

    Notice that if we associate each query with the node and its parent, these pairs don't overlap. This proves that we won't exceed $$$\lceil\frac{n}{2}\rceil$$$ queries.

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

I think I missed D by printing a edge multiple times :(

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

The only time I am in top 500 is during system testing (T_T)

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

How to solve B?I had some proof that decreasing a number to the maximum of two sides will work but got a wrong answer on pretest 2

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

    you only need to decrease a number if it is greater than both its adjacent element.

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

      I did so but still a wrong answer.

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

        I think this is becoz , u have not dealt with n=1 separately for input 1 1 2

        the answer should be 2

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

    Erase a block off of a histogram if it is strictly higher than the previous histogram and the one after it. If you do so, you will pay $1 for each erased block and decrease ugliness by 2.

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

    Make sure you only do this on bars that are strictly higher than both of its adjacent bars. Also be careful with the left and right end bars as they only have one adjacent bar.

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

      I take care of both this situations but it still doesn't work.Can you take a look at my submission if you have time?

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

    Handle n=1 case separately. For n=1,ans will be arr[0]

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

    Suppose we have our original array orig and and our new array arr. We want to minimize:

    $$$\sum |orig[i] - arr[i]| + \sum_{} |arr[i] - arr[i - 1]|$$$

    So.. if we update $$$orig[i]$$$ to some $$$arr[i]$$$, we need to make sure that it is going to decrease

    $$$|arr[i] - arr[i - 1]| + |arr[i + 1] - arr[i]| + |orig[i] - arr[i]|$$$

    as compared to

    $$$|orig[i] - orig[i - 1]| + |orig[i + 1] - orig[i]|.$$$

    And from here, you can formally prove that its optimal to update a value iff it forms a mountain.

    And this makes some intuitive sense too: obviously, updating a valley is a bad idea. And if we update something that is neither a valley nor a mountain, then its pretty pointless and suboptimal.

    Also case when $$$n = 1$$$ needs some special case (or at least, my implementation needed special care).

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

      Padding the array with one extra 0 element in the beginning and one extra 0 element in the end removes the need to handle special cases.

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

how to solve problem C ?

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

What was pretest 3 in problem D? I failed it 7 times!

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

https://codeforces.net/blog/entry/91617?#comment-803516 YAY I was right. All Tourist fans owe me a buck xD. Congrats Benq

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

Anyone tried randomization in D and got it accepted?

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

When Ninjaclasher forces you to do a problem with your own name in it

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

Thank you for the round! The problems were interesting.

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

why G was so big constraint? My O(NlogN) solution get TLE (TT)

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

Hey Guys Do you know how can i see the delta points columns in the contest ?

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

Does anyone know why I can't view other people's submissions? Apologies if the reason was mentioned somewhere already and I missed it.

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

finally the rating loosing streak is back. So excited to have more negative deltas. Wish me luck.

Thanks for this round and making me feel how dumb I am.

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

Apparently many people solved $$$E$$$ with some casework. You can do also like: (which I think is intended solution).

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

Big ups to the authors for the nice problems, and bigger ups for including the answers to the possible sample queries in the interactive problems where it's reasonable. That's such a nice thing to do <3

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

will the number of cycles and number of connected components be equal in C?

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

Is there a way to see how many people failed system test for a particular problem ?

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

    They will never show that as people will backfire for weak pretests. Although this contest had strong pretests. No one on my friend list got FST.

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

      I found a way, just go to the status bar and check all rejected submissions keeping the tests greater than the number of pretests.

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

What if i tell you, that in problem A you just need to check whether given matrix satisfies:

RWRWRW                   
WRWRWR        
RWRWRW 
WRWRWR

or

WRWRWR
RWRWRW
WRWRWR
RWRWRW
WRWRWR

Realized this in post-contest discussion with my friend.

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

Finally Tutorials are here. I was thinking of finally offering some goat to the devil. Thanks to problem setters for fast update.

PS: BEFORE YOU COMPLAIN NO TUTORIAL TO BE SEEN IN THE BLOG. TRY TO FIND IT FIRST

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

Fst on D coming :(

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

Now it's time to wonder if I got a great place thanks to competing drunk or despite competing drunk.

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

https://codeforces.net/contest/1534/submission/119394653

Can somebody try this out on their machine. I submitted this in contest and it gave WA on pretest-1 and i tried it on my machine multiple times and it worked well. I'm really frustrated as I don't understand how the same code in 2 machines can give different output (my strategy isn't random, the program will always query the same nodes for a particular tree everytime it runs).

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

    When your local submissions behave differently from codeforces submissions, it often indicates that your code may have undefined behavior. In your case, I think you are trying to access an element out of bounds of the done array: see 119406377 where the assertions I added fail. I think it is due to the line fire2.pb(mp(x,b+1));, where b can be up to n-1

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

      Thankyou so much for taking out the time to look into this and getting back to regarding the issue. I definitely learnt something new today. I understand why this happened now. Have a nice day :)

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

Thanks for the great problems and strong pretests!

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

Looks like highest rating record on codeforces is going to be broken.

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

Two questions:

F: Does anybody remember a similar situation when solving a small version and then trying to upgrade it was a mistake? Normally it's rather a good way, but there the small version required only SCC while the big one doesn't (which may lead you to really long code).

H: Isn't an interaction with $$$10^5$$$ flushes rather slow/dangerous/generally not CF-friendly?

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

    I finally found a problem with a good upgrade in this F. Not like F1 has an interesting idea, just a straightforward "build graph, do SCC", where the main point of failure is building the graph in a wrong way, but there's an element of double checking — if F1 passes, you can expand on it to solve F2, while if your SCC is wrong and pretests for F1 don't catch it, then pretests for F2 might because it's way more than SCC!

    There's a good reason to go for SCC in F2 even if you don't have F1. As soon as you have it abstracted as a directed graph, compressing to a DAG gives you plenty of guarantees for the next step — actually figuring out the solution. It's not hard to write either, just reproduce those 20 lines of Tarjan from whichever online resource you want.

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

      Well, I took my code to F2, erased the whole thing with SCC, did some obvious stuff and it worked, so I don’t find SCC useful here at all.

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

        Well, I used SCC and didn't have to erase and rewrite, so I think it was a good path to take.

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

          What’s your solution then?

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

            Mark vertices that you need to cover, make scc, mark respective vertices in scc, unmark those that are reachable from another marked.

            Now you have set of marked vertices none of which is reachable from the other.

            I claim that you can sort them in some order that any source in SCC will cover segment of marked vertices, just sort them by column id of any marked representative in scc vertices.

            Now you have to figure out minimum and maximum reachable marked vertex from each source and cover array with minimum number of segments, which can be done greedily without actually finding segments: take first unmarked vertex, go through back edges and mark every node as visited, from each marked node go down and mark all nodes as visited as well. You will reach all sources that cover first marked vertex, which is precisely what greedy on array does. Then take next marked unvisited vertex and so on.

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

            First, rephrase the whole thing as: you've got a directed graph where some vertices are marked (the $$$a_i$$$-th sand in $$$i$$$-th column), find the smallest set of vertices such that each marked vertex is reachable from at least one chosen vertex.

            I compress to DAG, note that only topmost components should be chosen, then note that from the way the graph is constructed, no two topmost components can share a column, so they're easy to sort. Also, paths in the graph are actual paths in the grid, so the set of topmost components from which a given vertex/component can be reached is a contiguous interval.

            With a simple graph traversal, for each component, I find the leftmost and rightmost of the top components which are above it (minimum and maximum of their numbers in sorted order) and the problem reduces to picking the smallest number of points that cover all given intervals, which is well-known.

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

    I thought there should be a natural extension in F. So I continued with the SCC formulation and reduced it to finding a minimum size set of vertices in a DAG such that every leaf is reachable from some vertex in the chosen set. Then I tried to solve it with some (wrong) flow models. Does anyone know if this problem admits a good solution in general?

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

119382434 Can someone tell me why I'm getting runtime error?

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

    In practice mode (i.e. after the contest), runtime errors on codeforces can be caught by the C++ diagnostics compiler automatically. I resubmitted and it shows that your char arrays a and c are too small: 119406134

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

      Thanks for the information. Is there any way to overcome this error?

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

        Make the arrays bigger, e.g. char a[n+1][m+1], c[n+1][m+1]. Alternatively, use 0-based indexing in the rest of your code.

        An array int a[50] only has valid positions a[0], a[1], ..., a[49].

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

Benq has raised the bar of highest cf rating to 3796 now. Beating Tourist . Congratulations Benq.

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

https://codeforces.net/contest/1534/submission/119344612 Why did this fst? Can't seem to figure out.

Edit -> Don't use global variables when you don't have to.

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

Hi. Can someone explain me why I got WA on test 4 in B? The idea is correct but I can't find the mistake in my solution. Thanks

119386786

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

    hist[i+1] causes an undefined behavior because the max n is 4e5 and the size of hist is 4e5, enlarge hist by 1 element and soln will pass

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

      I gave hist a size of 4 * 100005 which is 4 * (1e5 + 5) so that shouldn't be the problem. Also, I just tried with hist[(int) 4e6] and again got WA on test 4.

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

        ah, I'm blind, sorry, you don't fill it with zeros for every testcase, that's the reason, it is global

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

good to be back

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

can some one tell why I am getting WA on this submission my friends solved literally the same idea and they got AC I literally can't find any wrong I am getting wrong on pretest 2 my program is printing 01234501234512345623456734567845678956789100 how can the program prints smth like this plz help https://codeforces.net/contest/1534/submission/119401086

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

Since the highest ever rating title was most likely taken (at least for now) from tourist by Benq, do you think he will take his revenge and first reach the 3800 mark?

Any bets who will be first over 4000?

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

To not keep you waiting, the ratings updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

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

become newbie!

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

Really liked C. I am not sure if this was already commented by someone on problem C, but here is what I did. Let the first row be the permutation $$$a$$$ and let the second row be $$$b$$$. We have the property that $$$a_i \ne b_i$$$ for all $$$1 \leqslant i \leqslant n$$$. Now, since this does not change the answer, apply the permutation $$$a^{-1}$$$ on both arrays.(by this I mean changing indice $$$i$$$ to $$$a^{-1}_{i}$$$) Now we have the identity permututaion and some derangement of it at the bottom. Let this derangement be $$$c$$$. Note that $$$c$$$ is equal to $$$b \cdot a^{-1}$$$. The important observation is that if you swap $$$i$$$ with $$$c_i$$$, then continuing you must swap $$$c_i$$$ with $$$c_{c_i}$$$ and so on until you "cycle" back to $$$i$$$. This inspires to think of the cycles in the permutation $$$c$$$. So, if there are $$$X$$$ cycles, we have $$$2$$$ possible states for each of them. Either you go through that cycle once or you do nothing.(note that going through a cycle brings you back to where you started). Thus the answer is $$$2^{X} \pmod {10^9+7}$$$. So, we can say more about the graph in the tutorial, each vertex has degree $$$2$$$.

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

    In my C solution 119368225, the array formed of upper/lower pairs simply gets sorted by the value of the upper element in each pair (since this doesn't change the answer). After this is done, the upper elements became the identity permutation and the bottom elements became a derangement of it. The rest is the same.

    The only difference is that my solution has $$$O(n \log n)$$$ time complexity because of applying sort. And yours is a smarter $$$O(n)$$$ solution, achieving the same end result. My reasoning was "let's sort the input data and see if the problem becomes more simple" and indeed that's what happened! I overlooked the fact that this degraded time complexity, but humongous sizes of the input data typically have i/o as the performance bottleneck (to the extent that C++ people are forced to use the sync_with_stdio voodoo magic). While sorting the input data rarely or even never becomes a real performance problem.

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

      Nice idea to escape using too much space. Really liked that sorting idea! I never thought of using that to make the code simpler! Thanks for the help!

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

Still don't understand why my solution on D catches: "Idleness limit exceeded on test 1". I even do cout.flush() after endl. Can anyone help me?

My last submission: https://codeforces.net/contest/1534/submission/119510328

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

Can anyone please tell me what is wrong with my code 119381067

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

[DELETED]

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

Dear contest team,

I received a message that two of my solutions (B, D) significantly coincide with what user "gamegame" submitted. If you take a look at them, they are significantly different, especially D. I wrote and compiled my code locally without using any online resources. This round was my best contest in years, and I would be very sad if the rating changes were rolled back even though I didn't share my code with anyone or copy gamegame's code in any way.

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

When will you announce random T-shirt winners?

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

Please announce random tshirts winner

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

Your solution 119352589 for the problem 1534A significantly coincides with solutions sanduio/119352187, Shunya_/119352589. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.`

Dear contest team(Dormi), (I'm posting it pretty late that's the reason I'm tagging you, sorry), I've received this message two days back however I saw it today, I just want to explain the whole thing rest it completely depends on you, apparently the guy (sanduio) whose code is similar to mine has been cheating in all the contests (he should've been blocked by now), please just have a look at his submissions, Your text to link here..., on that particular day I was as usual using cp helper extension in my VSCode however while running the test cases the antivirus was displaying that the trojan virus has been found and repaired in xyz.cpp file so to avoid that during the contest I shifted to ideone, Honestly I didn't know about that the code is public on Ideone before today. I understand it's my mistake that I violated one of the rules(which I honestly didn't know) however I'd like you to see his profile and his submissions so that you get the clear picture of the whole case (I'm not the one who copied), and please return back my ratings if possible, they are important for me. (This is the first time I'm posting a comment and honestly I don't understand much about blog and comment system, sorry if there's any error and sorry for being so careless). Thank you.

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

MikeMirzayanov

problem ratings of this round are not updated.

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

Congratulations to prize winners! You will be contacted in a few weeks regarding the prizes.

  • Benq — MacBook Air M1 + Job offering and Stock Options
  • tourist — Xiaomi Mi 11 + Job offering and Stock Options
  • Radewoosh — Xiaomi Mi Notebook Pro 15" Enhanced Edition + Job offering and Stock Options

Job offering and Stock Options + Merchandise Pack:

List place Contest Rank Name
4 1534 4 Endagorion
5 1534 5 ecnerwala
6 1534 6 heno239
7 1534 7 VivaciousAubergine
8 1534 8 gamegame
9 1534 9 Pyqe
10 1534 10 maroonrk

Merchandise Pack:

List place Contest Rank Name
11 1534 11 ksun48
12 1534 12 jiangly
13 1534 13 neal
14 1534 14 Marcin_smu
15 1534 15 ko_osaga
16 1534 16 djq_fpc
17 1534 17 PinkRabbitAFO
18 1534 18 Um_nik
19 1534 19 Maksim1744
20 1534 20 SSRS_
21 1534 21 rama_pang
22 1534 22 ainta
23 1534 23 antontrygubO_o
24 1534 24 LayCurse
25 1534 25 ugly2333
26 1534 26 gop2024
27 1534 27 uwi
28 1534 28 LJC00118
29 1534 29 fastmath
30 1534 30 hitonanode
31 1534 31 Xellos
32 1534 32 Siberian
33 1534 33 Martin53
34 1534 34 never_giveup
35 1534 35 noimi
36 1534 36 dreamoon_love_AA
37 1534 37 fuppy
38 1534 38 natsugiri
39 1534 39 Arpa
40 1534 40 kostia244
41 1534 41 EzioAuditoreDaFirenze
42 1534 42 mango_lassi
43 1534 43 Rewinding
44 1534 44 kotamanegi
45 1534 45 KostasKostil
46 1534 46 dreaming_away
47 1534 47 SecondThread
48 1534 48 tatyam
49 1534 49 Golovanov399
50 1534 50 fsouza
51 1534 51 --d
52 1534 52 Suiseiseki
53 1534 53 conqueror_of_tourist
54 1534 54 Misericorde
55 1534 55 _overrated_

T-shirt:

List place Contest Rank Name
126 1534 126 sd0061
277 1534 278 BrayanD
810 1534 814 Sad_reacts_only
1068 1534 1080 MaytaCapac
2162 1534 2181 erfanul007
2484 1534 2515 I_love_Avicii
2976 1534 3016 SU_N_NY
4137 1534 4204 awesomemaths
4514 1534 4592 sejdemese
6367 1534 6510 vineeth143