Anadi's blog

Codeforces Round 880 Editorial
By Anadi, history, 17 months ago, In English

1836A - Destroyer

Tutorial
Solution

1836B - Astrophysicists

Tutorial
Solution

1836C - k-th equality / 1835A - k-th equality

Tutorial
Solution

1836D - Lottery / 1835B - Lottery

Tutorial
Solution

1836E - Twin Clusters / 1835C - Twin Clusters

Tutorial
Solution

1836F - Doctor's Brown Hypothesis / 1835D - Doctor's Brown Hypothesis

Tutorial
Solution

1835E - Old Mobile

Tutorial
Solution

1835F - Good Graph

Tutorial
Solution
  • Vote: I like it
  • -267
  • Vote: I do not like it

Comments Comments (115)
| Write comment?
»
17 months ago, # |
← Rev. 2   Vote: I like it -29 Vote: I do not like it

UPD: tutorial is empty

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

NTR_LOVER should get ntred ;-;

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

It says tutorial is not available!!

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

A fast tutorial without the tutorial.

UPD. The tutorial became available as fast!

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

i've never participated in atcoder contests. Is this what agc feels like?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    No.

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

      I've participated in AGC only several times, and can't speak much about how close are those problems to problems of this contest. But by difficulty, this contest (Div 1) is very close to AGC.

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

Fast editorial. B was boomer...

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

it's not an interesting competition at all

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

You guys are mean, I think the contest was great!

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    As good as the contest might have been (D1C and D1D look acceptable), people had to read D1B and think about it or just jump in a leap of faith to do D1C, and D1B doesn't have the happiest implementation, solution etc., so the quality of the contest bottlenecked at D1B

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

      The idea is easy, good competitors will impl quick, worse usually only solve 2 or 3 in div1 anyway. Not every problem should have trivial impl. It wasn't an amazing contest, but the quality was no different than majority of contests i've taken, i liked all the problems i've looked at (A-D).

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

        good competitors will solve quickly

        How good do the competitors have to be to solve D1B* 😂 😂? I have one of the lowest performances of such competitors (solved in 1h10m) and still managed to get ~2350 performance. I find it uncredible that so many people are poor competitors.

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

          Low master usually only solves 2 or 3 in div1 anyway, so taking 1h30min is reasonable for harder contest. GM can surely solve and implement in 45min and still have time for 3-4 total, or strategize to skip if they think it will be faster to solve harder, which we see both on scoreboard. It is unfortunate many on cf are too bad at implementing because they are only used to 10 line solutions (it is only downside with recommending cf for practice).

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

I feel like the problems were definitely interesting. It was just sometimes annoying to think about them.

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

It's easy to guess the conclusion of Div1.B but very hard to believe and proof it.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +101 Vote: I do not like it

    not really — lets say you choose position "m"

    let l be the vote k away from you on the left, and define r similarly

    the interval where you win is (l + m)/2 ... (r + m)/2

    therefore, m doesn't really matter, except for parity reasons — so it is optimal to choose 1, 2 to the right from a vote

    then theres the case where l doesn't exist, in which it would be optimal to choose 1 left from a vote

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

too hard div2b for me (for me)

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

Div.2 B-D have clear solutions but it was quite hard to implement them for me.

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

I believe there is a typo in the editorial for problem Div2C. The upper bound for b should be min(10^C — a, 10^B).

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

Div 2 C can be solved by brute forcing all candidates for A, then checking the range that satifies the equality with 2 binary searches 210127806. It's actually mostly the same as the editorial, but using binary search instead of basic math.

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

    I did something similar.

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

    I tried to do something like that in the contest but it ended up in TLE, I think that the problem was in the way I implemented it.

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

    Congrats on becoming CM

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

    Can you explain the basic math. I feel kinda dumb because I don't get it. Congrats on becoming Candidate Master btw

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

        Thank you for the explanation. I think I get it.

        b2 is the largest possible number that b can be. The largest value C can be is (10^c) -1. Therefore, the largest value b2 can be is (10^c)-1-a. However, b2 is also bounded by its length as it must be b digits. So it is b2 = min((10^c)-1-a,10^(b-1))

        Is this correct?

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

          Slight error. For $$$b1$$$, $$$10^{B-1}$$$ is the smallest B-digit number. But for $$$b2$$$ you'd have to look for the largest B-digit number instead(to maximize $$$b2$$$). Also, to know if you're correct, just check if what you wrote is the same as editorial.

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

In C tutorial, should it be min{10^C — a, 10^B} instead of max?

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

OMG i did not read this line in C

Each input file has at most 5 test cases which do not satisfy A,B,C≤3 .

used binary search and at last could not implement :( today is my worst day.

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

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

if two people can have the same lottery ticket, yall should've at least put that in the samples

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

    I think the difficulty was reasonable if two people cannot share the same position and $$$N \le 10^5$$$ as Div2D/Div1B.

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

      if two people can't share the same position, its still the same algorithm / difficulty, just minor implementation differences

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

        oh, then I should read solution but it is not available...

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

        It is the case if you observed that optimal lottery number can only lies on some $$$[x-2, x+2]$$$ range for some bought lottery x. But for me I tried to maintain a sliding window-like algorithm, in which case having same lottery tickets make case discussion like 10x harder ...

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

my solution in Div1C:

  • if N <= 8 , bruteforce all 4 ranges [L1,R1] [L2,R2].
  • else lets fix a range L1=R1 , now we find a subarray before or after that index that has the same XOR value as that element, run that for some random elements L1 a few times till you find a solution.

can someone hack this solution ? :)

https://codeforces.me/contest/1835/submission/210164524

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

I still did not get Div2B?? Can somebody help?

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

    give all of them g/2 -1 coins except for the last one.

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

      How about the case when there are some coins left? Why is giving them all to one astrophysicist optimal?

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

        I don’t know how to prove it rigorously but it is pretty intuitive. If you were to give any of the other astrophysicists a coin you would just be wasting silver coins. Try thinking of any way to redistribute them when they are in the above state to make it better and you won’t find anything. Either way, A and B are usually about intuition from my very limited experience.

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

      Why we give g/2-1 coins to others except last one , what is logic and intuition behind g/2 — 1 and why we are focusing distributing g/2 — 1 coins at first, can you please explain this intuitively ?

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

        g/2 — 1 is the maximum number of coins you can save from one astrophysicist.

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

Why was Div2 D/ Div1 B skipped by many contestants?

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

Even I solved Div2B, but I still can't understand the statements. Is it because I am bad at English?

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

    No i guess : (

    i also didnt understand the Div2B statement and cant implement the code : (

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

      Given n , k , g you must distribute k * g coins to n people in such way that if you round up all of them to nearest integer that is divisible by g , the sum of them us minimum as possible. after that , you should output k * g — sum of them to save the most amount of coins you can have

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

        Why nearest integer can't be zero?

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

          it can ne zero if your coins is less than g / 2

          for example if you want to near 4 coins to the nearest integer that is divisible by 9 , it will be zero. however if you want to near the 7 coins to the nearest integer that is divisible by 9 , it will be 9

          since 9 — 7 >= 7 — 0

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

Could you help me check it, I run my code and it correct testcase 930th of test 10 but the log show wrong.

My submission: 210165371

Thank you

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

Are Div 2 Bs supposed to be this math heavy ? Like the statement is not understandable at all unless you carefully parse it and post that try to find the formula ? I am not sure what this problem can you train you for or be reusable for anything else , open to opinions but didn't like the contest

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

The answer to 1835E - Old Mobile depends only on $$$n$$$, $$$m$$$, and the number of distinct digits of the array. My submission runs in $$$O(n+m)$$$ time (where the $$$n$$$ term is just for reading input).

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

Boink

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

look at E/C first solver's handles

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

For Div2B,I did not understand for the part where we have extra money.Can someone explain it with some test case to me?

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

In Div 2C, I tried to binary search the values of b for each a, but got TLE on 210139402 for complexity O(10^a*log(10^b)).

I then found limits for minimum possible a and iteratively updated for all subsequent values in submission 210153651 but still got TLE for O(10^a+log(10^b)) complexity.

I thought this should've passed according to constraints in question but still I submitted by replacing long long to int but still TLE on 210154560, then did some more optimisations to reduce operations on each iteration and got AC on 210155518.

I spent ~40 mins on just optimising for the time limit. Granted, my implementation might be too bad but I do think the constraints were too tight for this problem. I think my first 2 solutions itself would've passed if time were 2 sec. Do point out any specific slow part of the code, would be helpful for future.

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

    I guess you already got that all time consuming by main cycle.
    I guess you already got that in one cycle iteration you do at most 18 calls of digits macros.

    So you should ask yourself questions:

    1) Do I really need 18 calls in each iteration (you answered no in AC solution)?
    2) How long is single call to digits?

    I guess that you interested in second question. What you should do? Measure. Gladly we have Custom Invocation tab where we can do it.

    Snippet

    And you will see, that digits1 version do whole cycle within ~0.5s and digits2 is ~0.08s.

    Why? Don't know (I dont have any expertise in how abs and log10l functions implemented), but I dont see it strange since your version is abs + hard floating point operation and mine is just integer division (yeas, floating point operations hard).

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

      Hey, thanks for the insights and comparison! Will avoid floating pt calculations when possible.

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

My solution for Div1 C was different from the (deterministic) one in the editorial.

If there are at least two zeroes in the array, pick one of them as the first segment and another as the second. Now assume that there is at most one zero.

Consider all xors of type $$$a_i\oplus a_{i+1}\oplus\ldots\oplus a_{n/2}$$$, including the empty one; call the multiset of these xors left. Similarly, consider all xors of type $$$a_{n/2+1}\oplus\ldots\oplus a_j$$$, call them right. However, if there is a zero, then it will make two adjacent xors equal, in this case we remove one of them from the corresponding multiset (we'll see later why it's important).

Each pair of a left xor and a right xor generates a subsegment containing the middle of the array (by middle I mean the imaginary bar between elements $$$n/2$$$ and $$$n/2+1$$$). There are at least $$$(n/2+1)\cdot n/2 > 4^k$$$ of them, therefore some two of them have the same xor. Let's find one such $$$x$$$ that at least two pairs $$$(i, j)$$$ satisfy the relation left[i] ^ right[j] = x.

We can find such $$$x$$$ bit by bit, from highest to lowest. Indeed, on the first step calculate the number of xors of type 0????? (this can be done with some binary searches). If it is at least $$$2^{2k-1} + 1$$$, we will look for $$$x$$$ of this type, otherwise we assume that $$$x$$$ looks like 1?????. Then we try to set the next bit zero, and so on. After we found such $$$x$$$, we can find two segments $$$A$$$ and $$$B$$$ with this xor.

Now, if they have different beginnings and different ends, we just take $$$A$$$ and $$$B$$$ if they are disjoint, otherwise $$$A\oplus B$$$ is a disjoint union of two segments, which we print. If they have the same beginning then their ends differ by at least two (because otherwise we had two left/right xors that only differ by a position that has zero). Then $$$A\oplus B$$$ is a segment of length at least $$$2$$$ with zero xor, we can split it into two subsegments (which have to have equal xors).

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Also, my screencast

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

    I did the same bit by bit approach, but didn't split on left and right. Instead I found 3 subsegments from the whole array with the same xor (there always are) and either some 2 of them don't share an end and it's easy, or all three share one of the ends and we get 2 subsegments with xor 0.

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

Please add a proper editorial for Div1 B. What am I supposed to understand from that shitty macro-filled code?

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

    First, sort the array A. Suppose you pick your lottery number and insert it into the array A; let's call the resulting array B. For now, assume all values of B are distinct. Then your number has some index $$$i$$$. What is the range of numbers that make you win one of the K prizes? Clearly it's some consecutive range around B[i].

    Look at the lower bound first. If i < K then the lower bound is 0: since your number is among the first K, any value less than B[i] will definitely win you a prize. Otherwise, if i ≥ K and the lucky number Q < B[i], then you win a prize only if (Q-B[i]) < (B[i-K]-Q) (in other words: the lucky number is closer to your number B[i] than the K-th number to its left, B[i-K]). Written differently: Q > (B[i-K]+B[i])/2.

    Similarly, the upper bound is Q ≤ M if i ≥ N-K, and Q < (B[i+K]+A[i])/2 otherwise.

    Combining this, we can calculate the count of winning numbers as: (i >= N-K ? M : floor((B[i]+B[i+K])/2)) - (i < K ? 0 : ceil((B[i-K]+B[i])/2)) + 1. (This is just the difference between the upper and lower bounds mentioned above.)

    So far we assumed numbers are all distinct. What if there are duplicates? The basic idea remains the same, you just need to make sure that you count numbers A[j] = B[i] as lying to the left of B[i] in your lower bound calculation, and to the right of B[i] in the upperbound calculation, since all previously-bought tickets will beat yours even if you picked the same number.

    So now we have a way to calculate the winning probability given a chosen number and in theory we can find the answer by trying all values between 0 and M. Of course, this is way too slow. Fortunately, we only have to try a few candidates: 0, and the values around each possible A[i]. I ended up using {A[i]-2, A[i]-1, A[i], A[i]+1, A[i]+2}.

    Why is this sufficient? Look at the formula above. If K ≤ i < N-K then the count of winning numbers is (floor((B[i]+B[i+K])/2) - ceil((B[i-K)+B[i])/2) + 1). If B[i-1]+2 < B[i] < B[i+1] then we can subtract 2 from B[i] without changing the winning number count, and since we're supposed to minimize B[i] anyway, it doesn't make sense to consider higher values.

    (Why do we need A[i]-1 and A[i]-2 too? That's to cover the case where i < K.)

    For each candidate, you can easily find the surrounding numbers with binary search in A, for an overall O(1+5N×log N) = O(N log N) solution. I'm pretty sure you can also do the main algorithm in O(N) with a two-pointer solution instead of binary-searching each candidate, and that's probably faster in practice, but since you need to sort the input first, it's technically still O(N log N).

    I think my solution is more readable, too: https://codeforces.me/contest/1835/submission/210182613

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

      Great 'editorial'! Thanks.

      I made a 2-pointer implementation here: 210231900

      Your formula:

      (i >= N-K ? M : floor((B[i]+B[i+K])/2)) - (i < K ? 0 : ceil((B[i-K]+B[i])/2)) + 1

      is slightly different from your implementation, I used:

      hi= (i >= N-K ? M : ceil((B[i]+B[i+K])/2)-1)

      lo= (i < K ? 0 : floor((B[i-K]+B[i])/2) + 1)

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

      Hey, i dont understand why we are choosing A[i]+1, A[i] + 2. I undertstand we choose A[i] so that he is between A[i] and A[i+1] and it is the smallest optimal. but why are we checking A[i]+1, A[i]+2. Wouldnt they give the same winning range.

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

        Considering only A[i] isn't sufficient, because if you tie with a previously-picked number, you lose. For example, if K=1 and you pick any A[i], you can never win. That's why for K=1 you need to pick A[i]+1 or A[0]-1.

        You need A[i]+2 too due to the rounding after dividing by 2: sometimes when you move one space to the right, you gain 1 winning number on one side without losing it on the other side. For example, when K=2 and A={1,2,10,11}, then 4 is better than 3.

        (Maybe you don't need A[0]-2.)

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

What a cute determistic approach for D1C! How evil I always think about birthday-attack like approach for this kind of problems...

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

Might be biased, and sorry if it sounds harsh, but problem div 2C, from the problem itself, to the statement, to the constraints, to the format of the output, is the worst problem I have seen on codeforces in my 4 years here.

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

    I think it's fair to criticize if you also support your criticism with arguments, which you haven't really done.

    Problem itself: What's bad about it?

    Statement: It seemed clear and concise to me; maybe the lexicographical comparison could have been explained a bit more rigorously, but I think in this case it was pretty easy to understand what it meant for equations to appear in sorted order, since the numbers all had equal size (so you didn't have to wonder whether e.g. a space comes before or after a digit).

    Constraints: okay, the “at most 5 test cases do not satisfy A, B, C ≤ 3” part is a little awkward, but it's clearly intended to allow O(A) solutions to pass while also making it possible to create some input files with many test cases. Maybe I would have phrased this as:

    For at most 5 test cases: A, B, C ≤ 6.
    For all other test cases: A, B, C ≤ 3.

    Output format: what gives you trouble here? You can just do printf("%d + %d = %d\n", a, b, c); or std::cout << a << " + " << b << " = " << c << '\n'; in C++, or print(a, '+', b, '=', c); in Python. I could see how printing only the three numbers would be slightly simpler but adding a '+' and '=' character in between it's really not that hard, is it?

    How would you improve the problem?

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

      You literally just listed all the problems, and you're still asking what the problem is

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

        The point was, the problems I could identify weren't all that bad; just minor complaints. I don't think that justifies the label of “worst problem in four years”.

        Maybe it was intended as a compliment? If this was the worst problem in the past four years, then CodeForces is doing great!

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

      I would improve the problem by implementing the changes you gracefully pointed out.

      Presence of larger inputs, even if limited, suggests a faster than roughly brute force is needed, and while possible, it is very ugly. Sure, contestants can spend time figuring out what will pass and what won't based on input distribution, but I have never seen this in a cf contest and I don't see a reason to start now.

      The output format is easy sure, but I have never seen this in a cf contest and I don't see a reason to start now.

      All in all, it breaks with several precedents, and I add my opinion that the problem itself is uninteresting, but that is subjective so to be taken with a grain of salt.

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

In div2-C shouldn't b be less than MIN(10^C−a,10^B) instead of MAX?

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

What is the proof that $$$n^3$$$ is a large enough bound in Div1.D?

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

    Consider a strongly connected component. Consider the gcd of all cycles in this SCC to be $$$g$$$. Say $$$v$$$ and $$$u$$$ are a suitable pair. It means that there is a path between them (of length $$$\le n$$$) such that after going through it we are left to go divisible by $$$g$$$ number of steps. Now look at any simple cycle through $$$u$$$. Its length is divisible by $$$g$$$. Say this cycle length is $$$gx$$$. But the gcd of all cycles is $$$g$$$. Notice that if we start calculating this gcd with $$$gx$$$ and take new cycles one by one into the gcd (there is an infinite number of cycles, but you get what I mean), every time the current gcd either does not change or is divided by smth. We can look at only the cycles that decreased the gcd. Every time the gcd decreased by a factor of at least $$$2$$$, so we need only $$$\log n$$$ other cycles for their gcd to be equal to $$$g$$$. Now we can combine all these other cycles into one that has length $$$yg$$$ where $$$gcd(y, x) = 1$$$. The length of this cycle is $$$O(n \log n)$$$. Now we go through this cycle some number of times until the remaining distance we need to cover is not divisible by $$$xg$$$. This can be done due to the Chinese remainder theorem (it is easy to see that in this case there exists a positive solution to the linear gcd representation, and it uses $$$O(n)$$$ passes through the cycle because if you have one solution to $$$ax+by=1$$$, you can get a different one by adding $$$y$$$ to $$$a$$$ and subtracting $$$x$$$ from $$$b$$$). When the remaining distance is divisible by $$$xg$$$, we just go through the cycle of length $$$xg$$$ the needed number of times. This way we proved that we need at most $$$O(n^2 \log n)$$$ steps. In this argument, I didn't try to be precise, so we have the $$$O$$$ notation, so it does not prove the desired inequality for small values of $$$n$$$, but I hope I gave you an idea of how it works, and now you can figure out how to do in more precisely.

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

      How do you combine the $$$\log{n}$$$ cycles into one with length $$$yg$$$ where $$$gcd(y, x) = 1$$$, such that the combined cycle is length $$$O(n \log{n})$$$?

      You can't just add the cycle lengths together: for example, if you have $$$g=1$$$, $$$x=30$$$, and other cycles of length $$$5, 3$$$, if you add these other cycle lengths together, you get a cycle of length $$$y = 8$$$, and $$$gcd(x, y) \neq 1$$$.

      Also, what if some of these $$$\log{n}$$$ cycles that are added to the list to make the $$$gcd(x, y) = 1$$$ do not share a common vertex, so they cannot be combined easily into one big cycle?

      Lastly, how would one prove the exact $$$n^3$$$ bound (as big O notation doesn't show the exact bound for smaller $$$n$$$)?

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

Hello, my submission to div. 1 C 210190393 returned "wrong answer Segments have different xors (test case 8)", but my answer to test case 8 seems right. Is there anything wrong with the checker?

input:
1
2 1 2 3

output:
2 2 3 4
→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I think the test cases are numbered starting with 0. And answer for next test case is wrong. Input : 1 0 3 2 3

    Output : 1 1 3 3

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

    That wasn't very clear. Test cases are numbered starting with $$$1$$$ now.

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

I don‘t understand why d2C t* o(10^a+10^b) = 1e9 not TLE.And I write 2hours binary search.

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

1D similar with https://atcoder.jp/contests/abc306/tasks/abc306_g

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

Correction: [ 1836C — k-th equality ]

Section — Tutorial

We can easily find this range. We get that max{10C−1−a,10B−1}≤b<_max{10C−a,10B}_

The upper bound should be min {10^C-a,10^B}

→ Reply
»
17 months ago, # |
← Rev. 4   Vote: I like it +42 Vote: I do not like it

can't solve problem Div.1 B, because can't analyzed the details of the code.

lost rating, its very sad.

How improve?

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

Why the tutorial of D1B is unavailable? Or it's my problem?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it -44 Vote: I do not like it

    It's not written. We'll add it today or tomorrow.

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

Why problem D's tutorial is not available?

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

Сan it be proved that gcd of all cycles in SCC is lcm of good values for coloring (I tried to pass with this implementation and somehow failed)?

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

I need the tutorial of Div.2 D / Div.1 B

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

1835C — Twin Clusters

Interesting pair of "First solve")

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

Can someone explain how for div2C we get that the range is max{10C−1−a,10B−1}≤b<min{10C−a,10B}

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

In the tutorial (Deterministic solution) of problem 1836E — Twin Clusters / 1835C — Twin Clusters, we can prove that there are always two segment have the same XOR. But what if that two segment do not disjoint, how can we prove that we will always have two disjoint segment with the same XOR value.

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

    If they're not disjoint, you can still remove the common part and obtain two disjoint intervals with equal XOR.

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

      Ah yes yes, I have realized it yesterday. But in the situation that one of these intervals only have 1 length (like a = b and c = a, d > a), I just don't know to solve it.

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

Limitations for div1E are kinda confusing. Why $$$m \le 1000$$$ if the intended time complexity is $$$O(m^2)$$$ time? I first wrote an $$$O(m^3)$$$ solution that worked in twice the time limit and I was beating my head around trying to understand how to optimize it until I figured out that I just need to make it quadratic. I feel like $$$m \le 3000$$$ for example would be more suitable for this problem.

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

I have the same solution for div1F but I thought about it in a different way. I also first tried to use submodularity, but it seems like a too complicated concept for this problem. We can do it in classical CP terms!

As in the intended solution, we first handle the NO-case. If we are in the YES-case, it means that there exists a perfect matching. Let's rename the vertices in the right part such that in this matching vertex $$$i$$$ on the left side is connected to the vertex $$$i$$$ on the right side ($$$n+i$$$ in the problem definitions, but let's number both parts from $$$1$$$ to $$$n$$$). Now for every subset of vertices on the left side $$$S$$$ it is connected to at least the same set $$$S$$$ on the right side. So a set is tight if edges from this set go only into this set on the right side. Let's replace this bipartite graph on $$$2n$$$ vertices with a directed graph with $$$n$$$ vertices: if we have an edge between vertices $$$u$$$ in the left part and $$$v$$$ in the right part, we add a directed edge from $$$u$$$ to $$$v$$$ in the new graph. Now our condition can be translated as "A set $$$S$$$ of vertices is tight if and only if there are no outgoing edges from this set into the remaining vertices". If we now look at the strongly connected components of the resulting graph, it is easy to see that a set is tight if and only if it is downward closed in the DAG of strongly connected components (so it consists of multiple strongly connected components, and if it consists one of them, it also contains all reachable ones).

Ok. We want to create a new graph. The new graph is also good, so it also has a perfect matching. Let it again connect vertices $$$i$$$ with the same vertices on the right side. Now we want to minimize the number of remaining edges to add such that the set of downward closed sets in the corresponding directed graph is the same as in the directed graph for $$$G$$$. It is equivalent to making sure that the reachability is preserved ($$$u$$$ is reachable from $$$v$$$ in $$$G'$$$ if and only if it is reachable in $$$G$$$). Every strongly connected component should remain strongly connected, so if its size is larger than one, we should connect its vertices into a cycle. Now we need to preserve the reachability inside the DAG of strongly connected components. We should add an edge $$$v \to u$$$ only if it already existed, and also if we can not reach $$$u$$$ from $$$v$$$ via a detour. It all can be checked by going through SCCs in the reversed topological order and storing in bitsets all the reachable vertices from the current vertex. Code: 210678931.

Essentially this solution is exactly the same as the one presented in the editorial, however, I think that it is easier to grasp, and it is more natural. It also shows that the editorial actually talks about things like this directed graph, and its strongly connected components, but without saying these words, which could make things a bit harder to understand.

P.S. Maybe it was done on purpose so that people don't notice that both div1D and div1F are actually problems about strongly connected components :)

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

Sorry,I have a question. 1836B — Astrophysicists'Tutorial at the end of this part "and by decreasing the bonus of one astrophysicist, we can get at most 1 from another one" why is it at most not at least?

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

    Indeed, based on the analysis we've discussed so far, it should be clear why allocating only one silver coin to each person is not an optimal decision. Firstly, by giving each person only one silver coin, we can only save one coin per person. Secondly, in cases where the number of people is insufficient, the last person to receive coins would end up needing to be compensated with a larger amount of silver coins. This prevents us from saving the maximum number of coins. Therefore, allocating one silver coin to each person is not the most optimal decision.

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

      TTthanks just noticed your reply 0.0 I will review problem B

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

For Div2D, how to prove this : 'It will either have a length of ⌊(b−a)/2−1⌋ or ⌊(b−a)/2−2⌋'

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

In Prb C (https://codeforces.me/problemset/problem/1835/A) tutorial says we can iterate over all a (1e6). but tc is 1e3. so in worst case it can be O(1e6*1e3). and there is no information about sum of all a in all tc will be 1e6. What's the problem here?

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

I think Div2B statement is poorly written. It took me some good amount of time to understand the question.

→ Reply