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

Автор m3tr0, 5 дней назад, По-русски

Привет, Codeforces!

Хотим пригласить вас поучаствовать в Codeforces Round 984 (Div. 3), который состоится в 02.11.2024 17:35 (Московское время). Вам будет предложено 7 задач и 2 часа 15 минут для их решения. Штраф за неверную попытку будет равняться 10 минутам. В раунде могут быть интерактивные задачи.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов, после её завершения все успешные попытки будут перетестированы на успешных взломах. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у вас будут падать решения после окончания контеста.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Задачи были составлены и подготовлены командой, состоящей из Seny, eugenechka.boyko.2_0-0 и меня.

Раунд основан на прошедшей недавно Липецкой командной олимпиаде школьников по программированию. Обратите внимание, что если вы являетесь участником олимпиады, вам не разрешается участвовать в этом раунде. Спасибо координатору этой олимпиады myav и составителю Small_machine, задачи которого не вошли в этот раунд из-за высокой сложности.

Мы очень благодарим:

Мы надеемся, что задачи покажутся вам интересными. Удачи!

UPD.: Разбор

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

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

Looking forward to Round 984. Let’s have a good contest. Good luck, everyone!

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

    the contest was BS

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

      BS?

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

        Biased

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

        Binary Search

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

      I wish I could approve more than one time

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

      I've never seen bad contest like this.

      I hope we have better Div3 contest next time

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

    please answer that if i had submitted a solution just before time up and it is running test cases and after time up the solution was accepted, will it be counted or not

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

As a tester i almost became a tester and I am happy about it.

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

As a non-tester, I did not test it.

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

as a tester, i can assure you that these problems are, indeed, problems!

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

As a !tester I think you will like the problem sets

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

Even though I will be considered a trusted participant, when I'm trying to register, it says, "You are registering "out of competition" reason: rating should be between 0 and 1,599 in order to register for the contest." Why is it so?

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

    your rating is $$$\ge 1600$$$, so you are an unrated participant

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

      Then what about the trusted participant thing mentioned in 3rd paragraph? More than 5 contests and <1900

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

        About the results table of the round.

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

        The max rating not at 1900 or higher imo is to cross out the scenario that someone already participated a lot and had a high skill ceiling that purposely threw their ratings down to oblivion just to be rated in Div3/Div4.

        In short, preventing smurfing from legit/long-reputated account.

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

          But in fact, unrated participation is a way to increase your rating on your second accounts. So, we already have a lot of cheaters.

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

            True. Honestly those measures hold more to the moral ground than actual enforcement. That's something, but not perfect.

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

    bro,it's DIV 3 let it be for us for beginner.

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

as a tester, i want to sleep, i hope you enjoy the tasks

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

hope to enjoy this round

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

what is the difference between div1, div2 and div3? Is it only the level of difficulty?

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

    Yes, div1 is the hardest, div2 is slightly easier (often, div 2 contests run in conjunction with div1 contests, where the div 1 contest starts with the div 2 C problem), then div 3 is easier (I'd say div 3 E is equal to div 2 C in a lot of cases), then div 4 contests (which aren't as common) are the easiest

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

i went to daycare with testers!!!

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

Finally! An adequate round without pendochinese authors!

With love to my kittens

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

promlems❌ problems✅

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

    thanks

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

      I was 61 points away from reaching pupil. Now due to this disgusting baseless round I'll lose my points. I regret participating it, especially that string problem sucks. Hopefully God can kill me is worst possible way. I don't deserve to live!

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

        chill dude just a contest

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

        Agree. I got 4 pretests passed without an hour of the contest. But two of them (C andD) failed system testing and i went from +100 to -25

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

      worst presets.. worst problem pattern.. worst contest

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

There is a typo on the last row, it should be "problems" not "promlems".

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

hi guys i want dat delta tomorrow watch me ok i become the 500 rated directly or maybe 600 as well please watch ok ok i am curt btw i am

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

As a time traveller, this round is going to be historic. Also, the replies to this comment will be filled with "this aged like milk" after the contest. Good Luck!

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

What?Interactive!Oh,my,god.I have don't konw that do this problems.

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

justlm orz

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

aiming for pupil this round

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

No interactive problems pls T_T

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

Good luck everyone :)

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

Hope to be expert soon.

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

good lucky!

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

Guys, can someone please provide me the standard template for an interactive problem, it would be of great help.

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

    Why would you need a template, just remove the fastIO part of your template and thats it. You can also make a ask function, so you dont have to type out the interactions, but thats it. Also dont use endl in your normal code, use \n, its much faster.

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

      Thanks Brother, can you just explain why to remove the FastIO part?

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

        since it messes with the input and output and puts everything at the end, you cant interact properly with the system because you cant output the questions in the middle of your code

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

      Can't you just use cout.flush() after every output in cpp along with the fastio part?

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

        yea, i think you can, but that makes the output the same speed as if you didnt have fastio, and also you have to constantly put flush after every cout, which is a hassle imo

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

          If you put your inputs and outputs in a single function and use them then there won't be any hassle.

          E.g. query and output functions in 289277508

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

Let's go!, div 3 is good for me

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

I am Vladosiya fan

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

Is E maximum flow problem ? :laugh: :laugh: :sob: :laugh:

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

Is E maximum flow ?

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

I'm going to start my first race with c++

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

wish to be pupil after this round.

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

As a contestant, I hope I don't make stupid mistakes.

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

As a F1 fan I hope Norris wins the sprint race while I AC div3.

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

Currently I'm facing some problem in my account. I couldn't see the implementation to anyone else's code. Codeforces shows me N/A. How to solve this issue.. Can anyone help me?

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

    You have not made a submission on a single contest that you registered in, you cannot view other's codes. I do not know why.

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

    I had the same problem as you , if you log in your account in another device , just log out .

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

I'm new to Codeforces. Is this contest useful for me?

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

specialist plssssssss codeforces

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

Where can I read editorials for the contest?

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

i hate div3...

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

I hate Div3...

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

I hate C

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

    i made so many tiny errors costing me like 30mins total. so much implementation for this contest

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

I've enjoyed F, cool problem, thank you.

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

nice tasks

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

implementation forces

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

What is the purpose of problems like D?

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

so much cheating today

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

implementation forces sucks..

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

liked this round :)

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

problem D description could have been better ngl I spent first 1 hour on problem reading question wrong this layer thing could be highlighted instead of writtenn in small font I though you have to traverse clockwise on every cell smh

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

I hate it when the time limit for problem F is 1 second

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

    That's cuz I guess we can do it O(1) using range xor properties.

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

      that is true!

      first of all, $$$a \oplus b = c \Rightarrow a \oplus c = b$$$, so we need to find xor on range $$$[0;\ n]$$$. let the number $$$x$$$ be $$$(i,\ k)$$$-good if $$$x \equiv k\ (\mod 2^i)$$$.

      $$$\DeclareMathOperator{\xor}{XOR}$$$ let's try to find xor of all $$$(i,\ k)$$$-good numbers from $$$[0;\ n]$$$. firstly, all numbers from $$$0$$$ to $$$n$$$ are $$$(0,\ 0)$$$-good, and finding xor of all numbers is a popular task (you can find many implementations of it). let $$$\xor(n, i, k)$$$ be xor of all $$$(i,\ k)$$$-good numbers $$$\le n$$$. then

      $$$\xor(n, 0, 0) = \begin{cases} n, &\textrm{if } n \equiv 0\ (\mod 4)\\ n \oplus (n - 1), &\textrm{if } n \equiv 1\ (\mod 4)\\ n \oplus (n - 1) \oplus (n - 2), &\textrm{if } n \equiv 2\ (\mod 4)\\ n \oplus (n - 1) \oplus (n - 2) \oplus (n - 3), &\textrm{else} \end{cases} $$$

      now, let's find xor of all $$$(i,\ 0)$$$-good numbers. one thing to notice is that $$$2^i \cdot a$$$ is the same as bitshifting $$$a$$$ to the right, so this case is equivalent to the last one with one exception. let $$$f$$$ be the biggest number, such that $$$2^i \cdot f \le n$$$. then

      $$$ \xor(n, i, 0) = \begin{cases} 2^i \cdot f, &\textrm{if } n \equiv 0\ (\mod 4)\\ (2^i \cdot f) \oplus (2^i \cdot (f - 1)), &\textrm{if } n \equiv 1\ (\mod 4)\\ (2^i \cdot f) \oplus (2^i \cdot (f - 1)) \oplus (2^i \cdot (f - 2)), &\textrm{if } n \equiv 2\ (\mod 4)\\ (2^i \cdot f) \oplus (2^i \cdot (f - 1)) \oplus (2^i \cdot (f - 2)) \oplus (2^i \cdot (f - 3)), &\textrm{else} \end{cases} $$$

      lastly, $$$0 \le k < 2^i$$$, so $$$k$$$ changes only $$$i$$$ last bits of a number. that is why we can deduce the following (assuming $$$f$$$ is the maximum number, such that $$$2^i \cdot f + k \le n$$$)

      $$$ \xor(n, i, k) = \begin{cases} 2^i \cdot f + k, &\textrm{if } n \equiv 0\ (\mod 4)\\ (2^i \cdot f + k) \oplus (2^i \cdot (f - 1) + k), &\textrm{if } n \equiv 1\ (\mod 4)\\ (2^i \cdot f + k) \oplus (2^i \cdot (f - 1) + k) \oplus (2^i \cdot (f - 2) + k), &\textrm{if } n \equiv 2\ (\mod 4)\\ (2^i \cdot f + k) \oplus (2^i \cdot (f - 1) + k) \oplus (2^i \cdot (f - 2) + k) \oplus (2^i \cdot (f - 3) + k), &\textrm{else} \end{cases} $$$

      now, let $$$\xor(l,\ r,\ i,\ k)$$$ be the xor of all $$$x$$$ such that $$$x$$$ is $$$(i,\ k)$$$-good and $$$l \le x \le r$$$. then $$$\xor(l,\ r,\ i,\ k) = \xor(r,\ i,\ k) \oplus \xor(l - 1,\ i,\ k)$$$. then, answer to the problem is just $$$\xor(l,\ r,\ 0,\ 0) \oplus \xor(l,\ r,\ i,\ k)$$$, cause every number is either interesting or good

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

        Very well written. I just thought of xorring f*2^i for all f such that k + f * 2i is within l and r. since k has lesser bits than ith bit, we can treat their xor independently. as for the xor of f * 2 ^ i, we can think like normal range xor but all the xorring is happening starting from the ith bit instead of the first bit so the result is just the range xor of all f, then shifted by i, and as for the k, if there are even f's then 0 otherwise k.

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

          sounds true, when testing i just didn't want to think much, so i made the first solution that came to mind, and all work above is just my line of thought

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

        Awesome explanation, I did the same here https://codeforces.me/blog/entry/135766?#comment-1214968 just idk how to use latex in cf, how to do this?

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

        omg so beautiful, can i steal it for the editorial?)

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

        I think it is worth to note that you can seperate these operations, so to calculate the range $$$[0:r]$$$, you can first calculate the xor of all values (this is well known since $$$1 ->n+1 ->0 ->n->1 ->n+1...$$$) and then xor that with all values in $$$x$$$ in $$$[0:r]$$$ that are interesting. Their value is $$$k * (f\%2)+ (XOR(f-1)) * 2^i$$$, where $$$XOR(x)$$$ denotes the xor for all vaules in range $$$[0:x]$$$.

        So for the range $$$[0:r]$$$, the answer is $$$XOR(r) \oplus ((f\%2) * k) \oplus (XOR(f-1) * 2 ^ i)$$$

        submission

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

        what (i,k) mean?

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

woah!!

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

For Problem-E, how to reduce the time complexity?
My current Implementation gives me TLE

Each Query * Each Country * Each Region (q*n*k)

CODE

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

How is this even possible in problem G?

submission

    assert!(first != second && second != third && first != third);
    assert!(ask(io, first, first) != 0);
    assert!(ask(io, second, second) != 0);
    assert!(ask(io, third, third) != 0);
    assert!(first <= n && second <= n && third <= n);
    assert!(first >= 1 && second >= 1 && third >= 1);

Basically I check that my answer satisfies all condition, but I still got WA2. In rust asserts work in release code too, so I'd expect RE if my answer is wrong. Am i dumb?

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

    probably your solution exceeds the requests limit

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

    In interactive tasks like this one (where you can either output a answer or terminate the program if the requests are exceeded) RE goes to WA, since the participant can terminate the program including throwing any exception.

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

      Good to know. Now I will use MLE for this purposes :)

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

      That's not entirely true! For example the testing problem mike made back when interactive was first released correctly reports RTE as RTE. 101021-1 - Guess the Number, https://codeforces.me/blog/entry/45307

      My guess is that whoever coded the validator for 2036-G - Library of Magic was lazy and didn't bother making an RTE display as RTE. It would be nice if CF had standarized how RTE on interactive works, but that is clearly not the case.

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

        In the task you cited, there is no choice between outputting the answer and terminating the program to get WA (this logic is not a novelty of any of the contest organizers, I have seen many tasks where such a choice was given)

        Redirecting "Unexpected EOF" (including from throwing an exception) to WA is not some grossly wrong decision. Such a possibility is given in testlib.h (see ENABLE_UNEXPECTED_EOF macro) and is marked as suitable for interactive tasks.

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

          So from what I understand, if you don't use the macro, then if the user's program RTEs, it will be reported as an RTE.

          I'd argue that reporting RTEs as RTEs is a lot better than reporting RTEs as WAs. Interactive problems are confusing enough to debug to begin with. And someone could just make a homemade MLE/TLE assert anyways.

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

Tried so hard,

Got so Far,

But in the End,

got 6k rank .....

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

Problem D is kind of an extension of the Leetcode problem spiral-matrix.

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

Absolutely absurd.

Wasted so much time on C and btw Java's substring is O(N). How on earth is that even possible! Could've solved even D if it wasn't for this retarded language.

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

    Why to use substring which has O(N) TC. Just take 4 indices as per need as substring scans whole array I guess.

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

      For the check afterwards if it makes or breaks the 1100s. Had to write it manually.

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

    Uhhh no. The problem is with your n = new String(str); in your TLE submission.

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

      Yeah haha, that was the issue thank you

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

      289515042

      Could you please help in this one ? The time complexity is O(t(q+n)), right(ignoring the map queries) ? Then why is it taking 2999ms to run ? The time limit was 3s, so somehow managed to pass. How do I optimise it further ?

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

        I just read through your code, there are some lines where you assign the strings t=s and s=t (This costs O(n)), so it can grow to O(t(q*n)), basically.

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

          Aah, right! Thanks a lot. The t string was redundant. I could just directly have modified the character in s.

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

implementation forces lol

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

For problem C can anyone please tell what is wrong with this solution: Submisssion

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

    I think the range is i-3 to i+3 you put <i+3 making it i-3 to i+2

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

    try out this test, it might help

    1
    1100100
    9
    4 0
    4 1
    7 0
    7 1
    7 0
    1 0
    2 0
    3 1
    4 0
    

    The result is 3x YES, NO, 4x YES, NO

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

      Did you come up on your own with this case?

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

        of course my own, you can see I have WAs at C... then I hack myself with this test case

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

        btw I like the way you solved E in 1 go then go back to D-C.. actually impressive which I can't do for a while (skimming problems then aim at better accuracy). For now I just doing problems in default order.

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

          Usually I feel like I can solve problems (the logic building part) but it's usually dumb errors in my code the get me, like the above code, or my logic is completely broken. So, I prefer to move onto the next problem.

          This doesn't work out in my favor when I can't even solve the next questions.

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

            Nice to know the strat, probably when I'm stuck and figured my logic is broken, it's better moving on to the next problem. (Still have a long way to climb)

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

F was very good about the idea I wonder if there any other solutions

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

    This is my solution — https://pastebin.com/BCxvvJH8, my idea was to basically first find the XOR of all the numbers in the range [L,R], and then find the first & last occurrence of number of type x , in the range [L,R]. Then observe if the count (number of such numbers in the range) is odd then k contributes to XOR, else not. And the XOR of such numbers can be proved to be the rangeXOR(firstcount, lastcount). The answer would be the XOR of all these i.e. (XOR of numbers from L to R)^(XOR of numbers from countofx_morethan_L to countofx_till_R)^(k)).

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

    Problem F can be solved int just two steps

    1. Calculate the XOR of numbers in range [L, R]
    2. Determine the first non — interesting (let it be C) number greater than or equal to L and then its obvious that all non — interesting numbers will form AP with common difference d = (2 ^ i) . Using this calculate the XOR of the non interesting numbers C , C + d, C + 2d .......... C + kd (such that c + kd <= R)

    The final is XOR of values obtained in the above two steps

    The rest lies to calculate the AP XOR efficiently which is same as this ques (http://http://poj.org/problem?id=3495)

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

implementation forces lol

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

pD and pC are exactly the same problem with annoying implement. No skill on pD, just implement, really bad problem.

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

I'm a happy man now after all the practice is actually paid off, result is yielded (I peaked my performance). Thanks for the div 3 contest.

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

Implementation, Implementation and only Implementation.

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

interesting F

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

Is G a can be a ternary search problem, or it is necessarily a bit problem?

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

    Bits. The limit of 150 queries makes ternary search very difficult, if not impossible.

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

Implementation forces sucks...

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

G is interesting and difficult tbh.. G2. Ruler (hard version) didn't help me to come up with some useful thoughts..

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

D was extremely annoying. It shouldn't have been a part of this contest, especially when spiral matrix (on leetcode) is such a well-known problem.

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

    Even though it is a well known problem, you couldn't get AC in one go, so there is something to learn even from problems like D. Stop crying and get better.

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

      Yes, I agree with you. We can't have contests as per our mood/need. Sometimes it balanced, sometimes it is implementation heavy sometime not...

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

      So many people cry in math heavy contest (976 div2), greedy also cry (981 div3). Now implementation heavy also cry... (this contest)

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

      If you had a little bit of brain, you'd try to think about what I'm inferring in my comment. The point I was making is that there's often a lot of cheating when popular pre-existing problems are put up in contests. That's all.

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

        FYI, it's not considered cheating to refer to pre-existing sources on the internet in a Codeforces contest.

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

          Right, my bad. Anyways, I still think that it is a bad choice to put up questions whose 70% logic can be copied from an already-existing source on the internet.

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

Bitwise-Forces :D

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

Can someone please explain what is expected in Problem F. (I didn't quite get that expression itself). Thanks in advance.

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

    If you know python, I give you my naive code that express the F problem (of course this is just naive approach)

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

ImplementationForces

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

Couldn't implement E in time having 40 min time. So dumb

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

Problem F sucked.

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

respects to the authors but my honest review is that the contest was 'senseless' and of less quality. I gave up when I saw C and D and realised you just need to write a bunch of code and waste lots of time debugging (you could say I have implementation skill issue). D was also soo similar to spiral matrix on leetcode. I just felt demotivated moving forward.

Maybe I have to work on my implementation but traversing a grid in some beautiful way does not improve my thinking.

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

BS forces

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

BITWISE-forces :D

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

I appreciate the effort of the authors of this contest, But the problems were not that good, I feel like I didn't learn new things in this contest or even have fun while solving the problems as they were just implementation, and other problems were very standard problems.

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

    it's just a contest out of millions next contest might be based on something else

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

    its div 3, I don't think you should necessarily need to understand advanced data structures to do well. As a noob im happy to get more implementation practice like this.

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

      Yes, but I mean that it needs different topics to cover not just implementation and brute force. its div.3 not div.4

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

    Thanks for the criticism. Yeah, the first part of the contest is probably too trivial, and the second part is too difficult for most of the contest participants, although interesting

    If I venture to come up with more problems in the future, I'll try to take into account all the mistakes with this contest

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

      I really appreciate your efforts, It's your first contest as a problem setter, So it's great as a beginning, I am waiting for your next contests. Thanks, a lot

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

      Based, +1 for the heads up

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

      appreciate how you took the feedback. To add, it would have been okay if it's div 4. We look forward to your next one :). P.S: Thanks for showing me I need to work on implementation though lol.

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

      This guy is gold in taking criticism.

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

How to solve C ? what is the best complexity ?

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

    O(n+q)

    I kept track of number of occurrences, and for each query checked if it would make or break an occurrence, by checking the bits around it.

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

    I was accepted with O(N + Qlog(N+Q)) using set 289529638

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

    Influence of changing one bit only reaches a few segments of length 4, so each query can be processed in constant time after you have calculated the initial amount of 1100 in linear time.

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

      What is the intuition behind your solution ? Why do you subtract count of "1100" before change ?

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

    count the initial number of 1100 and for each query you just have to check 4 bits around the change

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

In Problem G, why is this (https://codeforces.me/contest/2036/submission/289601805) code giving Idleness limit exceeded error?

I am flushing after each cout. Besides on my local compiler it is working fine (can it be possible an interactive problem messing up in submission verdict but working fine in local?)

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

implementationforces

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

.

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

Thank you very much for the contest.

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

Can someone please help me why my submission for problem E isn't working. I spent a lot of time but wasn't able to figure it out.

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

Nice problem F.(only problem which required thinking in A-F).

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

    Uh, thank you. Yeah, we realized that the first part of the contest didn't turn out so well. I'll try to learn from mistakes

    I hope you find G task interesting too)

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

In Problem F, could someone please clarify the meaning of $$$x \not\equiv k \pmod{2^i}$$$?

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

Time for me to go back to newbie.

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

Div3s are great contest...

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

I think this is a very good contest given that it targets participants with rating < 1600.
I solved problems A-E which didn't really require a lot of thinking to find the main idea but these problems did need some thinking to find the most effective way to implement solutions as well as some skill and focus to write the code and test it.

For me, I didn't consider alternatives to implement the main idea and that's why I suffered and never have a chance to even look at problems F and G.
If problem F and G requires some thinking, like a Div 2 D, then this is a very good contest for Div 3.

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

Can anyone help me figure out why the response from judge in my submission is negative?

submission

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

    you are making mistake in finding the value of $$$start$$$ when $$$t = 0$$$

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

      Yea but you can see in this submission that although the first is correct, my output is contains negative.

      I still cant figure out why its become negative.

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

        it looks like you exceeded the request limit when all three numbers are large

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

        I think you still making mistake in finding $$$start$$$ you see you are checking this way :

        1

        10

        100

        1000

        10000

        this is not always the correct approach , you have to search this way :

        1

        11

        111

        1111

        11111

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

Someone please hack this https://codeforces.me/contest/2036/submission/289514229 string parameter of check() function isn't passed by reference , so it took 2.5seconds. Later i corrected it and submitted again and it ran in 100 ms. So i suppose passing by value should result in TLE for certain test cases??

»
3 дня назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится
A Python script to test solution on problem G
»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

in problem D layer is defined as closed strip
also there is defined no defined start point so this means that layer is circular
so why this solution 289520489 is incorrect

Polycarp became curious about how many times the number 1543 would appear in all layers∗ of the carpet when traversed clockwise

Edit : the layer is circular, my code fails on some other issue

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

    i think to calculate the number of layers we have to do min(N, M) / 2 intead of just N /2

    try this testcase

    1 4 2 37 47 57 17

    if we do n/2 layers count will be 2 but its only 1

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

      that's not the issue
      consider this
      2 2
      43
      51
      the only layer here it is 4315
      so my code will give 1 while checker will give 0 .

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

    in your solution you iterate left up layer start cell from 0 to n/2-1, but correct will be do it from 0 to min(n,m)/2 (think for yourself why), so your solution will failed in tests where n>m and where 1543 is on the right side from bottom to top

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

    Print the indexes you are accessing when n >> m and you will get the error.

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

      can you give hacking test.

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

        The hacking case was pretty large. But I guess this testcase will give a runtime error.

        1
        6 2
        68
        28
        06
        36
        24
        35
        
        

        I also found a tc that will give wa verdict.


        1 8 2 11 12 52 43 34 25 12 12

        The output should be 0

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

    try this, the output is 1

    1
    8 4
    1234
    1234
    1234
    1334
    1434
    1534
    1134
    1234
    
»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

some one please tell me why this python solution 289486115 gives TL

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

    start getting used to writing code in c++) dict object in python is quite slow relative to cpp unordered_map (but still working for amortized O(1)) a python solution may exist with using list with indexes as bottle types (but im really still not sure)

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

    yes, this python solution passes all tests

    def INT(): return int(input())
    def MAP(): return map(int, (input().split()))
    def MAT(n): return [list(map(int, (input().split()))) for _ in range(n)]
    for _ in range(INT()):
        k,n=MAP()
        w=[0]*(n+1)
        for i in range(n):
            t,c=MAP()
            w[t]+=c
        print(sum(sorted(w,reverse=True)[:k]))
    
  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The problem is that sets and dicts in Python are vulnerable to hacking due to the hashing function being predictable. You can read more here.

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

    My own python exp: I did got FST once the same as you and I learned my lesson.

    Never sort a dict. if you really need to sort, sort an array 1st then input it to dict.

    btw here's how I do B without maps 289482585

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

i did ABCD in contest, read E, and couldnt bother writing the code after getting the idea in 5 seconds, and after that i just didnt bother doing the rest of the contest, and i wont bother to read F and G, since ABCDE are just boring, unoriginal and implementation based problems. this is probably the worst div 3 i participated in, and was actually probably the first contest i actually just quit doing in the middle of the contest due to how boring it was, even though i knew the solution to the problem. im sorry if its harsh, but i think being honest and giving genuine feedback is the most important thing, and I hope you improve in your problemsetting skills.

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

    and also I think the statement for D is terrible, and i dont understand how that is ever allowed to be an actual statement. half of the difficulty of the problem is comprehending whatever you meant to say in that abomination of a statement

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

    Thank you for your sincerity, I will try not to make similar mistakes in the future

    It's a pity you didn't read F and G — according to other participants, these were the tasks that were interesting and useful (I realize that this is not an excuse and that all tasks should be interesting, not just a few)

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

As a hacker I hacked 50 solutions

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

THIS IS THE MOST TERRIBLE CONTEST EVER. weak tests for E, implementation for ABCE, and almost no algorithms involved. My solution had an obvious error in it and it passed the tests for E.

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

I don't seem to understand the expectation people have with Div.3 and why they didn't like the problemset. It seemed that the problemset was balanced. Only thing I can add is that the language could've been better, Apart from it I don't see any other negatives. I liked writing the binary search code for problem E. and other problem seemed good as well for Div.3.

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

    Thank you for support!)

    Many participants did not like that in some tasks it is much more difficult to realize the idea than to solve the problem. I understand them and agree that this is wrong

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

      but pls make the pretests stronger, ok?(especially for E)

      Note: im RE_Prince's alt acc

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

        Unfortunately, it is no longer possible to improve the pretests for E, but for the future we will definitely keep this in mind and try to think of more “silly bugs” in the pretests

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

    The authors promised that tests would be decent. But pretests turned out to very weak tests... So, people blame the authors.

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

    General problem with div.3 and ABCs is that they have several problems in the beginning that are basically a waste of time. I'm not saying this is a bad problemset design, but what happens is that ABCs and div.3 mainly teach people how to code fast without thinking that much and when they start solving ARCs and div.2 completely different skillset is required and there is no gradual transition between those contest types.

    The only real solution that works for me in div.3\ABCs now is changing the order: instead of ABCDEF doing something like DEFABC or EFABCD, so that I can enjoy harder problems first and then solve easy ones if there's time left, which makes contest experience much better.

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

I thought the problems were alright, A-E are mostly implementation, but you can make them relatively simple with the right approaches. F was nice, I tried to figure out the xor properties on ranges for a O(1) answer, but just got a headache instead

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

Overall this contest wasn't good, I disliked that D was purely implementation, and E had a rather wordy statement. I heard that F and G were actually fun, so I will upsolve those and hope to feel the same way, however for the first 60% of the contest, it was quite bad. Tasks should, even if educational, have some observations. Not only was D lacking observations, it wasn't even educational, anyone could mindsolve in a very short amount of time, and it would fully depend on whether they could implement well or not. While that is still skill dependent to some extent, tasks should be educational imo, as that is the true value this site provides in the first place. E was ok, however it could have been written more clearly. While I know I've said some harsh things here, its because I'd like to see improvement from the authors in the future if they decide to continue setting rounds. If they read this, please note it is constructive criticism, not an insult, even if its worded harshly. Thanks for the contest either way.

(also after seeing someone not check l>r and still pass for E, please make pretests better (this ones more funny than depressing though lol)

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

    I am the person who forgot to check l>r [skull]

    I HATE PRETESTS!!!!!!!!!!

    And it is NOT funny :)

    P.S. I upvoted u

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

I think G is a good problem, but I don't know how to solve it until now. :(

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

    This is what the content part of my solution for G looks like. Try to understand why it is correct (and why naive binary search isn't correct)

    l n, num1, num2;
    
    l req(l le, l ri, l num) {
        if (le > n) return 0;
        if (ri > n) ri = n;
        
        printf("xor %lld %lld\n", le, ri); fflush(stdout);
        l res; scanf("%lld", &res);
        
        if (num > 1 && le <= num1 && num1 <= ri) res ^= num1;
        if (num > 2 && le <= num2 && num2 <= ri) res ^= num2;
        return res;
    }
    
    void solve() {
        scanf("%lld", &n); num1 = 0; num2 = 0;
        l start = 1LL << (63 - __builtin_clzll(n));
    
        for (l i = start; i > 0; i >>= 1) {
            l res = req(num1 | i, num1 | (i * 2 - 1), 1);
            if (res) num1 |= i;
        }
    
        for (l i = start; i > 0; i >>= 1) {
            l res = req(num2 | i, num2 | (i * 2 - 1), 2);
            if (res) num2 |= i;
        }
        
        printf("ans %lld %lld %lld\n", num1, num2, req(1, n, 3));
        fflush(stdout);
    }
    
  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I usually dislike XOR problems in general, but I should say this one was very fun to solve for me. It requires only a few but nice observations while it doesn't involve any complicated formula.

    Interestingly, problem F was the exact opposite style of this, and I had a very painful time and wrote a very terrible implementation for it :(

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

I want to go to sleep and I'm already out of energy to respond to all the comments/feedback/accusations that I really want to respond to) But I'll read and consider every comment anyway

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

I tried F and G. F was nice, and I can't solve G yet. Nice problems.

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

does anyone know where is editorial(i am new i don't know where to get editorial)

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

I have participate in it. It was really good contest.

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

Really enjoyed F and G :D

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

I wish i can be tourist after this

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

I personally don't understand why there's so much complaining. As someone who is actually Div. 3 level, the actual intended audience of the problem set, I don't see how it's significantly different from many other contests I have participated in. Perhaps D needed to be swapped with something else, but even that seemingly simple problem took me a while to write the solution. Meanwhile top competitors implemented this quite easily, which shows I have a lot of work to do to improve even the implementation of solution after understanding what is required.

On another note, it is very disappointing how many cheaters compete on CodeForces. It becomes evident if trying to have a go at hacking that a large amount of contestants are blatantly copy and pasting code directly from ChatGPT and/or copying solutions from others. There was such a blatant group of cheaters for Problem E that I had to post here for documentation purposes. It will be interesting to see how many out of this group of 79 cheaters with essentially identical code (ignoring their attempts at obfuscation) get caught by the plagiarizing detection system.

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

My rating was 781 before i give this contest . In this contest i solved 2 problems . But my rating did not increases. I do not know why this occur. In this blog i read that less than 1600 rating will be rated. But my rating did not increase. Can any one help me with a answer?

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

    ratings are not updated yet, they'll be updated just after the hacking phase

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

      Thank you so much for the answer.

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

        for contests ruled according to the standards of educational rounds (like this one), after the round, the participants have the opportunity to "hack" other ppl solutions (which is, find some test that make the solution fail). If your solution gets hacked, you don't lose any points, but if you hack someones solution you get points.

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

      it's been 24 hours

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

So why are there so many implementation problems? I didn't have time to solve F because of spending much time on E.

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

in problem E some people use

int i= lower_bound(a[r].begin(),a[r].end(),c)-a[r].begin();

high=min(high,i); // tourist

and some use

high=min(high,i-1) // abc864197532

and both work

why not

int i= lower_bound(a[r].begin(),a[r].end(),**c-1**)-a[r].begin();

high=min(high,i);

plz some explain

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

    In Tourist's solution the valid range at the end is [low, high), for the other it's [low, high]. Finding c-1 may not work because of how lower bound works: it finds the suitable position for c-1, that position can have the value c as well. So you'll have to take extra steps to make sure you are avoiding a bad high index with c. Unfortunatly, I made a silly mistake somewhat similar to this. Inspecting my submissions may help understand this better.

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

Is there a way to check the code for plagiarism in contests?

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

I tried problem C using Segment Tree, where each node contains the substring in the interval [l,r], and a boolean value that stores the truth value of whether "1100" is present in the substring in range [l,r]. This can be implemented in O(|s|+q*log|s|). Submission Link: https://codeforces.me/contest/2036/submission/289723009. Why do I get a TLE?

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

    Building your segtree takes O(n^2) time because you are storing the whole strings in the node and combining two nodes takes O(n) time for the string concatenation. To solve this, try only storing the ranges [l,r] of the original string in each node. I think you can also implement it in a way that doesn't need to store the ranges.

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

why I still not have the rated score?

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

Is a recalculation still ongoing? I hope I didn’t pick Unrated participation. :(

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

    I usually wait for a full day with contest with a hacking phase. Be patient.

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

      So it’s normal for the Unrated value (equal to my actual current rating) to be as a placeholder on my rating graph until the recalculation is finished?

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

Where is the editorial ?

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

Good problems, maybe too much of implementation. I was close to solving F didn't have time left.

Nice work AUTHORS.

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

Worst contest ever.. like wth.. u accepted the solution during contest but after the contest u declared it wrong..!!!!!!!!!!

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

    Bruh, pretests passed does not mean it will 100% pass on the system test, it has always been like this on Codeforces.

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

Hi all, i participated in the contest, and solved 3 problems, but here it is only showing that I did 1? What could have happened? They were all accepted in the contest...

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

    System testing is going on, until it is completed, some questions will be in queue so it shows up as not accepted.

    Don't worry, after the testing you'll get to know which problems were accepted.

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

Does anyone have working solution for problem B in python. Mine got hacked.

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

first time FST TLE in test 41, bingo cell crossed rofl (painful af)

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

Why does it for ratings so long to be upgraded? Has been almost 24h after the contest.

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

Congrats on having the shittiest pretests so far.

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

Div.3 and Div.4 most important for the beginners. So more focused on those.

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

Can anyone point out the edge case I might be missing ?

My solution My approach is to see the difference corresponding value is making , change , before and after . Intially I am counting how many "1100" are possible then based on query I am checking all different scenarios .

Four for each (0 & 1).

Suppose for '0' , cases we loose a "1100" . If we place at first '1' or second '1' .

We gain if we have string like "1110" or "1101" where jth index is correspond to not un necessary 1s.

I am unable to figure what I missed .

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

    When you process the queries, you only check the substrings where i is the first or last character. But it could also be the second or third.

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

Judging by the speed of system tests, it seems Mike himself is validating every submission by hand

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

    because too many python sub got TLE, mine included... I'm thinking/testing ways to optimize after system test.

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

Is this game still keeping score

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

Thanks for the contest, loved it.

I just wanted to leave this here xD

best-meme-templates-16-copy

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

i have submitted solutions and they were accepted but why am i not still rated

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

Where is editorial

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

289515042

The time complexity is O(t(q+n)), right(ignoring the map queries). Then why is it taking 2999ms to run ? The time limit was 3s, so somehow managed to pass. How do I optimise it further ?

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

I wonder was it the edge case I'm missing with my solution? Submission

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

when rating upd?

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

My submission is 289489137.Why can not use find function? Why can't we use the find function? Isn't find O(n)? I see a lot of people are O(n).

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

Why are the rates not coming?

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

Why is the rating still not updated?

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

Great question E. Overall good contest.

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

The div was fine but my rate didn't change so ?

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

Thank you, pretests, for giving me false hope, only to nuke me in the final tests. Just a tiny bug that slipped by pretests but got me in the finals T-T. If only it was caught in pretests, I could've fixed it easily! T-T

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

Why did my submission for B get TLE after system testing 289495160 ? Looks the correct approach to me under the given constraints. I want to know to avoid this in future.

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

Hi can i ask why this code TLEs?

import sys
inputs = iter(sys.stdin.readlines())
TC = int(next(inputs))
for _ in range(TC):
import sys
import heapq
inputs = iter(sys.stdin.readlines())
TC = int(next(inputs))
for _ in range(TC):
    n, k = list(map(int, next(inputs).split()))
    b = dict()
    for i in range(k):
        b_i, c_i = list(map(int, next(inputs).split()))
        b[b_i] = b.get(b_i, 0) + c_i

    currSum, minHeap = 0, []

    for b_i in b:
        tc = b[b_i]
        currSum += tc
        heapq.heappush(minHeap, tc)
        if len(minHeap) > n:
            sc = heapq.heappop(minHeap)
            currSum -= sc
    print(currSum)
»
2 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Implementationforces

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

The worst problem statement award must goes to problem D

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

The worst problem statement award must goes to problem D

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

Solved problem B using python during the round, but after the contest it got a TLE. I implemented the same solution in C++ and it passed...

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

I need know who haked me

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

Can Anybody explain me the F solution pls? I really cannot get it. Thankiu :'))

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

Before starting div3 contest and after completing contest my reaction is totally different

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

submitted problem b in c++ with unordered map and it works :(

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

A bad Comment, as I dont know about this thing, Sorry :)

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

Hii

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

Hii