Great contest! Thank u!)

Great contest and great problems ! But weak test cases for problem A div1 ...

Deleted

It's a good contest! I like these problems! Thank you:-)

Really weak pretests for Div2 C.

I don't know if i'm too weak or not, but to me this must have been the hardest round that I have participate in

Weak test data (pretests) for problem 'C' Div.2 or 'A' Div.1 made a lot of solutions (more than usual) get WA during system tests . I hope next round's test data will be much stronger . Anyway,it was a great round and I hope everyone got what they wanted :)

Can someone explain D, please? Can you prove why the claim: "the Young diagram can be partitioned into domino if and only if the number of white cells inside it is equal to the number of black cells inside it." is true? Also, why was the example of a "basic" diagram provided?

So, i am a newbie to giving contests. This was my 5th contest and i wasn't able to solve any one of them this time too. Is that normal and will i be able to become good at this anytime soon if i practice. I have been practicing a2oj ladders lately. Everyone's feedback and support is appreciated.

For div2D, why doesn't this solution work?

We start from the first column and we move to the right. There are several cases:

• If our current column has even squares we add it as it is (ie. $$$ans += arr[i] / 2$$$)
• If it has odd, we do the following: We try to find the next column with odd squares and if in between them there are even columns, we can use all of them and get an optimal answer (ie. $$$ans += (sum-of-all-squares-we-found) / 2$$$). And then we move to the next column! (you can see that if you try an example)
• Otherwise, if there are odd (or it is the last column that has odd squares), there is no way to use the 1 square left (or am I wrong?), so we do the same as the 1st case (ie. we add ans += $$$arr[i] / 2$$$) and we move forward.

I could not find any test cases that break this greedy. Can you help me? Thanks!

Here is my code: https://codeforces.com/contest/1269/submission/67367653

Problem A. I spent half an hour on you. Good round.Thank you 300iq!!!

Can someone hack my Div2C / Div1A or is it actually O(n) code?

Don't you think that samples in Div2A are a bit too suggestive xD?

Can we solve Div2D using dp?

Is Div1B Div2D editorial not completed?

"Just because if you have more white cells (case with more black case is symmetrical), you can take the first column with more white cells than black cells and delete the last cell of this column" — I think it is not true if you have equal columns since resulting diagram can no longer be Young one. But if you preced that with argument of dealing with equal columns then you will be fine I think.

Excuse me, there might be a small problem in the editorial of 1269E:

[After that, let's say that $$$x≤k$$$ is zero, and $$$x>k$$$ is one.]

[Then you need to calculate the smallest number of swaps to make segment $$$1,1,…,1$$$ of length $$$k$$$ appear in the permutation.]

Isn't it segment $$$0,0,...,0$$$ of length $$$k$$$? I'm confused.

UPD: Fixed.

Can anyone explain me div2 D

can someone exlain me Div2B?

in div2 E what is "si"?

What was test case 7 for Div2C?

Can someone explain div2 B to me , i didn't understand the editorial

Pls explain Div 2 B (with code if possible) I'm stuck:(

More explain on Div.2 problem E, please.

Can anyone prove that editorial solution of div2C gives correct answer?

Could anyone here help me figure out what's wrong with my solution for Div 2 (C)? I have tried to follow the editorial here.
Link.

i think the word 'ciclycally' is a russian word. as a non-russian speaker, i find the use of the word confusing. you should have used a better word, such as 'cyclically.'

edit: the typo was fixed. i don't think my comment warrants such many downvotes, i was pointing out the typo in a somewhat sarcastic way.

For Div2 C, we can take the first k digits as a number and repeat it for length n, and then add one to that number and repeat it again for length n . This is optimal and i know it works.

But i am unable to proof that why it'll always work, can anyone help me with a proof?

you have 300iq s

In problem B div2 I just generated all possible x's and took the most frequent one. Is that right? 67350595

I really liked 1269D. To me, the solution seemed very non-intuitive though. (Like I couldn't understand how that train of thought could originate in the first place).

One question I had about it was, wouldn't this chessboard coloring logic be applicable even if the heights columns were not in a non-increasing order? I'd like to understand why this logic would fail in that case.

Any help would be appreciated.

I always look forward to contests with a single writer behind them and 300iq did not disappoint with this. The questions were really good !

How to solve the bonus question of $$$B$$$ ?

I have written code for div2C as per logic: 1) First, simply repeat 1st K characters and compare 2) If new_string is >= old string, print it 3) Otherwise, look for the index from first K character (starting from last one) for which if you iterate over K-sequence of (index, index+k..), then old_str > new_str. If so, increase the character value at that found_idx and at other position in its K-sequence order. After this, make all character K-sequences in between found_idx and K to '0'. I couldn't find the flaw in above logic and thus couldn't see why am I getting WA. Test case on which it's failing is pretty HUGE itself. I looked for other test cases from accepted solutions but still got the correct answer. Can someone please help me out of this trauma? My submission Link

Clarifying the editorial's $$$Div1B$$$:

Suppose you mapped the diagram to a chessboard, where the white cells count is $$$w$$$ and $$$b$$$ is the black cells count. We can see that the upper bound of dominoes we can put is $$$min(w,\, b)$$$. But what is the proof that we can always achieve it?

Let $$$a_i$$$ be number of available cells in the $$$i^{th}$$$ column. Starting with the original diagram, try always to place a vertical domino in a column i where $$$a_i>a_{i+1}+1$$$ (decreasing $$$a_i$$$ by $$$2$$$), or a horizontal domino on top of 2 columns $$$i$$$ and $$$i+1$$$ where $$$a_i=a_{i+1}$$$ and $$$a_{i+1}>a_{i+2}$$$ (decreasing both $$$a_i$$$ and $$$a_{i+1}$$$ by $$$1$$$).

Both of the previous $$$2$$$ operations will not change the property of $$$a_i\geq a_{i+1}$$$, and will not change $$$w-b$$$. If you can't do any of the previous 2 operations any more, then you have reached a configuration with values of $$$a_i$$$ being $$$t$$$, $$$t-1$$$, ..., $$$2$$$, $$$1$$$. In this configuration $$$b\neq w$$$, this means that $$$b\neq w$$$ from the beginning (So if $$$b=w$$$ from the beginning, you could have filled the entire diagram).

If you didn't fill the entire diagram, how can you still achieve $$$min(w,\, b)$$$? Assuming without loss of generality that the column with $$$a_i=1$$$ (the $$$t^{th}$$$ column) has a white cell, we can see that $$$w-b=\lceil \dfrac{t}{2} \rceil$$$. So if we kept putting vertical dominoes, we will end up with leaving exactly $$$\lceil \dfrac{t}{2} \rceil$$$ cells (the number of columns with odd $$$a_i$$$).

300iq can you please elaborate on how to solve problem E of Div2

Can anybody please explain me how to get second value for each k in div2 E how to do it with segment tree

What was the logic you all used in div2a i am having hard time understanding tutorail.its normal to not able to solve que i can solve a b sometimes but sometimes i have problems,

Can anyone tell me what is wrong with dp approch in div 2 D https://codeforces.com/contest/1269/submission/67394114 I have first converted a[i] to a[i]%2 that is making the sequence 100110... 1 if odd 0 if even. Then I note compute dp[i] as the min no of squares up to column i that can go unfilled.For this I use the following observations, 1. we can use the full column of even length (dp[i]=dp[i-1] ) 2.if columns are of the form 111..m times (i.e all odd), if m is even then all the squares can be filled, if m is odd 1 square is not filled. 3.sequence of the form ( 1.. even times 0..1 ) can be completely filled.(you can take example of 3 2 2 3) Am I missing something??

Will an editorial for all problems on the actual ByteDance contest be posted?

In Div2 D, why do we have a contradiction?
Does the proof still work in this case?
2
1 1
I think it has an equal number of white and black cell.

Can anyone please tell why O(n2) solution doesn't work in Div2 B? Please have a look at my submission and help.

Weak systests in Div2B. Some test cases where multiple x values existed, submissions have passed without taking the minimum of them. Example test case:

4 4
1 1 3 3
0 0 2 2

Here both x=1 and x=3 are valid and output should be x=1. But hacked submission outputs 3.

#include <bits/stdc++.h>
#define ll long long
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define pb push_back
#define N 400015
ll y=0;
struct table{
    int val,id;
};
bool cmp(table a,table b)
{
    return a.val>b.val;
}
bool isPrime(ll n) 
{ 
    // Corner case 
    if (n <= 1) 
        return false; 

    // Check from 2 to n-1 
    for (ll i = 2; i < n; i++) 
        if (n % i == 0) 
            return false; 

    return true; 
} 
using namespace std;//coded by abhijay mitra
#define watch(x) cout << (#x) << " is " << (x) << endl
int main()
{
    ibs;cti;
    int n;ll m;cin>>n>>m;std::vector<ll> a(m,0),b(m,0);bool Check=0;ll x;
    for (int i = 0; i < n; ++i){
        cin>>x;a[x]++;
    }
    for (int i = 0; i < n; ++i){
        cin>>x;b[x]++;
    }
    if(m==2){
        if(a[0]==b[1] and a[1] ==b[0]){
            cout<<"1\n";return 0;
        }
    }
    if(n==1){
        if(b[0]==a[0])
            cout<<0<<"\n";
        return 0;
    }
    for (ll i = 0;; ++i){
        if(a==b){cout<<i<<"\n";return 0;}
        std::rotate(b.begin(), b.begin()+1, b.end());
    }
}

it got rte in question B. I used vector rotation. Where is issue?

Can someone explain Div2 D, the domino problem?

In div2D/div1A, I understood the soln but what is the significance of "column lengths will be in sorted order"?Even if it's not sorted this algo shud work right?

For Div2 E. I can not get how to maintain the second answer. Who can explain more, thanks.

I see a tag of "Graph Matchings" on DIV-2 D, how the problem can be solved using such an algorithm. I couldn't see any mention of it in the editorial though.

Can someone please explain for Div2E how to calculate the second value(mentioned in editorial)? And why does it work(taking the median)? I understood the inversions part but unable to get the median thing!!

How DIV2 B can be solved in O(N)?

How we can solve problem D using graph matching as given in tag ??

Div 1.C — Div 2. E

The editorial says (or at least i understood this) that it's optimal to put the first $$$k$$$ elements together (consecutive) with the minimum number of swaps and the sort them (and because they are together we have to add the number of inversions), but why is this optimal?

The approach for Div2 D is very interesting. Just wondering can we use it for the case when size of domino is 1X3 or 3X1 (coloring the board in 3 colors and finding the minimum number of occurence of those colors)?

so weak pretests 300iq can you explain me what the fuck is this do you really think it's normal?

P.S. Я не лайко попрошайка, но блин, уже -12, я не ожидала о_О

I think I have a clear proof on 1269D, so I would like to post my proof here.

Without affecting the answer, we add '0' at the end of the histogram.

We define two operations:

1. If the difference between neighbour two bars $$$ \geq 2 $$$, then delete vertical dominos to reduce the difference.
   Example: 8 7 3 1 -> 8 7 1 1 -> 8 1 1 1 -> 2 1 1 1
2. Choose the rightmost two neighbour bars that have the same height. Delete the horizontal domino on the top.
   Example: 3 2 2 1 -> 3 1 1 1 -> 3 1 0 0

Repeatedly do the operation (1) and (2) until you can't. Note if no neighbour difference $$$ \geq 2 $$$ or $$$ = 0 $$$, then all neighbour difference $$$ = 1 $$$, which is "basic diagram" stated at the editorial. We then can just choose all dominos vertically on the "basic diagram".

How to prove that if (a + x) mod m = b then x = (b — a) mod m

Another way of thinking 1268E. Consider the problem is: given the start edge, how many possible increasing paths from that start edge? If we can answer this question, then the solution of starting from a vertex u is the sum of solutions of edges that are adjacent to u.

For a given path e, it is easy to find all the feasible next paths of e. Namely, if the weight of e_2 is larger than e_1, then e_1 -> e_2 is feasible. The relations, such that e_1 -> e_2, form a new graph, which is DAG. Thus, it is trivial to find a solution to the new problem.

Note that the edges should be directional. You should convert the original undirected edge to two directed edges.

Can someone explain to me the idea behind Domino for Young?(Problem D Div 2). Can someone tell me why this greedy approach fails as well? https://codeforces.com/contest/1269/submission/68692876