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

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

Привет, 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.: Разбор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        About the results table of the round.

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится +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.

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

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

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

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

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

hope to enjoy this round

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

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

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

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

i went to daycare with testers!!!

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

Finally! An adequate round without pendochinese authors!

With love to my kittens

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

promlems❌ problems✅

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

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

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

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

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

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

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

justlm orz

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

aiming for pupil this round

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

No interactive problems pls T_T

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

Good luck everyone :)

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

Hope to be expert soon.

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

good lucky!

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

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

  • »
    »
    3 недели назад, # ^ |
    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.

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

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

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

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

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

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

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

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

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

I am Vladosiya fan

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

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

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

Is E maximum flow ?

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

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

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

wish to be pupil after this round.

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

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

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

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится 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 недели назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    use binary search. OR operation result is always greater than both operands, so flow increases over each country within a region.

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

      Dear Lord, now I understand the solutions for E
      You use bisect (Binary Search for Python) to get the valid ranges and then min-max them to get the answer

      This works because OR operation result is always greater than both operands.
      Cool way to approach it. Thanks :)

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

    use a map to contain the query of "r" changes, only check those columns to avoid TLE.

»
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 :)

    • »
      »
      »
      2 недели назад, # ^ |
        Проголосовать: нравится 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.

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          2 недели назад, # ^ |
            Проголосовать: нравится 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

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

      • »
        »
        »
        »
        3 недели назад, # ^ |
          Проголосовать: нравится +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.

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

    • »
      »
      »
      3 недели назад, # ^ |
        Проголосовать: нравится +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?

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

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

when rating upd?

»
3 недели назад, # |
  Проголосовать: нравится 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).

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

Why are the rates not coming?

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

Why is the rating still not updated?

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

Great question E. Overall good contest.

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

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

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

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

»
3 недели назад, # |
  Проголосовать: нравится 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)
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Implementationforces

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

The worst problem statement award must goes to problem D

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

The worst problem statement award must goes to problem D

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

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

I need know who haked me

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

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

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

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

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

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

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

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

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

Hii

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

Hii

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

I submitted my solution for problem 2036E in the recent Div3 contest held on November 2, 2024. My solution was flagged for violating Codeforces’ plagiarism policies. I am writing this comment to explain to the organizers that it was purely coincidental that, out of 32,995 participants, my solution was similar to that of 30 other participants — a similarity rate of just 0.09%. This minor probability of similarity can occur, as the approach to the problem was straightforward; while the logic might resemble other solutions, the variable names and their handling in my code differ significantly.

All participants with similar solutions, including myself, used C++ to submit the answer, as the problem required an approach that naturally aligns with a deque-style method using specific variables like n and k, as outlined in the prompt. While the overall approach may seem similar, the specific handling of elements within my code is distinct.

This situation reflects poorly on the sponsoring team, as it discourages participants who invest their time in the contest only to receive a plagiarism penalty for such a negligible similarity of less than 0.1%. I am sharing both my code and that of another user to show that, although we followed a similar approach, the variable naming and output methods in my code are unique. My variable naming style remains consistent across contests, demonstrating my approach to problem-solving. Additionally, given that solutions often follow a linear sequence, many steps inevitably look similar across languages, contributing further to these coincidences.

My code: Submission link: https://codeforces.me/contest/2036/submission/289574722 Second code: Submission link: https://codeforces.me/contest/2036/submission/289549723

Msg I received from team : "Attention!

Your solution 289574722 for the problem 2036E significantly coincides with solutions kanose7734/289549723, Sana_Azeem5/289550646, Yasin_MalekAlaie/289551343, yaduvanshi_23/289552002, adityavermanov/289552027, hkm_12345/289552059, priyajgangwar1/289552369, competitivecoder96/289553096, TheFatCoder/289553363, WrongAnswerAtTest1/289554884, gopi2005/289555485, tsundere_/289556958, meetanupam/289557228, Coderv55/289557451, addme/289557594, sanhayu546/289557896, Barun34/289558238, faruk_kk/289558267, king2008/289559182, Thavar/289559273, Surgeon_of_Hell/289560879, Devendra_19/289561369, chandan_7499/289562386, java_unfriendme_/289563028, Nooooooooooooooobbxhj/289563164, rito_b/289564867, Aman6523/289565402, tleTauhid/289565714, Ashwinikumar23/289565761, viveksahus9368646191/289565963, Hitler_10/289566931, Proff_Shawn/289567180, hassan.masry1979/289567442, flamingo123/289568361, rohangarg1446/289568731, thecodereal55/289569272, i.ravi.pratap/289569547, Abhishek_Das_003/289569975, code_100m_amgf/289571326, yuv5120/289571633, anjali_4876/289571788, ayushisharma04/289572399, ashrafbhai005/289572862, -333/289572907, garvit27/289574722, Satyam8932/289575263, ashrafulalam005/289576543, purvk/289577280, akshar_bansal/289578363, Parthavinolover/289587465, Er/289588574, SinC_Nohara/289589042, ill.soul/289589212, 015-Daniil-M-2027/289589305, im_subhash/289589644, sanskardhyani98/289591022, yerwxzq/289591708, Tanishq_codegrandmaster2/289592436, Om3466/289594176, Jayesh_02/289594259, Tah1rTheT1ger/289594506, kaido7/289594658, Mubtasim_92/289595881. 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.me/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."

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

    This same thing happened with me too but on question 2036C. My similarity rate was a ~0.3% but this is still low to possibly consider my submission a flag. This was purely a coincidence as using sets is a common way to solve this problem. Additionally, having similar variable names is bound to happen due to coding conventions. People are bound to have the same logic in a problem and this is a case where this happened.

    One of my previous submissions for the same problem, 289537477, was in python where I realized that my logic was correct but I needed to work on decreasing the time complexity. This is why I then wrote my solution in C++ because its compiler is faster and used sets to further decrease my time complexity. As a person who knows multiple programming languages, I tend to switch between python and c++ depending on the context of the problem.

    I completely agree with you about how this discourages people in participating in contests. Due to this flag, my hard work in my past contests has been lost and I am forced to start over again. This is definitely a problem with the team and my solution should not be flagged because of this coincidence.

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

      Agreed. It's unfortunate it happened with you as well. Hope so, m3tr0 and his team will look into this

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

        Hi. Neither I nor the other setters have anything to do with bans for plagiarism. That is done by the Codeforces administration. I do not belong to them and I cannot consider such appeals in any way — I am a user like you

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

i got an email signifying how my solution https://codeforces.me/contest/2036/submission/289553791 matched with these solution https://codeforces.me/contest/2036/submission/289555438 which are written in c++ and mine solutions are written in java? how are they matching??? m3tr0 look at this and my solution is also sent before these solutions.

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

    Hi. Neither I nor the other setters have anything to do with bans for plagiarism. That is done by the Codeforces administration. I do not belong to them and I cannot consider such appeals in any way — I am a user like you

    I'll pass on that there are yours and other such appeals in the comments of the announcement, but I'm sure they're already aware of them

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

Ratings rollback, looks like cheaters got caught. Very soon we'll have 10K people solving A to F.

Edit: either the world is full of geniuses or there is rampant cheating, not this round per se but in other roudns the number of people that solve C, D is just too high. They far exceed FAANG interview questions. Maybe someone can explain this mystery.

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

Hi, I got an email today that my sol- Shivagya/289542631 coincides with theblueman/289570204. If you take a glance at the question then you will realize that the approach to the question is pretty straightforward and most of the submissions have used the same approach. So why only my solution is supposedly marked for plagiarism?? I hope the issue will be resolved soon. Here's exactly what I received-

"Attention!

Your solution 289542631 for the problem 2036C significantly coincides with solutions Shivagya/289542631, theblueman/289570204. 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.me/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."