Gheal's blog

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

A — The Ultimate Square

Author: Gheal

Hints
Solution
Code (C++)
Rate Problem

B — Balanced Substrings

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

C — Zero Sum Prefixes

Idea: Gheal, Solution: IgorI

Hints
Solution
Code(C++)
Rate problem

D — ConstructOR

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

E — Yet Another Array Counting Problem

Author: Gheal

Hints
Solution
Code(C++)
Rate problem

F — Circular Xor Reversal

Idea: Gheal, Solution: IgorI

Hints
Solution
Code(C++)
Rate problem

If there is anything wrong or unclear in this editorial, feel free to ping me in the comments.

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

Comments Comments (121)
| Write comment?
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Good Round! Thanks for the fast editorial!

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

    bro how to achieve graph like you what are you doing

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

      They had probably done CP on other websites before starting on Cofedorces, or at least they had had experience with math and problem solving in programming, maybe also some algorithms.

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +26 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\space d)$$$,use exgcd to get such $$$X$$$.

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

    Here is another solution for D:

    If $$$min(lsb(a),lsb(b))<lsb(d)$$$, there is no solution. Because $$$lsb(d*k)>=lsb(d)$$$ so their $$$lsb$$$ can never be equal. Hence, they can't also be equal.

    Otherwise; let $$$ans = 0$$$ initially, we want to fill bits of $$$ans$$$ such that it will be multiple of d, and $$$ans$$$ will be *superset of $$$a|b$$$.

    Let's iterate over bits of $$$ans$$$ $$$0$$$ to $$$29$$$

    If $$$i$$$'th bit of $$$ans$$$ is $$$0$$$ then add $$$d * (2^{i-lsb(d)})$$$ to $$$ans$$$. Now that bit will be $$$1$$$ and it will contain $$$a|b$$$ anyway.

    Since $$$d$$$ has at most $$$30$$$ bits and our target is to fill first $$$30$$$ bits and there must be an intersection, our answer will require at most $$$30+30-1=59$$$ bits and this fits constraints!

    Here is my submission.

    (*Note : $$$X$$$ is superset of $$$Y$$$ if $$$Y$$$ is subset of $$$X$$$.)

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

      tolbi "If i'th bit .... contain a|b anyway." Can you please explain this line? Like how did you come up with this approach?

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

        If $$$i$$$'th bit of $$$ans$$$ is $$$0$$$, when we add $$$d*(2^{i-lsb(d)}$$$ to $$$ans$$$, actually we shifted $$$d$$$ to intersect $$$lsb(d)$$$ with that bit. Since $$$lsb(d)=2^{i}$$$ and $$$2^i$$$ & $$$ans = 0$$$ after shifting, if we gather them then $$$i$$$'th bit will be $$$1$$$. Since we filled first $$$30$$$ bits with $$$1$$$, it will be superset of $$$a|b$$$.

        Actually first $$$30$$$ bits except bits that is smaller than $$$lsb(d)$$$ are $$$1$$$. But since $$$lsb(d) \le lsb(a|b)$$$, it is meaningless. There is no bit such that $$$bit$$$ & $$$(a|b) = 1$$$ and $$$bit$$$ & $$$ans = 0$$$. I wrote above comment incorrectly you must to start from $$$lsb(d)$$$ instead of $$$0$$$ but when coding it, (1LL<<bit) gives $$$0$$$ if $$$bit$$$ is negative. So you can start from $$$0$$$ too if you used shifting that way.

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

Problem D can also be solved using Chinese Remainder Theorem. First step is the same as stated in solution given above: proccess cases, when answer is -1, and then you can just find X, s.t. X = a|b (mod 2^30), and X = 0 (mod d'). Where d' comes from d = 2^i * d', where d' is odd. The answer is under 2^60, since 2^30*d < 2^30*2^30 = 2^60

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

    Can you explain the crt method in your code? I did like usual chinese remainder theorem and to take an account that x is congruent to 0 mod d. I took the remainder 0 as d and did normal chinese remainder theorem. It did not work. I saw that you are doing something in reverse fashion, but could not understand it. I appreciate your idea anyway! Thanks and eagerly waiting for your reply and my submission is at above comment.

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

      Basically, I used Garner's alrorithm for 2 co-prime numbers: d' and 2^30. You can read more about that here: https://cp-algorithms.com/algebra/chinese-remainder-theorem.html#garners-algorithm I don't really know what is wrong with your formula above, since it's quite messy, but maybe you can find your mistake by reading this article

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

        I finally got AC using your approach and normal congruence relation.

        We have two congruence equations as

        x=(a|b)mod(1l<<30) ---> 1

        x=0mod(d') ---> 2

        That means x=d'*k, replacing this in 1 gives

        d'*k=(a|b)mod(1l<<30)

        k=(a|b)(1/d')mod(1l<<30)

        Solve this we can find k and k*d is the answer

        Hope it might help someone.

        Today i learned that if we have remainder 0 in chinese remainder theorem we can convert x into multiple of that modulus and solve it instead of doing normal chinese remainder theorem which might yield a wrong answer.

        181131228

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

          I think you are getting something wrong. There is only 1 chinese remainder theorem, but there is also an algorithm to construct the number from remainders modulo co-prime set of numbers. Chinese remainder theorem works for any remainders, as long as they are remainders modulo co-prime set of numbers. I don't understand what is normal chinese remainder theorem you are referring to.

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

    thx, got x * 2^30 + (a|b) = 0 (or d) mod d => x * 2^30 = (d — (a|b) % d) mod d => x * 2^30 = c => x = c * inv(2^30,d)

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

I think the problem b was difficult than usual.

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

Huge gap between A and B.

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

    next time we will give all problems to have *800 so there won't be any impediments for people to AK

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

Problem A is so dumb, just look at it, a lot of people did it under 1 minute, which is time to read the statement alone. Its enough just to go to test cases and see the STUPID pattern

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

    I agree. I do not understand why problemsetters include such problems. Such tasks punish participants who take the time to properly solve the problem (e.g. work out a few sample cases on their own, and figure out the $$$\lceil n/2\rceil$$$ relationship, rather than relying on sample cases to do it for you). Competitive programming should not be like this in my opinion.

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

    Some would say pattern recognition is part of problem solving

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

I had the O(100*n) solution for B TLE: https://codeforces.net/contest/1748/submission/180630056 How come?

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

    Same for C linear solution TLE: https://codeforces.net/contest/1748/submission/180643204

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

      python is so slow

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

      For C it's most likely this: https://codeforces.net/blog/entry/62393

      testcase 8 I think is an anti hash test that's designed to cause as many collisions as possible in your dictionary setup. This results in the dictionary taking O(n) per lookup causing TLE.

      For B I'm not entirely sure what's causing TLE but I don't think you need .strip for n and s. I also converted s from string to an int array initially so I wouldn't need to convert each character into int type excessively.

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

        181003922

        Getting TLE on Linear solution for Problem C: Test Case 7

        Have used unordered_map. If not to use hashing, then how to solve this one?

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

          https://codeforces.net/blog/entry/62393

          Looking at it test case 7 is also an anti hash test, specifically for c++ unordered map. you can still use hashing here but you you just need to define a custom hash function to reduce collisions.

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

    You're checking if current digit's freq is greater than 10 or not, it could be possible that it is repeated only once, in this case you will check for all substrings (not just 100). You need a length check instead of individual digit's freq check.

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

      you think the solution is wrong? how did it pass all the 100 tests before the tle?

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

        It isn't wrong. It's just inefficient. Replace the freq check with length check and it will produce the exact same output with less iterations.

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

    you should try to define print = sys.stdout.write, it may decrease the time and instead of checking mx > 10, check if mx <= different values which is easily to find

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

    I submitted your B with PyPy3, and it passed as usual, use PyPy if you're competing with Python

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

    Python is not very fast. It can be accelerated. Go to my profile, I sent the problem with your complete solution (after the round). Only I used acceleration. It went in a time that is 10 times less than the maximum.

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

    Unfortunately, yes this contest is not suitable for python users, I was skeptical of both B and C, even though my idea was same. B bcoz its 10^7 operations, C bcoz it uses dictionary

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

    Python is extremely slow on looping. While 1e8~1e9 loop iterations are acceptable with C++, in python this number is about 1e6~1e7.

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

E is easy but I have no time :(

use cartesian-tree and dp.

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

    Looking at Um_nik's screencast, he only used 3 minutes (13:00 to 16:00) to read/think and 7 mins (16:00 to 23:00) to implement for E: https://www.youtube.com/watch?v=zdlrEs78gEQ&t=1004s

    Makes me feel bad that I gave up 30 minutes into the contest and solved nothing else because I kept coming up with hard to implement solutions and thought I wouldn't have time (even though I had over an hour left). There's always enough time, just gotta gitgud

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

is it possible to solve B in python 3 , I see no accepted solutions. would be greatly appreciated if someone can help me with it. thanks

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

Wow so fast tutorials .Great Contest .Problems were great . Thank u :)

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

I dont know why I'm experiencing a TLE for this code on my last pretest for problem C T_T any idea??

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split()))
    s = 0
    res = 0
    flag = 0
    d = {}
    maxi = 0
    for i in arr:
        s += i
        if flag == 0 and s == 0 and i != 0:
            res += 1
        if i == 0 and flag == 0:
            d[s] = 1
            flag = 1
            maxi = 1
        elif i == 0 and flag:
            res += maxi
            s = 0
            d = {}
            d[0] = 1
            maxi = 1
        elif flag:
            if s in d:
                d[s] += 1
            else:
                d[s] = 1
            if d[s] > maxi:
                maxi = d[s]
    res += maxi
    print(res)
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    python is so slow

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

    Read this

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

    Just use the pypy3

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

    Actually, the hash seems to matter here too. Idk the exact reason, but my O(n) code got accepted when I only changed the hash (thanks @DrMrogon https://codeforces.net/contest/1748/submission/180659676).

    Before (TLE on test 8): https://codeforces.net/contest/1748/submission/180682651 After (Accepted): https://codeforces.net/contest/1748/submission/180683231

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

    my python3 code alse TLE even on pypy3,no idea why

    from collections import *
t=int(input())
for i in range(t):
    n=int(input())
    arr=list(map(int,input().split()))
    cc0=[a for a in range(n) if not arr[a]]
    cc0.append(n)
    ans=0
    s=0
    for j in range(cc0[0]):
        s+=arr[j]
        if not s:
            ans+=1
    for j in range(1,len(cc0)):
        count=Counter()
        s=0
        for k in range(cc0[j-1],cc0[j]):
            s+=arr[k]
            count[s]+=1
        ans+=max(count.values())
    print(ans)
    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    well,i changed the number to str and count in dictionary and then accepted like this:

    t=int(input())
for i in range(t):
    n=int(input())
    arr=list(map(int,input().split()))
    cc0=[a for a in range(n) if not arr[a]]
    cc0.append(n)
    ans=0
    s=0
    for j in range(cc0[0]):
        s+=arr[j]
        if not s:
            ans+=1
    for j in range(1,len(cc0)):
        # count=Counter()
        dic={}
        s=0
        for k in range(cc0[j-1],cc0[j]):
            s+=arr[k]
            ss=str(s)
            dic[ss]=1 if ss not in dic else dic[ss]+1
        ans+=max(dic.values())
    print(ans)
    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really nice round. I had guessed that if $$$min(lsb(a), lsb(b)) < lsb(d)$$$, it might be impossible in problem D but can't prove it. Could someone provide a proof of why that is always true?

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

    $$$lsb(kd) \ge lsb(d)$$$ for any natural number $$$k$$$, i think?

    but $$$min(lsb(a),lsb(b))<lsb(d)$$$ implies that $$$min(lsb(a\vert x),lsb(b\vert x))<lsb(d)$$$

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

Am I the only one who stupidly used Euler's Theorem to find inverse modulo in D?

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

Can anyone explain me why am I getting TLE in Problem C here's my code https://codeforces.net/contest/1748/submission/180659944

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

    Because of unordered_map.. change it to map only

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

    I choose GNU C++20 11.2.0(64 bit, winlibs) when I submit your code, and it's ok.

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

My solution for B: for each i such that 1<=i<=n we find for each possible number of distinct elements what is the range L,R where this occurs. Then for each range we check where is the first index j such that the subarray [i,j] is bad, and subract R-j+1 from all possible subarrays. Time complexity is O(100nlogn) because we can find the ranges and check for bad subarrays using binary search. You can check my code to understand more

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

Thanks for the fast editorial. I quite liked problems A-C. However, on problem D I feel like there should have been a constraint that D is a prime that is not 2. Because most of the ideas from D still apply, but finding the modular inverse is much easier. Or it could have also been split into an easier and harder version, with the easier one having D as a prime. I feel that C-D gap was quite large.

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

    You can calculate composite inverses in $$$O(\log{m})$$$ as well. https://codeforces.net/blog/entry/103374?#comment-917844

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

    I got AC using Euler's theorem. but the complexity was O(t * sqrt(d)). It would not be good to split this problem into two versions. They would be almost the same.

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

    Why? We can simply use extended euclidean algorithm or a Euler's theorem right?

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

      Yes, but that is much less known than modular inverse for prime modulo. And all other observations are more or less the same.

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

can anyone please explain problem B...

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

    There are only 10 types of numbers, so the longest enumeration in a sequence is 100, and violence is sufficient

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

I cant solve b during contest, but still I think that it was a nice problem

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

    Yeah I mean i am not able to solve B and C but this round teaches me some new concept .

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

I think my solution for D is somewhat simpler (at least for me) to understand:

First, it is impossible if the (where $$$lsb$$$ is the least significant bit) $$$lsb(a) \leq lsb(d)$$$ or $$$lsb(b) \leq lsb(d)$$$ because we are trying to find an $$$x$$$ such that $$$a|x$$$ and $$$b|x$$$ are both multiples of $$$d$$$. When we multiply a number $$$h$$$ by another $$$k$$$ and look at the result in binary, the result is the sum of multiplying the first by each of the bits of the second, which would imply that $$$lsb(h*k) \geq lsb(h)$$$ and $$$lsb(h*k) \geq lsb(k)$$$.

After we figure this out and deal with that case, the rest is easy. First lets say $$$m_i$$$ is the $$$i_{th}$$$ bit of $$$m$$$. We want to find a multiple of $$$d$$$ (lets call it $$$k$$$) where there is no bit $$$i$$$ such that $$$x_i=1$$$ and $$$k_i=0$$$. If we find this then all we need to do is apply a bitwise OR to $$$x$$$ in order to make $$$x=k$$$. This is always possible through the following algorithm:

Lets make $$$x=a|b$$$ and $$$k=d$$$ initally, then we iterate through the bits of both,

If $$$x_i=k_i$$$ then we can can ignore this bit.

If $$$x_i=1$$$ and $$$k_i=0$$$ we can left shift $$$d$$$ some number of times until the $$$lsb(d)$$$ is at the $$$i_{th}$$$ bit and then add this to $$$k$$$. This would not change any of the bits that we have already iterated over, would maintain that $$$k$$$ is a multiple of $$$d$$$, and would make $$$k_i=1$$$.

Now, there is no bit $$$i$$$ where $$$x_i=1$$$ and $$$k_i=0$$$, so we can just make $$$x = k$$$ by making $$$x=x|k$$$

Im pretty sure this is a naive solution compared to one using a single eqution but still I enjoyed coming up with it and think it is a little easier to understand.

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

    I was having a very hard time understanding it Now I get it after reading your comment...really thx <3

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

    Could u plz say what's does curr+=e does in ur code?

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

      e was $$$d$$$ but right shifted until the $$$lsb(d)$$$ was at the first bit. The way I iterated through the bits of $$$k$$$ was by using a temporary variable for it and right shifting it continuously, only looking at it's first bit. So curr+=e is the same as adding $$$d$$$ to $$$k$$$ like I described in my solution.

      My implementation was quite messy though because I rushed it before the contest ended so I wouldn't really bother trying to understand it.

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

    We want to find a multiple of d (lets call it k) where there is no bit i such that xi=1 and ki=0.

    Why do we want to do this?

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

      Because then we can make $$$x=k$$$ which would imply that $$$x$$$ is a multiple of $$$d$$$. I am also assuming that $$$x=a|b$$$ initally so this would then imply that $$$a|x$$$ and $$$b|x$$$ are both divisible by $$$d$$$.

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

    Your solution really deserve to be the editorial for this problem instead of the huge misleading equations of the official editorial, Thanks. rfhalb

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

In problem F the number of operations can be improved from $$$\frac{3}{2} m^2 + O(m)$$$ to $$$\frac{5}{4} m^2 + O(m)$$$.

Similarly to $$$f(i, j)$$$ in the editorial we can define $$$g(i, j, l)$$$ as a sequence of operations that performs xor-assignments $$$a_i = a_i \oplus a_{j+l-1}$$$, $$$a_{i+1} = a_{i+1} \oplus a_{j+l-2}$$$, ..., $$$a_{i+l-1} = a_{i+l-1} \oplus a_{j}$$$, where indices are cyclic modulo $$$n$$$ and cyclic segments $$$[i, i + l - 1]$$$ and $$$[j, j + l - 1]$$$ do not intersect. This sequence is the same as $$$f(i, j + l)$$$ when $$$l \equiv j - i$$$ and otherwise ends with 3 passes between $$$i + l - 1$$$ and $$$j$$$ to clean up the mess. Defining $$$h(i, j, l)$$$ as a sequence of operations that reverse-swaps such two segments, $$$h(i, j, l) = g(i, j, l) \mathbin\Vert g(j, i, l) \mathbin\Vert g(i, j, l)$$$, $$$\frac{3}{2} m^2$$$ solution is $$$h(0, \lceil\frac{n}{2}\rceil, \lfloor\frac{n}{2}\rfloor)$$$.

But we don't have to drag $$$a_{n-1}$$$ through the whole array to get to $$$a_0$$$. Essentially instead of $$$swap(a_0, a_{n-1})$$$ we can perform $$$swap(a_{n-1}, a_0)$$$, then we replace two long passes and one short with two short passes and one long. Instead of $$$h(0, \lceil\frac{n}{2}\rceil, \lfloor\frac{n}{2}\rfloor)$$$ we split both segments, reverse-swap one pair though the middle of the array and the other through the ends. For example, taking $$$x = \lfloor\frac{n}{2}\rfloor$$$, $$$y = \lceil\frac{x}{2}\rceil$$$: $$$h(n - y, 0, y) \mathbin\Vert h(y, n - x, x - y)$$$.

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

Hint 2 for problme D: Combined with the first hint, we can say that a triplet (a,b,d) has no solutions if min(lsb(a),lsb(b))<lsb(d). Here, lsb(x) represents the least significant bit of x.

Does this mean that if a and b are even and d is odd then it should have no solution but test case 7 of the example have a solution?

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

    Does this mean that if a and b are even and d is odd then it should have no solution It's incorrect. There is a solution.

    If $$$a$$$ and $$$b$$$ are even, then their LSB of both are greater than 1.

    If $$$d$$$ is odd, then its LSB is 1.

    $$$min(1, 1) < 1$$$ Isn't true. Hence, there is a solution.

    If you are confused with the fact that if $$$min(lsb(a), lsb(b)) < lsb(d)$$$, then there is no solution., read below.

    Let $$$dq$$$ be any multiple of $$$d$$$. And $$$k = lsb(d)$$$. You can see that $$$lsb(dq) \geq lsb(d)$$$. It can be easily seen by adding d itself in its binary representation. You can see that any multiple of $$$d$$$ will have its bits on after or from $$$lsb(d)$$$.

    Let $$$m = a|x$$$. According to the problem, we require $$$m$$$ to be some multiple of $$$d$$$. Since $$$m$$$ will be forced to have on all bits that are on in $$$a$$$ or $$$x$$$, then $$$m$$$ will have the $$$lsb(a)$$$ bit on. But we have seen that any multiple of $$$d$$$ will have its bits on from or after its lsb. Hence, if $$$lsb(a) < lsb(d)$$$, then there is no solution, it's impossible to have any multiple of $$$d$$$ that can have the $$$lsb(a)$$$ on, since it's less than $$$lsb(d)$$$.

    So if $$$lsb(a) < lsb(d)$$$ or $$$lsb(b) < lsb(d)$$$, then there is no solution.

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

I use unordered_map in C, and I get TLE.

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

    Use map instead. Remember not to use unordered_map in cf.

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

I keep getting a "wrong" judgement on my Kotlin code even though I followed the example solution to a tee. Any hints?

import kotlin.math.max
import kotlin.math.min

fun main() {
    val t = readLine()!!.toInt()
    (1..t).forEach {
        readLine()
        val s = readLine()!!

        var result = 0L

        (0..s.length-1).forEach outer@ { fro ->
            // count how often each digit 0..9 has occurred so far
            val numOccur = MutableList(10) { 0 }

            // only substrings of length <= 100 can be diverse, otherwise maxOccur >= 11 is forced
            val maxTo = min(fro+1 + 100, s.length)
            var diversity = 0
            var maxOccur = 0

            (fro+1..maxTo).forEach inner@ { to ->
                val idx = s[to - 1] - '0'
                numOccur[idx] += 1

                // no matter what chars we add, it can never be diverse anymore
                // note that this also makes the above length-100 condition obsolete
                if (numOccur[idx] > 10)
                    return@inner

                diversity += if (numOccur[idx] == 1) 1 else 0
                maxOccur = max(maxOccur, numOccur[idx])

                result += if (diversity >= maxOccur) 1 else 0
            }
        }
        println(result)
    }
}
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Apparently I need to replace return@inner with return@outer

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

I'm not sure I'm right or not, but const number can't exist in $$$O()$$$(except $$$1$$$).

The number of operations are $$$n\times10^2$$$ but you can't say that the time complexity is $$$O(n\times10^2)$$$,maybe.

And of course it is easy to understand, but I suggest to fix it due to rigour.

If I'm wrong please figure out thx.

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

    I think $$$O(N \cdot 10^2)$$$ is more concise than saying "$$$O(N \cdot a^2)$$$, where $$$a=10$$$ is the alphabet size", even though it's not as rigorous.

    Nice observation though!

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

    me when worst case $$$n$$$ is worst case $$$10^5$$$ so my $$$O(n^3)$$$ solution becomes $$$O((10^5)^3)$$$ which is a constant so it is equal to $$$O(1)$$$ so it enters any conceivable TL

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

https://codeforces.net/contest/1748/submission/180639586#

wa on #516th ... any help?

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

I finally became Master after this round. Thank you for the interesting problems.

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

I feel like there's an error in editorial of problem C. It should be added $$$[s_{i_1}, s_{i_1 + 1}, \cdots, s_{i_2 - 1}]$$$ in between $$$[s_1, s_2, \cdots, s_{i_1 - 1}]$$$ and $$$[s_{i_2}, s_{i_2 + 1}, \cdots, s_{i_3 - 1}]$$$. Of course, it does not really matter, the pattern is obvious, I was just pointing it out.

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

    You're right, thanks for noticing. It's fixed now.

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

I have a stupid and complicated solution for B https://codeforces.net/contest/1748/submission/180642025 time complexity O(n logn)

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

I think the sample of D is a big hint. During the competition, I tried to convert the output of the last example into binary and found that the last 30 digits are all 1s, so I could find the solution. I think if the sample set the last 30 digits to be a|b, I must not be able to solve it.

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

how to solve d with exgcd（Extended Euclidean algorithm）?

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

Have someone else solved C by dp?

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

    tried but wa if you know pls teach me

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

      Consider $$$O(n^2)$$$ dp: $$$dp(i)$$$ -- maximum number of consecutive subsegments with zero sum you can get from the $$$i$$$-th prefix. $$$dp(i) = max_{j = 1...i} check(j, i) * dp(j - 1) + 1$$$ where function $$$check(l, r)$$$ is a boolean function which returns $$$1$$$ if you could obtain subsegment $$$(l, r)$$$ having zero sum. It is possible if and only if it contains $$$0$$$ or if it has zero sum. You can consider these two cases and optimize dp: find previous zero left to position $$$i$$$ and get something like prefix minimum, and for second case you can store in map optimum dp for every prefix sum value.

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

so my question is:

why https://codeforces.net/contest/1748/submission/180728658 this works and https://codeforces.net/contest/1748/submission/180728780 does not?

the only difference is that in #1 I go from n-1 to 0 and #2 I go from 0 to n-1

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

    have not gone through the code completely, but since we have to look at the prefix sums it makes sense that only one of them is ccorrect

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

This's a great round... and my first round in CF :)

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

can someone explain the dp solution for qC?

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

Can anyone explain why in problem "C — Zero Sum Prefixes" is c++ std::map (my test) more preferable than std::unordered_map (my time limit test)?

Always thought that std::unordered_map should give constant time on all required operations but std::map — logarithmic. sorry for the newbie question.

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

I participated from an alt but wanted to offer my feedback on the problems.

A — alright, I accidentally saw the title before I vc'd and prewrote the code, it actually worked

B — also alright

C — not very interesting, this problem does not need to exist

D — weird definition of an integer, this problem does not need to exist

E — annoying, this problem does not need to exist

F — incredibly annoying, I don't like this problem at all, i won't even try to solve it

Am o problema mai calitativa:

Dandu se un sir de operanzi cifre si operator ^ * | & ~ XOR + — / ** ! oplus, gasiti valoarea maxima a expresiei facand maximum k interschimbari.

Marinush

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

I participated from an alt but wanted to offer my feedback on the problems. A — alright, I accidentally saw the title before I vc'd and prewrote the code, it actually worked B — also alright C — not very interesting, this problem does not need to exist D — weird definition of an integer, this problem does not need to exist E — annoying, this problem does not need to exist F — incredibly annoying, I don't like this problem at all, i won't even try to solve it I have another solution for F: Bagi bulaneala pe vectori

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

At Codeforces Round #833 (Div. 2)

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://codeforces.net/contest/1748/submission/180650292

https://codeforces.net/contest/1748/submission/180650184

https://codeforces.net/contest/1748/submission/180649269

https://codeforces.net/contest/1748/submission/180646072

https://codeforces.net/contest/1748/submission/180646346

https://codeforces.net/contest/1748/submission/180646263

https://codeforces.net/contest/1748/submission/180646094

https://codeforces.net/contest/1748/submission/180645940

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

For problem D, how can we say for sure that $$$x$$$ will be of the form: $$$p11..11(30 - k \ times)00..00(k \ times)$$$

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

In problem D: How can we prove that $$$x_{(2)}=p 1 1 1 … 1 0 0 … 0$$$ is divisible by both a and b? Please, help!

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

The data structure, described in the editorial for problem E, is called Cartesian tree. One can build it in O(N).

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

How come in Problem B, not using ~~~~~ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ~~~~~ gives AC 181109995 but using this in code gives WA 181109865

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

I came up with a different solution to problem E but it is not working (even on the first test case). I can't figure out what is wrong with my approach. I have described the idea below.

Observation

a[i] >= a[i + 1] implies b[i] >= b[i + 1]

a[i] < a[i + 1] implies b[i] < b[i + 1]

dp state: dp[i][j] = number of arrays with b[i] = j

// base case
for j: 1 ... m
    dp[1][j] = 1;

// transition
for i: 2 ... n
    for j: 1 ... m
        if(a[i - 1] >= a[i]) // then b[i - 1] must be greater than j as per observation
            for k: j ... m
                dp[i][j] += dp[i - 1][k]
        else
            for k: 1 ... j - 1 // then b[i - 1] must be lesser than j as per observation
                dp[i][j] += dp[i - 1][k]

Below is a link to my submission with actual code (which optimizes the above pseudocode using a prefix sum array.

181409754

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

In problem D, there's this step in the explanation

$$$p+1 ≡ (2^{−1})^{30−k} \mod d' ⇔ p+1 ≡ (\frac{d'+1}{2}) ^ {30−k} \mod d'$$$

I don't understand where it comes from, like what property is being used or why this is done, can anybody help me please?

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

Why is my same code getting accepted in GNU G++17 7.3.0 and not in GNU G++20 11.2.0 (64 bit, winlibs) ? What's the difference between these two languages? GNU G++17 7.3.0 — 186674226 GNU G++20 11.2.0 (64 bit, winlibs) — 186674279

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem B, can anyone help me understand why this 188673953 is AC, but this 188673213 is WA?

The AC one is simply starting from ans=0 and doing ans++ for each diverse substring. The WA one is the opposite. It starts with ans=(n*(n+1))/2 and doing ans-- for each non-diverse substring.

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

    Take a look at Ticket 16693 from CF Stress for a counter example.

    By the way, it's trivial to prove that your WA algorithm is incorrect. In your AC submission, you are iterating over all diverse substrings. In your WA submission, you iterate over all non-diverse substrings. So if I combine both of your solutions, I would be able to iterate over all $$$O(n^2)$$$ substrings in $$$O(n)$$$ time. A contradiction.

    The catch here is that the diverse substrings are scarce, and closer to $$$O(n)$$$, while their complement is abundant, of order $$$O(n^2)$$$. That's why the subtraction strategy would result in TLE if implemented properly, or would undercount the non diverse substrings of length greater than 100 if implemented poorly.

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In C can it happen that maximum frequency prefix of the subarray is such that for nullifying that prefix our ai exeeds the limit of 1e9 ?

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

    My bad it can be any arbitary number.... i thought that just like initial ai new replaced ones should also lie b/w -1e9 and 1e9

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

D is such a nice problem man but there is something that I found very unintuitive about it and that is — why you filled all the digits before p and after k to be one. I mean the best thing I could arrive at after solving this problem for hours was that rather than filling up all of them with ones as you did I would fill it with a^b and I reched nowhere.

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a flow-based solution for Problem E?

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

    Thumb Rule: only thing one needs is segtree atmax for a div2 round Anything else is overkill

    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hard Div2 ?

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

might be stupid to ask but how we can write

inverse_of_2=(d+1)/2;

any proof or just observation?

→ Reply