Gheal's blog

Codeforces Round #833 (Div. 2)
By Gheal, history, 2 years ago, In English

Hello, Codeforces! (or as we say in romanian, "Nu renunţ la tine niciodată")

I am glad to invite everyone to participate in Codeforces Round 833 (Div. 2), which will be held on Nov/12/2022 17:35 (Moscow time).

This round will be rated for all participants with rating lower than 2100.

You will be given 6 problems and 2 hours to solve them. All of the problems are authored by me.

I would like to thank the following people, without whom this round would not have been possible:

Here is the scoring distribution: $$$500−1000−1500−2000−2250-2750$$$

Good luck & have fun!

Edit 1: The round is over, the editorial can be found here.

Edit 2: Congratulations to the winners:

Div 1 + Div 2:

Div 2:

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

Comments Comments (209)
| Write comment?
»
2 years ago, # |
← Rev. 5   Vote: I like it +32 Vote: I do not like it

As a tester, holy fuck 2 romanian rounds in a row and 3 cars of polis wtf romania

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Wish for a positive delta & Good luck everyone...

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I guess you can become pupil in today's round if you solve A and B fast. Good luck!!

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thank you, buddy... Definitely, I will try. :)

      → Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Woahh an early scoring distribution OwO

→ Reply
»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

omg no green round

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope everyone good luck! :)

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Everyone best of luck,,,,

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I am looking forward to the problems of this contest, hoping to surprise me.

→ Reply
»
2 years ago, # |
  Vote: I like it -64 Vote: I do not like it

down vote me :)

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Best wishes for everyone

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

As a Romanian, I am delighted to see lots of Romanian rounds lately!

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Good luck!!!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to be a specialist in this round.

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

All the best everyone.

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hoping to be green in the orange round. Bad luck doesn't allow. Hope so this time maybe i will :)

→ Reply
»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

best of luck everyone. Will meet tommorow.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope next round after this one will be green again

→ Reply
»
2 years ago, # |
  Vote: I like it -28 Vote: I do not like it

unacceptable contest! why can romanians make contests now on codeforces? does no one know how things run among romanians when it comes to programming, especially competitive programming? this is deeply disturbing and I will reconsider whether I want to continue with this website or not. cheers but look into it

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    No one wanted you to join the contest

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    unacceptable contest! why can humans make contests now on codeforces? does no one know how things run among humans when it comes to programming, especially competitive programming? this is deeply disturbing and I will reconsider whether I want to continue with this website or not. cheers but look into it

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      unacceptable contest! why can capybaras make contests now on codeforces? does no one know how things run among capybaras when it comes to programming, especially competitive programming? this is deeply disturbing and I will reconsider whether I want to continue with this website or not. cheers but look into it

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

        unacceptable! why can? does no one know how things run? this is deeply disturbing. cheers

        → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Good luck everyone, hope for Candidate Master

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Good luck to everyone!

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I intent to become green today!

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I can see that you have been consistent for the past few days. Hope you reach green, good luck bro!!

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Google Kickstart Round H and Div.2 Codeforces contest at same time... :(

(*P.S. I'll go with Codeforces):))

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    they literally have a 12 hr gap in their start time...

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Damn my mistake..yeah u are right i thought it PM instead o AM

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

among us

→ Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Hey, my neighbour is Romainian, too. Good luck.

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What color is your codeforces account? ♫ Tourner Dans Le Vide ♫

→ Reply
»
2 years ago, # |
  Vote: I like it -26 Vote: I do not like it

why div2 ?

i want div3 or 4 for become pupil

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

gl

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck!(or as we say in romanian, baftaaa baaai)

→ Reply
»
2 years ago, # |
  Vote: I like it -17 Vote: I do not like it

liis Gang!

→ Reply
»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Time to be a specialist.

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Best of luck Everyone.

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Wish for a positive delta & Good luck everyone...

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it -31 Vote: I do not like it

Mathforces with Awesome round :(

→ Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Time to be a pupil.

→ Reply
»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

B is soo tough...

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    no we are just retarded

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    or maybe we need to improve ( i mean look at the standing alot of peoples solved it)

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Corrected: lot of cheaters solved it.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if you can't solve some problems but a lot of people can

        don't call them cheaters make yourself better

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Totally agree, but one solution video for B had over 1.1K views on YouTube before the contest was even over.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            don't get sad for some cheaters they don't ever get improved but you can

            → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We have skill issue smh

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have never felt more retarded in my life while solving B.

getting WA 3 times because of being a dumbass only

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Again leaked solutions on YouTube... (https://www.youtube.com/channel/UChJvx-TFKQ5t-T6YyPf1tsw, https://www.youtube.com/watch?v=0x9kKxfqLr8)

This solution for problem B has 1.1K views and the contest is not even over yet!

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can't solve B lol :((

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unbalanced round.

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In problem C, my code with std::map got AC but with std::unordered_map got TLE at pretest 7... WTF??

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here you go. https://mirror.codeforces.com/blog/entry/62393

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same got TLE, in python...

    Tried collections.Counter, defaultdict and all such, but nothing worked...

    It seems that O(n) solutions won't be accepted. Maybe I just need to work out an O(log(n)) solution next time...

    Viewing the acceptance rate, it seemed that many people had similar issues.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Okay, seemed that they also had a hash hack test case for Python. Great to learn a new lesson!

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Anti-hashing testcases. I was aware of that...

    Basically there are some testcases that purposefully break solutions that use hashing.

    More details

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in the worst case, the time complexity for all the operations in an unordered_map is O(n)

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C ?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Construct a prefix array $$$p$$$. Then you can break the original array into segments based on the positions of $$$0$$$s in it. Each segment starts at a $$$0$$$ and ends at the index before the next $$$0$$$. Suppose the positions of $$$0$$$s in $$$a$$$ are $$$z_i$$$, then the maximum score you could get from subarray $$$[z_i, z_{i+1}-1]$$$ is the maximum frequency of any element in the subarray of $$$p$$$ from $$$[z_i,z_{i+1}-1]$$$. I implemented this by using a resetting the frequency count every time I hit a zero, and then finding the maximum among the frequencies when I reached the next zero. Also, any $$$0$$$s in $$$p$$$ that occur before the first $$$0$$$ in $$$a$$$ have to be counted as well. Hope this helps!

    → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How is D done? I was thinking some SAT solver possibly but couldn't think of a way to calculate divisibility rules of $$$d$$$ efficiently.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    My Solution for D:

    Check no solution:Note $$$cal(x)=max(i),2^i|x$$$,if $$$cal(d)>min(cal(a),cal(b))$$$,no solution.

    Otherwise,Let's construct the solution.

    First,let $$$d»=cal(d),a»=cal(d),b»=cal(d)$$$,calculate the $$$x$$$ for the new $$$a,b,d$$$.When outputting the answer, we only need to output $$$2^{cal(d)}x$$$.

    How to construct such $$$x$$$?The key point is make $$$x=(2^{key}-1)+2^{key}X$$$,($$$key=30-cal(d)$$$).

    This is actually a problem of solving congruence equations:$$$(2^{key}-1)+2^{key}X=0(mod d)$$$,use ecgcd to get such $$$X$$$.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B really shocked many!!!

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Was pretest 8 of C a hash hack?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Lol, I rewrote my solution to c++ to pass 8
    Didn't even think we could have hash-hack pretests

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You're right

    Well, It is nice that they included it in pretests I guess.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I suspect it was, I only passed pretest 8 after adding code specifically to stop hash hacks (mainly xoring each value in the dictionary by a predetermined random value)

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What was the intended solution for D? I had a solution of $$$O(T * \sqrt d)$$$ but it TLed.

Edit: Ahh, intended was $$$\log d$$$ per test.

Link: 180645422

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it
    1. You consider base 2 factors independently — if 2^x divides d, then both a and b must have x clear least significant bits
    2. Now let d be not divisible by 2. We want to use 30 most significant bits, because they are enough. Let's say that a | b has remainder y over d. then we are looking for number x, such that x * 2^30 = d — y mod d. So x = (d — y) * (2^30)^(-1). Then we return x * 2^30 + (a|b)
    → Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

how to solve D? i got stuck at the part where you have to find some modulo using some certain bits ;-;

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really good E! I like this problem of dp on cartesian tree.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I normally solve A, B, C, this time I only solved A. All good, go next

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C? I had ideas with dynamic programming but I'm tangled up in my thoughts

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The main idea is to split the original array into segments based on the positions of $$$0$$$s. Each segment starts at a $$$0$$$ and ends at the index before the next $$$0$$$. Then I can perform the operations in such a way that each $$$0$$$ only affects its own segment. Construct a prefix array $$$p$$$ and in each segment, find the maximum frequency of occurrence of any element in $$$p$$$ — That will be the score of that particular segment. Also count all $$$0$$$s in $$$p$$$ that occur before the first $$$0$$$ in $$$a$$$. Hope this helps!

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B can use the enumeration algorithm, this surprised me.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish I had time to look at F but B took so long because I didn't realize brute force passes it :(

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And here I was thinking that it had to be done using 2 pointer+ sliding window

    Then I realized it could be done with brute but was unable to find the maximum times inner loop should work :(

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also thought it was two pointers at first and wasted so much time XD

      → Reply
»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

In my honest opinion it was the hardest Div 2 that I participated, I could only solve 1, and I lost expert :'v, but I will learn new concepts and that it is great

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How a simple brute force is getting accepted for B?? what is the time complexity of the solution.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$O(100n)$$$

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It seems the intended solution is to bruteforce with one simple observation: By the pigeonhole principle, a substring of length $$$101$$$ would have at least one character with at least $$$11$$$ occurrences. So we only have to check for substrings of length upto $$$100$$$, because lengths above that are guaranteed to be non-diverse.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      wow giving contests regularly and upsolving is the best way to learn topics thanks i would never have understood pigeonhole principle better than this time .

      → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Quick system test!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C . Anyone ?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The main idea is to split the original array into segments based on the positions of 0s. Each segment starts at a 0 and ends at the index before the next 0. Then you can perform the operations in such a way that each 0 only affects its own segment. Construct a prefix array $$$p$$$ and in each segment, find the maximum frequency of occurrence of any element in $$$p$$$ — That will be the score of that particular segment. Also count all 0s in $$$p$$$ that occur before the first 0 in $$$a$$$. That will give you the answer.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did A. Then looked at B couldn't solve it initially. So I skipped went to C. Tried it for about an hour. Then came back to B, after staring at it for a while saw that there was a pigeonhole principle angle which brought the solution under time limit, so did it that way PH principle: ceil(n/h) is the minimum put in h groups if n values has to be distributed among it. so 100/10 -> 10 and ceil(101/10) = 11 which means there is no substring out there of length 101 that can satisfy the conditions. So you can test the substring lengths accordingly. Worst case it goes to 10^5*10^3 = 10^8 which comes under the 1 second condition, 10^3 because 100 values to be checked and say we check all value counts from 0-10 in that case.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    even better: 100 is only 10^2, not 10^3

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I counted the time taken for going through the 0-9 count values for every one of substrings. Are you counting that to be constant?

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, everyone. I have given this contest( Codeforces Round #833 (Div. 2)) and got a score of 464. But still, I am unrated. Can anyone plz say why I am still unrated?? N.B. I am new in codeforces.:):) Thanks in advance..

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My Solution for D:

Check no solution:Note $$$cal(x)=max(i),2^i|x$$$,if $$$cal(d)>min(cal(a),cal(b))$$$,no solution.

Otherwise,Let's construct the solution.

First,let $$$d»=cal(d),a»=cal(d),b»=cal(d)$$$,calculate the $$$x$$$ for the new $$$a,b,d$$$.When outputting the answer, we only need to output $$$2^{cal(d)}x$$$.

How to construct such $$$x$$$?The key point is make $$$x=(2^{key}-1)+2^{key}X$$$,($$$key=30-cal(d)$$$).

This is actually a problem of solving congruence equations:$$$(2^{key}-1)+2^{key}X=0(mod d)$$$,use ecgcd to get such $$$X$$$.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +32 Vote: I do not like it

D is sooooooo cute!!! (Though there is a gap between C and D)

hint 0

hint 1

hint 2

hint 3

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This should have been included in the official editorial. I think most of the solutions came from this intuition. Hats off man!

    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

B is run in time O(100*n), beacause all numbers [0:9] as a maximum frequency in one sub-string is 10 if it's frequency is greater than 10, then second loop will stop, because no sub-string will be made as no numbers of distinct numbers from [0:9] will exceed frequency of 10. i like this problem.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can i ask why in your solution you have used i+228 if 100 is the maximum length of valid substring?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      My friend told me of this (i+228), but then i reach the main concept. :)

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        When you say your friend told you, do you mean during the contest?

        → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        or maybe because the video with leaked solution on youtube has i + 228?

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -9 Vote: I do not like it

          This is the problem of taking an hint from a friend during the contest, thank you.

          → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did so many people solve C? I solved D and E but didn't solve C. Are there any good ways to come up with the solution?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I learned main idea when study IOI 2002 Batch Scheduling. This problem's main topic is CHT but provides one observation related to the prefix sum. Other implementations were learned while upsolving code forces.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It was quite simple to come up with by looking at the prefix sum array and the zeros ;-)

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro maybe u were just overcomplicating it. C is quite simple as you can probably tell from the editorial (i havent read it yet tho)

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

180648134 My overcomplicated solution for B which I was restraining myself to implement till the final minutes of the contest.

→ Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

B was leaked by a youtuber. Here is the link. https://youtu.be/0x9kKxfqLr8

You can clearly see its comments was 1+ hour ago from now. I am giving some screen shots.

https://drive.google.com/drive/folders/15e5mFpLw8ESoqK-0A6WXDSxGgzDqIjTV?usp=share_link

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    and when i look at the solutions many people are suspiciously using that i+228 logic, is there actually any reason for it to be i+228 or is everyone just copying this video?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      NOTE: the solution just needs to be i+100 in the worst case thats why this specific number is quite suspicious

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      LOL if it is 228 then these subs are from the same sources.

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I failed C for mistakenly specifying the wrong type for the map iterator like a complete dumbo. Why live? Please host another competition soon I need to avenge my stupidity.

Btw is there a way to somehow apply for retroactively rejudging solutions in cases like this? I will respect and understand if not, but could be very appreciated!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what a nice round! thank you

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Congratulations being a fifth place.Jarif_Rahman

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

When speaking of B, if I quote Joma Tech : "Because of pigeonhole principle, child's play"

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve C ? I read the editorial and I still can't make sense of it, Also does any one know how to start solving C problems this is my 10th round in which I only solve A, B and fail C :(

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If there are more than 10 * 10 + 1, we can realise that there is at least one digit that appears more than 10 times. It is because there are at most 10 digits, and if those digits doesn't appear more than 10 times, it means that there are at most 10 * 10 numbers, which contradicts what we are saying. (I think the rest is the most delicious part of the problem, so i won't say it...)

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Start with the simplest case:

    $$$a[x]=0,a[1],a[2],...,a[x-1]≠0,a[x+1],a[x+2],...,a[n]≠0$$$.

    How to determine the value of $$$a[x]$$$?

    Case1:make $$$a[1]+a[2]+...+a[i]=0$$$,the contribution is $$$1+cnt$$$,$$$cnt$$$ is the number of $$$y>x$$$,which make $$$a[y]+...+a[n]=0$$$.

    Case2:make $$$a[1]+a[2]+...+a[i]=k$$$,the contribution is $$$cnt$$$,$$$cnt$$$ is the max number of $$$y>x$$$,which make $$$a[y]+...+a[n]=k$$$.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, I get too nervous while giving contests. Any tip? I feel like I have enough knowledge to keep on solving A, B, C but I get too nervous while the contest that I mess up.

→ Reply
»
2 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

Awesome problems(at least A-D). But it's sad, that completely stupid 2e9 solution passes pretests and falls on systests. 1e9 is AC

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was C leaked like B and A somewhere? I feel like this C is harder than the usual C div2

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B took much longer time than C.I solved B just one second before this contest over.But I still lose a good oppurtunity to become expert.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I believe question B should have been a C and question D should have been an E

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In D, is there any reason there are two numbers given (a and b)? I think the problem works with a single number just as well, or am I missing something and it becomes very easy with one number?

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

    I think you're right. If there were an easier way to find $$$x$$$ for only one number $$$n$$$, then the problem can be solved by finding $$$x$$$ for $$$n:=a\vert b$$$?

    Adding more numbers doesn't increase the difficulty.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Would you please review my C? My code is bad because I am messed up during the contest. Only solve() is meankngful. Others are trash.

Fail at no.4227 at test2. And another failed contest.

https://mirror.codeforces.com/contest/1748/submission/180647355

→ Reply
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

There is a case of cheating in the problem B A solution is available during the contest on YouTube https://youtu.be/0x9kKxfqLr8

Matching solutions:- https://mirror.codeforces.com/contest/1748/submission/180650292

https://mirror.codeforces.com/contest/1748/submission/180650184

https://mirror.codeforces.com/contest/1748/submission/180649269

https://mirror.codeforces.com/contest/1748/submission/180646072

https://mirror.codeforces.com/contest/1748/submission/180646346

https://mirror.codeforces.com/contest/1748/submission/180646263

https://mirror.codeforces.com/contest/1748/submission/180646094

https://mirror.codeforces.com/contest/1748/submission/180645940

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I registered 20 minutes after the contest started will it be rated?

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Really unacceptable! Isn't the codeforces rule that only pupil or below can set a round? Why can an orange coder set a round? The experience of this round will definitely be bad! I can't accept it at all!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution on C is uphacked for TLE. The cause seems to be the usage of unordered_map. See 180668799 and 180668851. The only difference is that the first one uses map and accepted, while the second one uses unordered_map and TLE.

Is unordered_map really that bad on performance? Am I using it in a costy way?

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Weired. I find some benchmark showing that std::unordered_map outperformed std::map on every use case. I have totally no idea what is going on here.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm changing compiler from g++ to MSVC resolves this issue, interesting... See [submission:https://mirror.codeforces.com/contest/1748/submission/180670005] which is exactly the same code as the one getting TLE I mentioned before. but accepted with MSVC.

      Looks like it's not my fault. Maybe there's something wrong with the compiling flags?

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can refer to this : https://mirror.codeforces.com/blog/entry/62393

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      Ouch, the hash function, of course... Thanks a lot for your reply, and the guy below too.

      → Reply
»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

When we will get rating changes?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    When all cheaters are punished. :)

    → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

where rating where

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why codeforces don't make any hack phase in the regular rounds about 1 hour or even permit any rate account to uphack any solution ?
below there are huge number of hacks after the end of the rounds.
codeforces round 833
codeforces round 830

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Dang I cheated but my rating wasn't taken away...

Well yay my rating got removed

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem B why do we do (fr[s[j] — '0'] == 1) what does — '0' do here and how will it be equal to 1.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$s[j]$$$ is a character and we need to transform it into a number so we can use it as an index for the array, we can transform by subtracting $$$'0'$$$ from $$$s[j]$$$ that will result in the number itself.Take a look at the $$$ASCII$$$ table you will find that the result of subtracting the corresponding $$$ASCII$$$ code for each digit and the $$$ASCII$$$ code for $$$'0'$$$ will result in the digit itself, now we can use that number as an index for the array.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you show me an example with the string, "1011101"?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How would subtracting a character with '0' result in the number?

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Take for example the character $$$'1'$$$,How can we get the number $$$1$$$ from the character $$$'1'$$$ ?

          The $$$ASCII$$$ code for the character $$$'1'$$$ is $$$49$$$,

          The $$$ASCII$$$ code for the character $$$'0'$$$ is $$$48$$$,

          $$$ '1' - '0' = 49 - 48 = 1 $$$.

          This is how we can get the number $$$1$$$ from the character $$$'1'$$$, This can work with any other characters $$$('2','3','4',....)$$$.

          Note that this only works with characters and not strings (you can't get the number $$$"1011101"$$$ using this method), instead you can get each character at a time and calculate the number based on its base.

          → Reply
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Personally, I think the problems F are not very difficult. They are very good. They do not involve advanced algorithms, but simple thinking problems

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

good morning :)

→ Reply
»
2 years ago, # |
← Rev. 4   Vote: I like it -12 Vote: I do not like it

..

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I got this message from codeforces:

Attention!

Your solution 180610916 for the problem 1748A significantly coincides with solutions nilan12/180610916, vishu.ut/180611741. 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://mirror.codeforces.com/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.

This is probably due to both of us using the PyRival template and the problem being quite simple; how should i resolve this?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By doing precisely what you did! Simply comment on it with all the details, like you did. Your rating should come back soon.

    Although it is very sus that the two submissions are less than a minute apart and the code is ridiculously similar... it is too simple to know if you cheated or not.

    In the future, be safe and make your own templates.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i got none message and i loss my rating,how can i sovle it ?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my rating someting loss sometime back. what happened?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think it may just be a temporary roll back caused by either cheaters or wrong cheating detections. I believe that this would be solved in a few hours (or days).

      → Reply
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Ok so I submitted 180618741 in 9 minutes, and you have disqualified me for a generic Russian number 228 in my solution? I don't use any cloud IDE, neither do I have a clue why a widespread leaked solution has 228 in it, I lost about 80 pts in that contest, but please be so kind to cancel the disqual

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There were only 3 successful attempts on B in my room, and the only locked one was made by a random Indian guy at 00:42:02. I haven't checked completely but looks like every other submission was made strictly after this particular moment. Thus, I strongly believe that my solution had been leaked through locking + hacking, akm07 do you have something to tell us about?

    MikeMirzayanov could you also take a look, please?

    → Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why is the rating cancelled?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, I recieved this but obviously it's not me. What happened?

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I have received a message that my solution 180643841 to the problem 1748C significantly coincides with solution pqr0xffffff/180627756. But I wrote the code myself, without violating the competition's rules, and I didn't post it anywhere. I have compared both solutions after I got the message, and it is clearly visible that the codes were written independently. The part of code that looks most similar is calculating prefix sums, which is a basic and very commonly used technique, and is written the same way by many people. One more thing that occurs in both implementations is using maps to solve the task, but the most important part differs — my solution uses one map, while the other solution uses two; my solution does some iterations over the map inside the "for" loop, and the other doesn't, etc. I hope that this situation will be reconsidered and I will get correct verdicts to my submissions from the contest, instead of 'skipped'.

→ Reply