BrayanD's blog

By BrayanD, history, 4 months ago, In English

1631A - Мин-макс замены

Author: humbertoyusta

Hint 1
Hint 2
Solution

1631B - Веселье с четными подмассивами

Author: humbertoyusta

Hint 1
Hint 2
Solution

1630A - И-сопоставление

Author: humbertoyusta

Hint 1
Hint 2
Solution

1630B - Отрезок и разбиение

Author: humbertoyusta

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1630C - Раскрась середину

Author: humbertoyusta

Hint 1
Hint 2
Hint 3
Solution

1630D - Переверни отрезки

Author: humbertoyusta

Hint 1
Hint 2
Hint 3
Solution

1630E - Ожидаемые компоненты

Author: BrayanD

Hint 2
Hint 3
Solution

1630F - Сделай его двудольным!

Author: BrayanD

Hint 1
Hint 2
Hint 3
Solution
 
 
 
 
  • Vote: I like it
  • +246
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Auto comment: topic has been updated by BrayanD (previous revision, new revision, compare).

»
4 months ago, # |
  Vote: I like it +46 Vote: I do not like it

Really appreciate writing an editorial with hints. Helps a lot!!

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

Did you give the proof of cont cannot be $$$0$$$ in problem E? What if $$$\mathit{tot}_{\mathit{all}} \equiv 0 \pmod{998244353}$$$?

Upd: Thank the authors for replying. It’s just a tiny flaw. I didn’t solve the problem is just because I’m away from training for too long...
Looking forward to a specific case with $$$\mathit{tot}_{\mathit{all}} \equiv 0 \pmod{998244353}$$$, can someone construct such one?

Advertisement: A live recording of me participating this contest (in Chinese, bilibili: BV1kq4y187B4)

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

    The statement will be fixed, I added the restriction:

    It is guaranteed that the total number of different permutations of $$$a$$$ is not divisible by $$$M$$$

    Sorry for that mistake

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

    Yes, there is a case that leads to $$$tot_{all} = 0$$$ (mod 998244353)

    30612 ones, 12124 twos, 2 threes

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

      Can you put the Easiest Solution for Problem E in Editorial?Link

      I don't know How I missed this intution!!

      "All I know is, I know nothing But how Do I know?"

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

Love this style of editorial! Thanks!!

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

In case someone is interested, I made video Solutions for A-D(div-2)

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

nice edi

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

I think in 1630C problem it is also easy to calculate 1's, for reference we do everything same , but few ranges are joint , for e.g. (x1, y1) && (x2, y2) such that y1 > x2 and y2 > y1 than we can not paint both y1 and x2 but we can paint 1 of them including every other element in range x1, y2

here is implementation

https://codeforces.com/contest/1631/submission/144258175

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
  • A simpler approach for Div1B/Div2D using binary search.
  • It was mentioned ai<=n, so we can linearly iterate on x from min element to max element of the array.
  • For every x we can find the first y using binary search that can produce atleast k subarrays.
  • To check if we can create atleast k subarrays given a range [x, y], we count the number of elements inside and outside the range. For every subarray, we will need atleast one extra element inside the range than outside, so we can keep a sorted copy of the array, and using lower bound we can count number of elements inside and outside the range, and if we have atleast k extra elements lying inside, then [x, y] is a valid range.
  • If we have more than K legal subarrays, we can merge some, because merging two legal subarrays will give us a legal subarray always.
  • After we have found y, we can check for y-x, minimize and store them.
  • After we have a desired [x, y] we can linearly traverse again and as soon as we have more elements inside the range [x, y] than outside the range, we can keep it as a subarray, like this we can get k-1 subarrays and for the last subarray, it can contain all the remaining elements.

My solution for the same 144255745

UPD: The same problem can be done using two pointers with better TC. Solution using two pointers 144364659

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

Problem D was really cool problem. I have solved it with segment tree. link

This contest was:- Operationoforces :)

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

How to solve D1A/D2C without the k<=n-1 constraint ?

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

    Notice that $$$a_i \oplus b_i = a_i + b_i - 2 \cdot (a_i \& b_i)$$$, where $$$\oplus$$$ denotes bitwise xor, which is much nicer for pair-wise budgeting than bitwise and. Thus, in any solution, $$$ \sum_{i=1}^{n/2}{a_i \oplus b_i} = \binom{n}{2} - 2 \cdot k$$$. The bitwise xor of each pair is between $$$1$$$ and $$$n-1$$$, so we may reject if this sum is not between $$$n/2$$$ and $$$n/2 \times (n - 1)$$$. Otherwise, a solution always exists.

    You can construct one by starting from a pairing that matches every $$$x$$$ to $$$x \oplus C$$$ for some fixed $$$C$$$ and tweaking it at some small number of pairs, similar to what the main editorial does for $$$k < n - 1$$$. The simplest tweak is to mess with exactly two pairs. This can be done by, for example, pairing $$$(0,x)$$$ and $$$(C, x \oplus C)$$$, with a resulting total xor of $$$(n/2 - 2) \cdot C + 2 \cdot x$$$. It's easy enough to see that there always exists at least one working choice of $$$C$$$ and $$$x$$$, but an explicit formula seems a bit messy. My code just brute-forces all possible options: 144268260

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I really liked the problem 1631C - И-сопоставление, but I think the constructive solution shown in editorial is a bit overly complicated. My solution is similiar, but I don't really need to handle that many cases (it's only necessary to check if a number hasn't been already used).

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

    I solved it the same way. In simpler terms: match $$$i$$$ with $$$n-1-i$$$, and then 'shift' the positions of $$$ 0, b_1, b_2, ... b_x $$$. This will make the sum $$$k$$$, except when two of them are already matched with each other. It can be proven that this only happens when $$$n=4$$$ and $$$k=3$$$.

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

In the solution of 2D/1B: $$$[x\le a_i\le y]$$$

What is the name of this square bracket expression? It seems to me that $$$[\text{true}] = 1$$$ and $$$[\text{false}] = 0$$$.

Edit: Iverson bracket

»
4 months ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

..

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

    You misread the problem. You need to assign the value $$$a_{l+k+i}$$$ to $$$a_{l+i}$$$, not the other way around.

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

What's wrong with: 144271690

Idea 1: If we have two intervals, one of which contains the other, then remove the smaller interval.

Idea 2: If we have three intervals which mutally intersect, then remove the middle one.

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

Reminder that multiple (N) gcd calls over the same variable works in O(log(A) + N) where A is the first number greater than 0 set to it.

So div1E's complexity is wrong. Edit: not wrong but there's a lower bound :)

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

    In problem D1E, we need $$$gcd(n,x)$$$ for all $$$x$$$ independently. So we need to call $$$n$$$ times the $$$gcd$$$ function

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

      True, let's fix that: let's say x = p * y for some prime p that divides x. gcd(x, n) is gcd(y * p, n) which is either gcd(y, n) or gcd(y, n) * p. Do dp[x] = gcd(x, n), check those 2 cases separately and preprocess some prime for every number. Is there any other part higher than O(N)?

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

        Well, that's interesting. In fact, I had a O(N) solution using euler phi function, but O(N*log) solution was easier to explain. Anyways, your idea is good, and yes, it is O(N) in total.

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

          In fact, just the editorial is O(N), I just was too sleepy to realize:

          sum log(a[i]) <= sum a[i] == N so sum log(a[i]) is O(N) where a[i] is the frequency of i

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

            This is the part of more complexity, are you sure that it is O(N)?


            long long res = 0; long long cont = 0; for(int i = 1 ; i <= N ; i++) { long long ggg = N/__gcd(N,i); if(G%ggg == 0) { res = (res + arr[ggg])%MOD; cont = (cont + arr2[ggg])%MOD; } }
            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              No, that's O(NlogN). I guess I went by too quickly through that part of the editorial (because I didn't want to completely spoil the idea).

              With that code it's clear that

              for(d divisor of N) if(G % (N / d) == 0 or something like this) res += arr[d] * phi(d), cont += arr2[d] * phi(d)

              is equivalent and another way to optimize the complexity.

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

                Yes, that was my idea with euler phi function. You can precalculate all phi numbers until N in complexity O(N), or maybe factorize N and do something

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

nice round

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

For Div.2 Problem D, my first intuition is to enumerate x, and for each x use binary search to find the best y.

for x in [min, max]:
    l, r = x, max
    while l < r:
        y = (l + r) / 2
        if ok(x, y):
            r = y
        else:
            l = y + 1
    if ok(x, l):
        update_answer()

The problem is that if we naively implement the predicate ok by traversing the given array, it will be of O(n) time and the overall time will be O(n^2 log(n)), which is hopeless.

One important intuition to optimize it is to sort the given array and implement an ok in O(log(n)) time (in other words, for determining the feasibility of a range [x, y], the order of the given array doesn't matter). Then the overall time becomes O(n (log(n))^2), which is good.

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

    During the contest I only came up with the O(n) implementation of the predicate ok, and I was even thinking about whether there are some kinds of "2D binary search" to eliminate the outmost enumeration of x, but I didn't succeed in that direction.

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

Div1 B can be solved using two pointers on $$$x$$$ and $$$y$$$ with a fenwick tree. Replacing all elements in the range $$$[x,y]$$$ with $$$1$$$ and those not in the range with $$$-1$$$, the partition can be made if the sum of all elements is at least $$$k$$$.

Submission — https://codeforces.com/contest/1630/submission/144278138

»
4 months ago, # |
  Vote: I like it +104 Vote: I do not like it

I had a different solution to 1630C - Раскрась середину, which I think was very simple and clean (I wrote 5-10 lines of code without any complex expressions, branching, or sorting events/intervals).

The idea is to define a DP array $$$f(i)$$$ = maximum answer for the subarray $$$[0, i]$$$, assuming $$$0$$$-indexing. Therefore, $$$f(0) = 0$$$ and $$$f(n-1) = \textit{ans}$$$. Note that $$$f(i)$$$ never involves coloring $$$a_i$$$, because it's impossible to color either endpoint of your array.

Let's consider our choices for different ways to get candidate values of $$$f(i)$$$, assuming we know the previous values of $$$f$$$.

Option 1: $$$a_i$$$ has a previous occurrence at index $$$j < i$$$. We can perform the optimal solution for $$$[0, j]$$$, then color the $$$(i-j-1)$$$ elements strictly between $$$a_j$$$ and $$$a_i$$$, giving us a score of $$$f(j) + (i-j-1)$$$.

Option 2: If there is an instance of $$$a_i$$$ at some index $$$k$$$ such that $$$k < j < i$$$, so we can perform the optimal solution for $$$[0, j]$$$ except for leaving $$$a_k$$$ untouched, then color the remaining elements between $$$a_j$$$ (inclusive) and $$$a_i$$$ (exclusive), using the fact that $$$a_k = a_i$$$. This gives us a score of $$$(f(j)-1) + (i-j)$$$, which is the same expression as in the previous paragraph.

Option 3: We can always ignore the last element, giving us a score of $$$f(i-1)$$$. This can be creatively re-written as the same expression as before: $$$f(i-1) + (i - (i-1) - 1)$$$.

Therefore, we have the following simple quadratic DP: $$$f(i) = \max_j \left[f(j) + (i - j - 1)\right]$$$, for $$$j$$$ such that either $$$\text{first}(a_i) \le j < i$$$ or $$$j = i-1$$$. Equivalently, $$$\min(\text{first}(a_i), i-1) \le j < i$$$.

quadratic (TLE) code

In order to optimize this, we make the following rearrangement: $$$f(i) - i = -1 + \max_j \left[f(j) - j\right]$$$.

Setting $$$g(i) = f(i) - i$$$ gives us $$$g(i) = -1 + \max_j [ g(j) ]$$$. This can be very easily implemented using a segment tree to compute $$$\max_j [g(j)]$$$, and our answer is $$$f(n-1) = g(n-1) + (n-1)$$$.

Final implementation

You can read my full submission (including IO and templates) here: 144275521

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

    Thanks!!! Feeling confused when trying to read the official editorial

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

    I am confused about your Option 2: for first(i)<j<i, why can we always assume that the optimal coloring of j always includes coloring first(i)? Or why it won't be the optimal coloring for i if using a j whose optimal coloring don't include coloring first(i)?

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

This is the best editorial writtern in the history of codeforces , thanks a lot

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

Check out my solution for 1631B. I think it's a good bit simpler than the one in the tutorial. Same core logic I think, though.

144280684

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

Div 2 B : Fun with Even subarrays video Editorial LINK

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

This has been the most organized editorial that I have seen so far with solutions of different complexities and hints, Great work

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

Thanks everyone, for this fun and amazing contest.

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

hello BrayanD in problem And Matching Constructive approach (easier) The code of this approach in Case 2 : ( k > 0 && k < n — 1 ) if condition ( i != 0 || i != small_k ) should be ( i != 0 && i != small_k )

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

    In fact, I think that the condition is not important. It can be removed. Anyways, I fixed the solution code. Thanks for noticing it and telling me.

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

nice solutions !!! thank u!

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

https://codeforces.com/contest/1631/problem/C Can anyone help me in understanding why I am getting the wrong answer, If I directly output the answer instead of storing all the results for a particular test case in a vector and then print the answer. https://codeforces.com/contest/1631/submission/144287685 (solution with using the vector [Accepted]) https://codeforces.com/contest/1631/submission/144285733 (solution without using the vector[Wrong Answer])

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

Nice editorial

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

For 1631B — Fun with Even Subarrays, I implemented something similar to O(n) solution described, but instead of reversing the array. I traversed backwards, while jumping the maximum span possible at each iteration. Can you suggest some testcases for which it fails? https://codeforces.com/contest/1631/submission/144231299

wrong answer 19821st numbers differ - expected: '3', found: '0'

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

    Submission I used same approach it passed. Your solution might be failing at some edge case.

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

      Thank you stranger! This tool is helpful. But there's a very weird problem I fail to decode. Locally, I run the failing test case with 10 cases (t=10) and I get a value of 2 for the last testcase. But If I run the last test case only by passing (t=1) I get a value of 3 which is correct. I'm not able to understand this behaviour.

      https://ibb.co/w6nB8B6 (img link)

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

        That's a pretty common mistake. Whenever your code passes single testcase inputs, but fails on multi test case inputs, there are only 2 possible reasons.

        1. Incorrect initialization of global variables.
        2. Early termination

        Since you aren't using any global variable, it leaves us with Early Termination, and in your submission, you can see that when $$$n == 1$$$, you print the answer as zero and move to the next iteration using continue, but you don't really take the full input for that test case. This messes up the future testcases.

        Don't mix cin/cout with continue/break (or be attentive when you do that).

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

Can anyone explain me what does this statement mean "Select some subarray from a of even size 2k that begins at position l (1≤l≤l+2⋅k−1≤n, k≥1) and for each i between 0 and k−1 (inclusive), assign the value al+k+i to al+i."

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

    It means you can choose a subarray of even size and make any element in first half equal to the corresponding element in second half. Eg array a->[1,2,5,4,7,8,9,0] Here, you can choose the subarray starting at index 3(1-based) array b-> [5,4,7,8,9,0] and make b[1] = b[4], b[2] = b[5], b[3] = b[6]

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

      Bro can you explain this "al+k+i to al+i"? with values of l,k and i

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

        In above subarray b is of length 6. Therefore 2k = 6 => k = 3.The subarray starts at index 3 (in the original array a),So l = 3 (starting point of first half) and l+k i.e., index 6 is starting point for second half. Now i goes from 0 to k-1, and we make a[l+i] = a[l+k+i]

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

Can someone explain me B , I couldnt get it

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Could anyone explain solution of Div1 C ?

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

Can anyone hack my code for div1 problem C? I'm failed in test 3 but I don't know what's wrong.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
int t,k,m,n; 
int a[maxn];
int r[maxn];
signed main() {	
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>a[i];
		r[a[i]] = i;
	}
	int ans = 0;
	int r1,r2=0;
	for (int i=1;i<=n;i++) {
		r2 = 0;
		r1 = r[a[i]];
		if (r1==i) continue;
		for (int j=i+1;j<=r1;j++) {
			r2 = max(r2,r[a[j]]);
		}
		if (r2==r1) {
			ans += r2-i-1;
			i = r1;
			
		}
		else {
			ans += r2-i-2;
			i = r2;
		}
	}
	cout<<ans;
}

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

Is the complexity not NlogN*longN for Question D

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

Thanks buddy!!, i apriciate your initiative, it is very much helpfull!!

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

There is another easier (as I consider) solution for Div1 D.

Let's look throw elements with position $$$x \pmod g$$$. If there are even number of elements $$$a_i < 0$$$ — we can make all elements $$$\geqslant 0$$$. And if there are odd number — we can make all elements $$$\geqslant 0$$$ except 1, any of them.

Ok, let's the first set will be remainders $$$\pmod g$$$ with even number of negative elements and the second set — remainders with odd number of them.

And it turns out, that the optimal set of negative elements in the final answer — the 1 element with minimum module from every remainders of the first set or from every remainders of the second set.

The solution with very simple code. 144363709

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

    can you please explain intution behind this approach.

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

      Ok, when we invert the segment — we change (parity of negative elements) of each remainder. (If some of these elements are $$$0$$$, let's imagine, that they will be $$$-0$$$ now: it doesn't really matter).

      And the second thought — we can invert any two elements at a distance $$$g$$$. Because we can invert $$$[x, x+g-1]$$$ and $$$[x+1, x+g]$$$. And, of course, we can start to repeat it: $$$(x, x+g)$$$ and $$$(x+g, x+2g)$$$ will turn into $$$(x, x+2g)$$$ and so on.

      Finally, we can invert any of pair elements with the same remainder $$$\pmod g$$$. And from here my solution quickly follows :)

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

      Div. 1 D is a harder version of https://atcoder.jp/contests/abc125/tasks/abc125_d. I started with the idea in the first official solution for that problem and ended up with exactly the same solution presented here.

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

For Div2 C, I got the first 2 cases, but the third case was tricky

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

Can someone help me with my code div2 problem E . I'm stuck at test case 3 (wrong answer). Although I think my algorithm is correct.

include <bits/stdc++.h> using namespace std; define ll long long define lld long double define ff first define ss second define pb push_back define mp make_pair define fl(i,n) for(int i=0;i<n;i++) define rl(i,m,n) for(int i=n;i>=m;i--) define pi 3.141592653589793238 define vr(v) v.begin(),v.end() define rv(v) v.end(),v.begin() define Code ios_base::sync_with_stdio(false); define By cin.tie(NULL); define Asquare cout.tie(NULL);

ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);} ll lcm(ll a, ll b){return (a/gcd(a,b)*b);} bool sorta(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);} bool sortd(const pair<int,int> &a,const pair<int,int> &b){return (a.second > b.second);} void printarr(ll arr[], ll n){fl(i,n) cout << arr[i] <<endl;} ll binaryToDecimal(string n){string num = n;ll dec_value = 0;int base = 1;int len = num.length();for(int i = len — 1; i >= 0; i--){if (num[i] == '1')dec_value += base;base = base * 2;}return dec_value;} bool isPrime(ll n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;} bool isPowerOfTwo(int n){if(n==0)return false;return (ceil(log2(n)) == floor(log2(n)));} bool isPerfectSquare(ll x){if (x >= 0) {ll sr = sqrt(x);return (sr * sr == x);}return false;} ll moduloMultiplication(ll a,ll b,ll mod){ll res = 0;a %= mod;while (b){if (b & 1)res = (res + a) % mod;b >>= 1;}return res;} ll powermod(ll x, ll y, ll p){ll res = 1;x = x % p;if (x == 0) return 0;while (y > 0){if (y & 1)res = (res*x) % p;y = y>>1;x = (x*x) % p;}return res;}

int main() { ll n; cin>>n; vector v; ll x;

fl(i,n) { cin>>x; v.pb(x); }

unordered_map<ll,ll > m; vector<pair<ll,ll> > vec;

ll u=1;

fl(i,n) { if(m[v[i]]==0) { m[v[i]]=u; vec.pb(mp(i+1,0)); u++; } else { vec[m[v[i]]-1]=mp(vec[m[v[i]]-1].first,i+1); } }

ll le=vec.size();

// fl(i,le) // cout<<vec[i].ff<<" "<<vec[i].ss<<endl; // cout<<"xxx"<<endl;

vector<pair<ll,ll> > l; ll r=0; for(;r<le;r++) { if(vec[r].second!=0) { l.pb(vec[r]);r++;break;} }

// cout<<"r"<<r<<endl; ll j=0; for(ll i=r;i<le;i++) { if(vec[i].second!=0) { if(vec[i].first> l[j].second) { l.pb(vec[i]); j++; } else if(vec[i].second>l[j].second) {
l[j]=mp(l[j].first,vec[i].ss); } } }

ll len=l.size();

// fl(i,len) // cout<<l[i].ff<<" "<<l[i].ss<<endl;

ll count=0;

fl(i,len) { if(v[l[i].first-1]==v[l[i].second-1]) { count+=l[i].second-1-l[i].first; } else { count+=l[i].second-1-l[i].first-1; } } cout<<count;

}

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

Nice editorial! Appreciate it!!

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

Nice editorial, If anyone wants video editorial for problem DIV 2D
Link

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

What is the expected rating of problem C?

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

1630-D is really an impressive problem!!

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

if i have the edges that are making my graph non-bipartite ,how can i see which is the minimum number of vertexes to erase ,so it becomes bipartite?