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

even though the round has many problems, but no one can disagree that the problems were great and beautiful.

So there is no explanation on how this wrong solution passed the system tests?

I think using math formula in C more beautiful and easier than editorial

My solution using some binomial theorem and flt 125416610

It faster than editorial solution

can somebody tell me abt my WA https://codeforces.me/contest/1557/submission/125416469

Back to back segtree problems for the past 3 rounds.

Can you share the interactor as well? Would be interesting to know how does it decides where to move the king.

Randomized approach for E:

1. First, I put my queen at one of $$${(4,4),(4,5),(5,4),(5,5)}$$$(random choice)
2. For each move, I calculate $$$S$$$, which is the set of square which have a possibility of king's square. The size of $$$S$$$ is going small with the progress of the game.
3. Next, I make some random horizontal or vertical move. As a reminder, through this progress, $$$S$$$ is going small.
4. The important thing is, when we know where's the king, we can checkmate in $$$8$$$ turns.
5. For example, if we have only $$$5$$$ candidates of king's square, we can finish the game in additional $$$40$$$ turns. When $$$S$$$ becomes small enough, try all candidates.

It seems that this solution uses far less than $$$130$$$ queries, or can you kill my solution?

my code

Can someone elaborate what are the leaves of seg tree used in D? If rows would have up to 10^5 columns the seg tree would be trivial, but with 10^9 I wasn't able to come up with seg tree structure and editorial didn't help neither.

Even the "dpi,j = maximum number of rows (from row 1 to row i) that make a beautiful grid, and has 1 in column j at the last row." doesn't make much sense to me, as there can be up to 10^9 j indexes.

Solution for first three questions. https://www.youtube.com/watch?v=vBqSLVoXYsI

Love this round. Hoping to have more lovely rounds like this in the future. (◍•ᴗ•◍)❤

My heart starts bitting faster every time I see 5 problems in a contest. I was at the top of my abilities to solve C today

SegmentTree for D is such an overkill.

Hello , I didn't get the logic behind 2nd problem .

https://ide.geeksforgeeks.org/8684Y9kbwQ

• this is my idea . But got wrong output on pretest 2. Can anybody help me in this ?

Why do I get WA on pretest 2? https://codeforces.me/contest/1557/submission/125391145 Brief explanation: If $$$n$$$ is odd, the answer is just $$$(2^{n-1}+1)^k$$$. Otherwise, if $$$A_n(j)$$$ is the number of ways for the bits from 0 to $$$j$$$ such that $$$And\geq Xor$$$, I get the recursion $$$A_n(j+1)=2^{nj}+2^{n-1}A_n(j)$$$, which solves to $$$A_n(k)=2^{nk-k}+2^{kn-n+1}-2^{nk-n-k+2}$$$. Where is the flaw?

EDIT: found it, wrong recursion, it should be

AhmedEzzatG Do you mind looking into why this solution fails on D? I used the approach described in the editorial during the contest, but really have no clue why the 4th pretest is failing. It's giving me headache. Thanks.

125401562

really quick pure combinatorics sol for C:

We'll look at each bit independently. The bit for the LHS will be 1 iff all the bits are 1 and 0 otherwise. For the RHS, the bit will be 1 iff the number of bits that are ones is odd, and 0 otherwise. In order to handle both at the same time, you need to split into cases based on the parity of $$$n$$$.

Suppose $$$n$$$ is odd. Then, you can never have the case that the LHS is strictly greater than the RHS, because if the AND is equal to 1, then the number of bits that are 1 is odd, meaning the XOR is 1. Thus, you must have equality.

If both the LHS and RHS is 1, then it must be all ones so that is 1 way. Then if both sides are equal to 0, we must have exactly an even number of ones, or

which is equal to $$$2^{n-1}$$$. Thus, in the odd case, the answer is $$$\left(2^{n-1}+1\right)^k$$$.

Now suppose $$$n$$$ is even. This time, it is possible to have the strict inequality by taking all ones. You then must consider two cases: when we have equality for both sides and when we have the strict inequality.

We tackle the first case. Both bits can not both be equal to one, as that would require all the bits to be one, for an even total, and an odd number of ones, contradiction. Thus we need both to be 0, meaning not all bits are equal to 1, and we must have exactly an even number of ones. This corresponds to

Again, this can be seen to be equal to $$$2^{n-1}-1$$$ through whatever method you want. Thus, there's a total of $$$\left(2^{n-1}-1\right)^k$$$ arrays in this case.

Now suppose we have a strict inequaltiy. What we'll do is fix the bit where we have a 1 on the LHS and 0 on the RHS, and iterate over the positions for that bit: suppose the $$$i$$$'th bit will satisfy this. For the $$$i-1$$$ bits before it, we must have equality, which gives $$$\left(2^{n-1}-1\right)^{i-1}$$$ from the analysis of the previous case. Then, we have exactly 1 way to get the $$$i$$$'th bit, which is to take all ones. Then, the remaining $$$k-i$$$ bits don't matter, so there are $$$\left(2^n\right)^{k-i}$$$ choices here.

Putting both cases together and summing over all $$$i$$$, we have

different arrays in the case that $$$n$$$ is even. Compute this now however you want.

If you wanted a closed form for this, you can see that the summation is actually equal to

where you use the factorization

EDIT: sorry for the typoes oops as you can tell i am terrible at proofreading

could some one tell me why this is wrong https://codeforces.me/contest/1557/submission/125421372

I think it's meaningless to set the space of problem D so tight…… It's hard for $$$O(m\log10^9)$$$ to get pass, since it's easily getting MLE.

But also great problems, thanks for the contest!

I have a different solution for E.

In the beginning the possible positions for KING is the whole chessboard. And if the king do a move , some positions will become impossible. So you can do $$$30$$$ random walk , to make the possible positions become very few(may be greater than one).

And for each possible position , you try to checkmate it .

You can do it for a known position in at most 8 steps :

1. move the queen to that row .
2. move the king.
3. if the position is in your left , move left and move to the row where the king is ,vice versa.

And remember to maintain the possible positions after every move .

It seems that it use only about total $$$40$$$ moves for a test case.

code

I find the interactor for E a little "dumb": in all testcases, I made no more than 20 moves to kill the king lol (if the output of the testcase is the number of moves)

Thanks a lot for a detailed editorial.

problem E was super cute and I recommend everyone to just take a look at it :)

Well, D is a good problem. I solved many problems that can directly construct schemes through dp arrays before. But problem D ISN'T such problem, so I got Wrong answer on pretest 4. This is a good reminder to me that the record transfer is used to construct the scheme, rather than backward pushing according to the dp array.

But I'm still disappointed that I didn't passed D in the round. I am so close to the correct solution!

thank you for the nice editorial

What would be the rating of Div2C question?

AhmedEzzatG Thank you, Sir, The problems were really Good, We can learn a lot from them.

i did this in D problem: if the first and second row have something in common(which I am precomputing) then we can just move on to next row and set previous column as current index and if they don't have anything common, then we have to find the minimum of the two cases: removing the first row and removing the second row. So I call for two functions, with previous values as current index for one and the previous index for the other.

Recursive Code:

int fn(int prev, int cind, set<pair<int, int>> adj[])
{
    if(cind >= n)return 0;
    if(dp[cind] != -1)return dp[cind];
    if(isMerging(cind,prev))
        return dp[cind] = fn(cind, cind + 1, adj);
    return dp[cind] = min(fn(cind, cind + 1, adj),fn(prev, cind + 1, adj)) + 1;
}

But I am doing isMerging step in O(n), can we do it in less than that? Also, I was not able to print the rows deleted.

on what concept problem c is based upon.?

hello everyone In Problem B is showing runtime error in testcase 2 but the code seems to be fine have a look guys. https://codeforces.me/contest/1557/submission/125441413 kindly help if you can. Thanks

Problem C Video Editorial

I solved it in contest and I show my thought process so it might help some of you

Can someone explain my WA? All my tests is AC, but here WA on pretest 2. https://codeforces.me/contest/1557/submission/125395144

How my approach is wrong for the submission of 1557B — Moamen and k-subarrays problem ? Please help 125447732

Hey, In problem A we proved that taking the maximum number in one subsequence is better than taking the two greatest numbers (instead of only one) in one subsequence.My question is how we can generalize this argument for the whole problem as there might be the other cases except for taking the two greatest number.AhmedEzzatG

Problem C，forgot to add enough mod,and failed twice.100 points T T

In problem D,why adding $$$ dp[i][j] = max_{k\in C_i} {dp[i - 1][k]} $$$ step as call modify(1,1,N - 1,mx) is useless and wrong? In my opinion,tutorial's definition points out that $$$ grid[i][j] = 1 $$$ so the transfrom $$$ dp[i][j] = max_{k\in C_i} {dp[i - 1][k]} $$$ is not exist.And that's why add modify(1,1,N - 1,mx) will casue wrong?:/

In Problem E, this is a false promise:

If at any point you make an invalid query or try to make more than 130 queries for each test case, the game will terminate immediately and you will receive a Wrong Answer verdict.

after 30+ submissions of getting RTE and TLE I realized that my code making a move of the type : $$$(6, 1)$$$ -> $$$(6, 1)$$$. I should have got WA verdict but didn't.

I can't understand "You can make i-th bit = 1 in an even number of indices, then Andi will be 0 and Xori will be 0 too." only one position is 1, then the xor could 1 why is 0?

For Problem C, I think the editorial is wrong because $$$dp[i][0]$$$ is just a product of $$$2^n$$$ which corresponds to all possible cases.

Let's define two vectors of size $$$k$$$ :

• allcases[i] : number of ways to buid an array of size n from bit $$$0$$$ to bit $$$i$$$ (included)
• dp[i] : number of ways to buid an array of size n from bit 0 to bit i s.t. (a[1]&...&a[n])[i...0]>=(a[1]&...&a[n])[i...0]
• with (x)[i...0] = $$$2^i x[i] + ... + 2^0 x[0]$$$

Then for allcases:

• allcases[0] = $$$2^n$$$
• allcases[i] = $$$2^n$$$ allcases[i-1]

And for dp:

• n is odd. two cases for bit i:
  • all 1 : AND=1, XOR=1
  • even number of 1 : AND = 0, XOR = 0. number of cases : C(n,0) + C(n,2) + ... + C(n,n-1)
  • dp[i] = (1 + number of cases) * dp[i-1]
• n is even. two cases for bit i:
  • all 1 : AND=1, XOR=0 then for the bit 0...i-1 we can use all possible cases i.e. allcases[i-1]
  • even number of 1 (except n) : AND = 0, XOR = 0. number of cases : C(n,0) + C(n,2) + ... + C(n,n-2)
  • dp[i] = allcases[i-1] + (number of cases) * dp[i-1]

I got WA on test 43 125484134 , test 43 seems random...., can somebody tell me why

I dont know what someone expected for when trying to copy code to on top of the leaderboard of virtual participation. Lmao

I hope that each example of the problems can be more valuable.

In the solution of D it said:

$$$dp_{i,j}$$$ — maximum number of rows (from row $$$1$$$ to row $$$i$$$) that make a beautiful grid, and has $$$1$$$ in column $$$j$$$ at the last row.

What does it mean here "last row"? Is it the row number $$$i$$$ or it is the last row of the biggest beautiful grid?

If it is the row number $$$i$$$ then the following doesn't make sense. It should be just 0.

Otherwise, $$$dp_{i,j} = max_{k\in C_i}{dp_{i-1, k}}$$$.

Otherwise $$$dp_{i, j}$$$ should somehow depend on $$$j$$$, but the right hand side doesn't contain $$$j$$$ in any way

Why is this blog getting so many negative votes, Codeforces community doesn't appreciate the authors' effort!

In the tutorial of problem D, the following statement is not correct:

Otherwise, $$$dp_{i,j}=\max{..}$$$

Should be: If $$$grid_{i,j}\not=1$$$, $$$dp_{i,j}=dp_{i-1,j}$$$.

Is the solution for problem A wrong? I think we can not sum things up like that

The first edi that has -100 downvotes :/

Can somebody please help me figure out, why my code, which quite literally implements the solution described in the editorial (except that I am scanning from left to right instead of top to bottom), not work? It gives runtime error because my queen somehow enters the 8th column, whereas it should be able to checkmate while it is in the 7th column. Any help in figuring out the error (either in the solution or the implementation) would be appreciated.

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debugger.h"
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", debug(__VA_ARGS__)
#else
#define dbg(...) 5
#endif
int main()
{
    int test;
    cin>>test;
    while(test--){
        int curfile=1,currank=8; // curfile=current column, currank=current row
        cout<<currank<<" "<<curfile<<endl;
        int cur=1; // keeps count of number of moves made in the current column
        bool firstmove=true;
        while(true){
            string king;
            cin>>king;
            if(king=="Done"){
                break;
            }
            else if(king=="Right" || king=="Up-Right" || king=="Down-Right"){
                if(firstmove){
                    currank--;
                }
                else{
                    curfile++;
                    cur=1;
                }
            }
            else if(king=="Left" || king=="Up-Left" || king=="Down-Left"){
                cur=1;
                currank--;
                if(currank==0){
                    currank=8;
                }
            }
            else{
                cur++;
                if(cur==9){
                    curfile++;
                    cur=1;
                }
                else{
                    currank--;
                    if(currank==0){
                        currank=8;
                    }
                }
            }
            firstmove=false;
            assert(curfile<8);
            cout<<currank<<" "<<curfile<<endl;
        }
    }
    return 0;
}

Why so much hate around this contest? It wasn't bad at all, C and D were interesting enough and the other tasks were good, maybe only E wasn't finally prepared but it's not the point to hate the whole thing :\ what a heck

AhmedEzzatG I don't understand the following part: If equal is false at any moment, then you can choose any subset of indices to contain 1 in the i-th bit.

You could select the odd number of indices to contain the i-th bit and then And would become less than Xor.

I have a solution to problem E that only needs 16 moves in worst case, verified by DFS.

https://codeforces.me/contest/1557/submission/125862124

I believe it can be made better, but that means slower runtime and will be hard to verify.

A simple random solution for E: 126166286. Just do random moves and try to keep a list of valid starting positions for the king each time. When just one starting cell remained, simply trap the king.

Why this entry has so many downvotes?

About B,I use map<int,int> nxt,directly link the next value,but I failed Test3 in 58th case,I don't know why,anybody can find the mistakes in may code?It will help me a lot,thanks so much!

My code here...
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

void solve(){
	int n,k;
	cin >> n >> k;
	VI a(n),b(n);
	rep(i,0,n){
		cin >> a[i];
		b[i] = a[i]; 
	}
	sort(all(b));
	map<int,int> nxt;
	rep(i,0,n-1)nxt[b[i]] = b[i+1];
	int i = 0,piece = 0;
	while(i < n){
		while(i + 1 < n && a[i+1] == nxt[a[i]]){
			i++;
		}
		piece++;
		i++;
	}
	if(piece > k){
		cout<<"NO"<<endl;
	}else{
		cout<<"YES"<<endl;
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	caset{
		solve();
	}
  	return 0;
}



 

I used a different approach in C, then given in editorial. If n is odd, then for each i from 1 to k, either the ith bit should be on for all the n numbers or the number of on bits should be even so that the XOR does not become one. If n is even, we will follow similar approach but there are some extra cases. For each i from 1 to k, we will count the number of cases where number of on bits for each i should be even(but less than n). Then for each i from 1 to k, consider that the ith bit in all n numbers is on and there is no j from i+1 to k such that the jth bit is on in all n numbers. All the bits less than i can be on or off in all n numbers. All this counting can be done using simple combinatorics. You can look at my solution here https://codeforces.me/contest/1557/submission/144063292 Sorry for the text wall.

Hi guys, i can't understand what wrong with my solution for C. Please help me. My solution:here.I found my mistake.

Is there a way to solve D without coordinate compression ?