m3tr0's blog

By m3tr0, 5 weeks ago, translation, In English

Hi Codeforces!

We would like to invite you to participate in Codeforces Round 984 (Div. 3) on Nov/02/2024 17:35 (Moscow time). You will be given 7 problems and 2 hours and 15 minutes to solve them. The penalty for an incorrect submission will be 10 minutes. There may be interactive problems in the round.

The round will be ruled according to the standards of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, there will be a 12-hour phase of open hacks. After open hacks all accepted solutions will be rejudged on successful hacks. We've tried to make decent tests — just like you, we'll be upset if you have dropped solutions after the end of the contest.

Reminder that only trusted Division 3 competitors will be included in the official results table. This is a forced measure to combat unsportsmanlike behavior. To qualify as a trusted Division 3 competitor, one must:

  • participate in at least five rating rounds (and solve at least one problem in each of them)
  • not have a point 1900 or higher in the rating.

Whether you are a trusted Division 3 participant or not, if your rating is less than 1600, the round for you will be rated.

The tasks were authored and prepared by a team consisting of Seny, eugenechka.boyko.2_0-0 and myself.

The round is based on the recent Lipetsk Team Programming Olympiad for school students. Please note that if you are a participant of the Olympiad, you are not allowed to participate in this round. Thanks to the coordinator of this Olympiad myav and the author Small_machine, whose tasks were not included in this round due to their high complexity.

We thank very much:

We hope you find the problems interesting. Good luck!

UPD.: Editorial

  • Vote: I like it
  • +75
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    the contest was BS

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you submitted before timer run out, then solution will count

»
5 weeks ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        About the results table of the round.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              I pray that we will not have an unrated parc. in div2/div1.

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              But we can do something like you can't create more than 1/2 accounts from 1 mac-adress.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hope to enjoy this round

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

»
5 weeks ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

Finally! An adequate round without pendochinese authors!

With love to my kittens

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

promlems❌ problems✅

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

aiming for pupil this round

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

No interactive problems pls T_T

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone :)

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Hope to be expert soon.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

wish to be pupil after this round.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Спойлер
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As a F1 fan i hope Norris locks up into turn 1 tomorrow and comes P11

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

specialist plssssssss codeforces

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I read editorials for the contest?

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

I hate Div3...

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

I hate C

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

nice tasks

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

implementation forces

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

What is the purpose of problems like D?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    implementation practice ig

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      D was too direct problem, and don't really requires anything other than some implementation skill. I think problems that only ask you to impelemnt something should be avoided in a rated round, or at least in Div.3 A,B.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    i felt the same, the contest was so much implementation based. i just couldnt implement D

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    It is possible to code D neatly, my code isn't heavy to implement.

    CODE: 289531869

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Me after reading D: wtf is this!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I spent wayyy too much time handling this Test Case lol

    51
    43
    
»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it +20 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          just put your $$$\LaTeX$$$ commands between '$'

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          yeah, why not! just put credit somewhere :)

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what (i,k) mean?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

woah!!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      NGL, your solution for Problem-E scares me but I got the approach
      Thanks :)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      its not necessary though, map's constant is heavy, might be better to just binary search over range n

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    probably your solution exceeds the requests limit

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also check this condition. Waiting for open tests to confirm that I am acoustic)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 - Отгадай число, https://mirror.codeforces.com/blog/entry/45307

      My guess is that whoever coded the validator for 2036-G - Библиотека Магии 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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Tried so hard,

Got so Far,

But in the End,

got 6k rank .....

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah haha, that was the issue thank you

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did you come up on your own with this case?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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)

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)).

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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)

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

implementation forces lol

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Implementation, Implementation and only Implementation.

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

interesting F

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Implementation forces sucks...

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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...

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Conclusion No matter the contest people will cry (:

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -22 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    Code
»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

ImplementationForces

»
4 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

Problem F sucked.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

BS forces

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

BITWISE-forces :D

»
4 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Based, +1 for the heads up

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      This guy is gold in taking criticism.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C ? what is the best complexity ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

In Problem G, why is this (https://mirror.codeforces.com/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?)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you create a vector of k in q queries -> 10**10 complexity

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I solved it now. I'm so sad man, how did I not see that?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        btw why you use alt? could've comment by the main acc...

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are iterating over the whole K's in each query consider only what is mentioned in the current query

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

implementationforces

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you very much for the contest.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Time for me to go back to newbie.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -51 Vote: I do not like it

Div3s are great contest...

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

submission

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone please hack this https://mirror.codeforces.com/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??

»
4 weeks ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it
A Python script to test solution on problem G
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 .

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you give hacking test.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try this, the output is 1

    1
    8 4
    1234
    1234
    1234
    1334
    1434
    1534
    1134
    1234
    
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -9 Vote: I do not like it

    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)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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]))
    
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    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)

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

As a hacker I hacked 50 solutions

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    upd: I hacked myself :)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The pretests passed without checking l>r?? LOL thats wild

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    damn, now I have to pray I dont get FST after hacking phase rofl.

    P/S: btw how do you realize your mistake after contest?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I just looked at everyone else's solution and realized I didnt check l>r

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      Note: im RE_Prince's alt acc

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    And it is NOT funny :)

    P.S. I upvoted u

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      lol i found more

      289611332

      (using upper bound for both LOL) what are these pretests I cant :sob:

      be glad you didnt do this lol

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +15 Vote: I do not like it

    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);
    }
    
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 :(

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really enjoyed F and G :D

»
4 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

I wish i can be tourist after this

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thank you so much for the answer.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it's been 24 hours

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/2036/submission/289723009. Why do I get a TLE?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

Nice work AUTHORS.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Congrats on having the shittiest pretests so far.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 .

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For 0 , when it is placed at 1st or 2nd position we loose "1100" as it is converted to "0100" and "1000" corrspondingly .

      Now for gain we gain on followin cases "1110" if 3rd position is the index where we place '0'.

      Similarly we gain for following case "1101" if 4th position is the index of placing '0'.

      This is what I am doing , covering all the 4 charactes .

      Similary I am doing for 1 also .

      Any edge case that I am missing , I want to know :).

»
4 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this game still keeping score

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for the contest, loved it.

I just wanted to leave this here xD

best-meme-templates-16-copy

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is editorial

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Issue is in creating temporary strings in each query that is taking O(n). That makes the time complexity O(tqn).

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

when rating upd?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Why is the rating still not updated?