i feel so dumb after seeing B's solution because I used topological sort and then sorted all the elements with equal entry times in descending order

B killed me and C buried me :(

Why the B looks easy here:(.I've done converting the undirected graph in directed based on pi<pj and then i had applied topological sort .Feelin dumb man

How did every single person predict that B was lower rated than C? C was much easier IMO. I think we need more lower rated testers.

C's solution can be put fairly simple:

Answer will be of the pattern:

[1, 1, 2, 3, 4, ..... ,n-2, 1]

then the max length f(a) is 3

and the count g(a) is: (n-2) + (n-3) = 2*n-5, which is greater than n for n >= 6.

The difficulty distribution of this match is simply a disaster.

Another solution for $$$C$$$ is for $$$n > 6$$$ construct the array $$$1,2,$$$ $$$[3...n - 2],$$$ $$$1,2$$$. Most elements will be part of two palindromes of length $$$3:$$$ $$$1,x,1$$$ and $$$2,x,2$$$. For $$$n = 6$$$ use the one in the example.

Edit: Nevermind I just realized this was mentioned in the editorial.

In C, If you realise that g(a) is 3n-11 for 6, and notice that 11 is a constant, and for each additional n, it will increase by 3, you notice that using the first construction directly solves the problem.

1,1,2...1,2 works because it follows 3n-11.

Any idea which test case is failing for my submission: 301434979 for Problem B. I used a bubble-sort-like approach.

It seems like i completely overcomplicated D, because i solved it in $$$O(nA^2 + A^4)$$$.

For C, I just took sample solution with 15, it already gives 190 and just pushed numbers in the end like 16 17 18 ... n.

The same way, for 15 > n >= 9 I took sample solution for 9, as it gives 24.

For 6 they already gave answer.

So I only needed to solve by hand 7, 8, which I did on paper.

why lasts codeforces rounds are random ? rarely to find topics .. number Theory or graphs in first 3 problems ?!! can any one explain

What's with the constraint of n in C? Why is it so small?

Also you can just put random distinct numbers at the end of the 3rd sample answer, as g(a)=190 which is >=100

Tried sort in B and failed, using another 30 min to ponder another graph solution (almost like dijkstra)... absolutely overkill for B.

Learned, though C is really too easy for some reason.

Still I conclude C << B.

A different way to approach D:(Probably easier?)

Solution :

My submission

Hope you understand the solution, if you have any queries feel free to ask, and I'll try to help if possible.

Very nice problem F!(however probably too hard for div2)

I don’t understand the editorial for D. For even length subarrays, when we are testing for x as the median, the bad scenarios seems a lot more than what the editorial depicts.

For instance, if we are testing for 9, the array 1 1 1 9 is certainly bad, but the number of numbers less than or equal to 9 is 4, not 2 as in the editorial .

I have the dumbest solution using BST to solve B
301463165

Why we only update the cnt array when a[i] equal to chosen digit? I may think that when the conditieon is enough when we firstly seen the digit x? Like: n = 6, a = {1, 4, 4, 3, 1, 4} with chosen digit = 3. It only update when we at index 4 (a[4] = 3), so that we have {1, 3, 4, 4}. But there are also in the index 6, we can have an bad array {1, 1, 3, 4, 4, 4}, but in this case the author not update the cnt array.

Code:

if(a[i] == x) {
  while(j <= i) {
    cnt[pref[j]]++;
    j++;
  }
}

The constraints in the question C were kind of redundant because, I solved directly from visible cases. The answer for n=15 the third case they have given is 198, so I directly gave the same array as output for n>=15 followed by 16, 17, 18... until the required length is achieved. And for n=9 => the answer was 24, so 9-15 range is also sorted. So, only ones remaining are 7,8, we can manually generate that by appending some numbers after the given array for n=6.

In the solution of D, it's a little confused by using the term "median". It took me some time to realize "median" means the (r-l+1)/2-th smallest number here.

Also, this intended solution is interesting since the observation is apparent but useful, and it seems that only few contestants came up with it.

i didnt realize that the solution for b was that simple. i have just started thats why ig. i did something like trying to find a correct candidate from indexes 1 to n in p. if the number of pairs that can be formed from this index to the last is > than the number of edges our candidate should be connected to and also the number of elements that are larger than our candidate that have not been used yet are also greater than the number of edges our candidate should be connected to then skip this candidate and move on to the next one . since that would mean we would definitely connect an edge that is not supposed to be connected. i converted the undirected to directed first for that and then did it. well the contest time was over by the time i did that lol. but it did work when i submitted it later.

I did very dumb solution for C.

For n = [6...11] find answer by hand.

For example, I realized that the prefix of "AABCABCDCDD" where different characters stands for different number gives correct answer, and I used it. As you see, we just need 4 different numbers.

Now, divide n to small parts: many 6 and one x from range [6...11]. Solve for small parts separately, with different set of numbers. Then concatenate them to one big array. It's not hard to see it will give you correct answer.

My submission.

E is solvable with xor hashing as well: 301474893

in problem C 1 1 2 3 4 5 ... 1 the maximum f(a) is 3 the first and the last one will add n-2 and the second and last one will add n-3 so 2*n -5 it worked for n>=6

i did something very different for C and it took me an embarrasing amount of time, first ans = [1, 2, 3, ..., n].Then ans[n-1] = 1 and ans[(n-1)//2] = 1, essentially ans = [1, 2, 3, ... (n-1)//2 , 1, (n-1)//2 + 1 ,..., n-2, n-1, 1] and it got accepted as those 1 essentially made f(a) = 3 and g(a) = 2*(n-2).

We can even solve D by counting the good subarrays for every fixed median and sum them up.

Here is my submission.

https://codeforces.net/contest/2056/submission/301477712

5 00000 00010 00000 01000 00000 for this input jiangly's solution gives 5 3 4 2 1 while solution in editorial gives 5 4 3 2 1 and both solutions get accepted how is 'p' unique then for this case

Thanks for highlighting the unusual limits.

I don't seem to have received any rating yet — was this contest unrated?

How to solve the C with Binary Search?

Thanks in advance!

From F:

For a fixed $$$\text{cnt}$$$, the number of ways to order a is $$$\binom{n}{\text{cnt}_0, \text{cnt}_1, \ldots, \text{cnt}_{m - 1}}$$$. By Lucas's theorem the contribution is odd iff for each set bit in n there is exactly one i such that $$$\text{cnt}_i$$$ has this bit set, and $$$\sum\limits_{i = 0}^{m - 1} \text{cnt}_i = n$$$. In other words, $$$\text{cnt}$$$ has to partition all set bits in $$$n$$$.

Can someone explain this more in detail? I can't connect the dots between Lucas's theorem and this formula.

you don't have to consider n = 6 / 9 /15 separately.

1 ,1 ,3 ,4 ,5 ,... ,n-1 ,1

has f(a) = 3

and 2*(n-3) + 1 = 2n-5 palindromes! so g(a) > n for n >= 6 which fits the constraints

301414951

Solved C like nothing, bricked at B. Nice Problemset. Here's my weird solution to C. Solution

For D, I was like with a median of x: |the number of elements larger than x — the number of elements smaller x|<|the number of element of x in the sequence|. And I cannot find a good algorithm. It was too counterintutive for me to count "bad subarrays".

i think i have a better solution for c, i hope you'll like it :D it only require hardcoding for n=6 i just messed it up during the contest in second for loop where i started it from n/2 and not n/2+1

anyways good contest ~~~~~~~~~~~~ //this is code

include <bits/stdc++.h>

using namespace std;

define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

define ll long long

void solve() { int n; cin>>n; vectortemp={1 ,1 ,2 ,3 ,1 ,2}; if(n==6){ for(auto it:temp){ cout<<it<<" "; } cout<<endl; return; } vectorarr(n); int j=1; for(int i=0;i<=n/2;i++){ arr[i]=j; j++; } j=1; for(int i=n/2+1;i<n;i++){ arr[i]=j; j++; } for(auto it:arr){ cout<<it<<" "; } cout<<endl;

}

int main() { fio; ll t; cin >> t; while (t--) { solve(); } return 0; } //this is code ~~~~~~~~~~

I solved C differently. In sequence [1,2,3,…,n] I changed a[⌊(n+1)/2⌋]=1 and a[n]=1, so in this new sequence f(a)=3 and g(a)=n-3+n-2=2n-5 which is enough for n≥6. Here's my solution 301421526

for c just create sequence such that length of longest palindrome is 3 , putting 1 ....1 1 here all elements in between create 3 length palindrome now we have (n-2) palindromes ready now do it with 2 it will always exceed n>

~~~~~~~~ t = int(input()) for q in range(t): n=int(input()) buffer=[0]*(n+1)

adj=[buffer]
for i in range(n):
    adj.append(list('0'+ input()))
for i in range(len(adj)):
    for j in range(len(adj[0])):
        adj[i][j]=int(adj[i][j])

#print(adj)
arr=[]
for i in range(n,0,-1):
    arr.append(i)
#print(arr)
i=1
val=None
while(i<n):
    j=i-1
    #print(i)
    val=arr[i]

    while j>-1:
        if adj[val][arr[j]]==1:

            j-=1
            if j==-1 or (j>=0 and adj[arr[i]][arr[j]]==0):
                #print(j+1,val)
                arr.insert(j+1,val)
                #print(arr)
                arr.pop(i+1)
                i+=1
                break
        else:
            i+=1
            break
print(*arr)

~~~~~~~~~~~~~~~~

I did B this way: first arrange in descending order 5 4 3 2 1 now 4-->5 so 4 5 3 2 1 now 3 is connected to 5 but not 4 so: 4 3 5 2 1 now 2 is to 3 and 5 4 2 3 5 1 now 1 is to 3 5 4 2 1 3 5.

managing the loop parameters was a bit confusing but it is easy to get and works all good.301490247

geeked on b

I am too dumb for Smart contests.

I did so dumb for C.I never think that f(a) can be 3 for any input,I can't solve constructive problems:(

In B, i came up with the idea that if can device some sort of point or ranking mechanism for each vertex of the graph based on the edges the vertex makes, either to a greater value vertex or a smaller value vertex. Then i can use those points to arrange them in order.

~~~~~~~~~~~~~
// cpp
vector<pair<int,int>> vpr;    
for(int i=0;i<n;i++)
{
    cin>>s;
    int pnt=0;
    for(int j=0;j<n;j++)
    {
        if(j<i&&s[j]=='1')
        {
            pnt++;
        }
        if(j>i&&s[j]=='0')
        {
            pnt++;
        }
    }
    vpr.push_back({pnt,i+1}); 
}
vst(vpr);
for(int i=0;i<n;i++)
{
    cout<<vpr[i].second<<" ";
}
 cout<<endl;
   ~~~~~~~~~~~~~~

I increased a point if there was an edge from the current vertex to a smaller vertex, and increased a point when there was no edge from the current vertex to a greater vertex.

How come c is this simple,

void solve(){
	int n;cin>>n;
	vi pres(n+1 , 0);
	pres[1] = 1;
	pres[2] = 1;
	pres[3] = 2;
	pres[n-1] = 1;
	pres[n] = 2;
	int counter = 3;
	rep(i , 4 , n-2){
		pres[i] = counter;
		counter += 1;
	}
	rep(i , 1 ,n )cout << pres[i] << " ";
	cout << "\n";
}

wasted whole time on B noooooooooooooooooo.

Why the type of was_single is int in the solution of E

为什么在 E 题题解里面 was_single 的类型是 int

the wording of B's problem statement is extremely confusing, especially when the notes switch back and forth between i, j, pi, and pj

1 4 0110 1001 1000 0100

For this test case B no. solution doesn't work!! Why??

My B solution constructs a btree with a starting root node of 1

Then it will iterate nodes i from 2 to n

For each i, it will be attached to the btree like this:

void attach(btree* root, i):
    if adj[root->val][i]:
        if root->right == null:
            root->right = new node(i)
        else:
            attach(root->right, i)
    else:
        // same as above, but for root->left

Then the answer is just the inorder traversal of this btree.

Code: https://codeforces.net/contest/2056/submission/301423733

void solve()
{
    int n, m;
    cin >> n >> m;
    int prevx, prevy;
    ll lastx, lasty;
    ll firsty, firstx;

    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            cin >> prevx >> prevy;
            firstx = prevx;
            firsty = prevy;
            prevx = firstx;
            prevy = firsty;
        }
        else
        {

            int tempx, tempy;
            cin >> tempx >> tempy;
            lastx = prevx + tempx;
            lasty = prevy + tempy;
            prevx = lastx;
            prevy = lasty;
        }
    }
    if (n == 1)
    {
        cout << m * m * 2 << endl;
        return;
    }
    cout << 2 * ((m + lastx - firstx)) + 2 * (lasty - firsty + m) << endl;
} 

this code is giving me error on test case 2 what am i doing wrong here

Can someone explain why my soln is wrong ? Thanks

https://codeforces.net/contest/2056/submission/301536267

Submissions of C is more than B. That denotes which one is more difficult.

another correct solution for C was to print 1 1 2 3 1 2 3 1 2 3... didnt know that it worked lmao

nice problem!but i think E is too simple

Problem C. Palindromic Subsequences. Video Editorial Solution Link : https://youtu.be/LmlZuqndrHg?si=Lmv00zHhXvMck2WQ

For the D solution, could someone explain what does the vector pref and cnt in the code represent?

This is best contest for me. I became expert in it.

for F2, it is useless to calculate SOSDP and can be computed in a linear time using bitwise arithmetic.

$$$O(k\log m)$$$ reference code, available more discussion were easily optimised to linear time :D

there is a easier way to solve problem B sunbmission

D's editorial just blew my mind , such an elegant solution !

for D, i fixed the median $$$x$$$ ,and tried to count the number of good subarrays whose median is exactly $$$x$$$.
however i failed.
so i wonder could someone give me a solution to forementioned subproblem

Hi, I have an issue with problem B.

For the input:

1
4
0110
1011
1100
0100

there are several solutions that got AC but produce different results. For example:

• This solution outputs 2 1 4 3
• This solution outputs 1 3
• This solution outputs 1 4 2 3
• This solution outputs 0 4 0 3
• Finally, the solution from the editorial outputs 4 1 2 3.

These are the top 4 solutions. First of all, this contradicts the problem statement, which says "It can be proven that permutation p can be uniquely determined". Secondly, none of these "permutations" seem to resemble the original graph.

So what's happening here? Can someone help me understand what is wrong?

in sollution D line 8 (this shoulld be if instead of iff) "iff ∑i=lrbi=0" ."

For problem D, my idea was to count all subarrays of odd length using sum of first n terms formula of AP and then good subarrays of even length, but the problem with this approach is the given constraint, n can be 10^5. So If I will calculate for all even length subarray one by one then I'll get TLE.

Editorial is saying that count number of bad subarrays then subtract it with total number of subarrays. How this approach is avoiding traversing the array again and again for all subarrays? Also, didn't got the intuition that why someone should think in this direction.

Is there any other approach which is easy to understand and intuitive?

Doubt for problem D.

Approach: I want to count total number of median arrays for each median. So basically,

l - 2x >= 2 [less, less, less, m, m, >=m, >=m, >=m] (for array size 8 having median m)

l - 2y >= 2 [<=m, <=m <=m, m, m, more, more, more] (for array size 8 having median m)

x: total number of elements strictly smaller than the current median

y: total number of elements strictly greater than the current median

l: size of the array under inspection(here is 8)

From this we can see that if we store values of i - 2*x and i - 2*y then for some index j we can query for index i falling on same parity(if the current index is odd only query odd or vice versa. did this so that length is always even and I don't count for odd index) having values <= 2.

Basically current index j and some seen index i,

$$$j - 2*x1$$$ we have now [x1: from start till index j, how many are less than current median]

$$$(i-1) - 2*x2$$$ we have stored [x2: from start till index i, how many are less than current median]

If we subtract we get,

$$$j-(i-1) - 2*x$$$ [x: from i to j how many elements are less than current median]

So query at each index j for values such that (i-1) - 2*(x2) should be <=2

So now the problem is given an array like [ {-1,-2}, {-4,-6}, {-8,-2} ... ] find the count of all values for current pair(mx,my) such that x <= mx-2 and y <= my-2. Looks like a 2D co-ordinate search. Nice.

Either you can find set union or 2D search. I went for the latter and used 2D segment trees. I got a time complexity of $$$O(10 * n * log^2(n))$$$ [ 10 median, for each array element, 2D segment tree search + insert ] which is not passing as you can see here. (Adding n for -ve values. The value can be max n - 2*n which is -n add n to make it 0. So 0 to 2n)

Can someone drop a little hint. I will really appreciate it. I don't really understand the PIE even after reading the editorial and its very counter-intuitive for me.

A better way to code problem C without handling n=6 case separately : 302147317

For anyone who is stuck trying to understand the solution to D:

When it says "If there is no x in [l,r], then the median of a[l,r] trivially can't be equal to x.", it is refering to an even array where the "median" is the left part of the median. Meaning that we want to find an array where the left median is x and the right is not x (making it a bad array). We do not need to check for cases like [5, 7] when x == 6 because it is caught when x == 5, therefore we are only concerned with cases of b[l, r] == 0 when there contains x.

A side note: the solution doesn't need to check for when x == 10 since the b array would always be full of -1 since the bounds of a[i] are always less than or equal to 10.

Editorial solution for problem C is kind of overcomplicated. Consider this sequence of length n for n >= 6: [1 1 2 3 4 ... n — 2 1] We have n — 2 + n — 3 = 2n — 5 palindromic subsequences of length 3; as it must be larger than n: 2n — 5 > n => n > 5, which meets the constraint. Hence, we just need to output the sequence: [1 1 2 3 4 ... n — 2 1]

How to solve problem d using dp ?

Alternative solution to question C (using segment Tree):

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int t[4 * N];

void upd(int p, int x, int tl, int tr, int v) {
    if (tl + 1 == tr) {
        return void(t[v] = x);
    }
    int tm = tl + tr >> 1;
    if (p < tm) {
        upd(p, x, tl, tm, v * 2 + 1);
    } else {
        upd(p, x, tm, tr, v * 2 + 2);
    }
}

int get(int p, int tl, int tr, int v) {
    if (tl + 1 == tr) {
        return t[v];
    }
    int tm = tl + tr >> 1;
    if (p < tm) {
        return get(p, tl, tm, v * 2 + 1);
    } else {
        return get(p, tm, tr, v * 2 + 2);
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tst;
    cin >> tst;
    while (tst--) {
        int n; cin >> n;
        upd(n - 1, 1, 0, n, 0);
        upd(n - 2, 1, 0, n, 0);
        for (int i = 0; i < n - 2; ++i) {
            upd(i, i + 1, 0, n, 0);
        }
        for (int i = 0; i < n; ++i) {
            cout << get(i, 0, n, 0) << " ";
        }
        cout << "\n";
    }
    return 0;
}