Downvoted, thanks for explaining the "simple cases analysis" for Div1D

During the round,I noticed that in div2 B it is written that "In one operation you can select some i (1 ≤ i ≤ n) and replace element ai with ai & x,",which it's said "some",meaning I can choose an many i(s) as I like.So I think the max ans should be 1 instead of 2(Maybe it's just a translation mistake).

However, I got tons of Wrong Answer because of this. So,is it a mistake....or because I am too weak in English?

SORRY FOR MY POOR ENGLISH

my div1 D solution

40970859

I coded so many lines...

some of the submissions in editorial can not be visited

In Div2E/Div1C, here is a simplier solution:

Let dp[i][j][k] means the min cost that we are at pos i, we have built j houses in [1,i]and k means if we are going to build a house at pos i ( k = 0 or 1 )

when transforming , it's clear that:

when k = 0, we can use dp[i][j][0] to update dp[i+1][j+1][1] and dp[i+1][j][0],means if we are going to build a house at pos (i+1)

when k = 1, we can use dp[i][j][1] to update dp[i+2][j+1][1] and dp[i+2][j][0],means if we are going wo build a house at pos (i+2) ( we cannot build at pos(i+1) now since pos i has already had a lovely house)

You can see the DP equation in my Code: 40965480

#define Mymax(a,b) if(a<b) a = b;
int P( int pos , int goal ){
	if( a[pos] <= goal ) return 0;
	return a[pos] - goal;
}
dp[1][0][0] = 0;
	dp[1][1][1] = 0;
	int div2 = (n>>1) + (n&1);
	For(i,n){
		Forx(j,0,div2){
			For0(k,2){
				#define N dp[i][j][k]
				if( dp[i][j][k] == -INF ) continue;
				if(!k){
					Mymin(dp[i+1][j+1][1],N+P(i,a[i+1]-1));
					Mymin(dp[i+1][j][0],N);
				}else{
					Mymin(dp[i+2][j+1][1],N+P(i+1,min(a[i],a[i+2])-1));
					Mymin(dp[i+1][j][0],N+P(i+1,a[i]-1));
				}
			}
		}
	}

Complexity: O(n²)

I used the algorithm during the contest and acceptted,and I think it's much clearer than the Editorial

SORRY FOR MY POOR ENGLISH

Editorial for Div. 2 B:

"Clearly, if it is possible then there are no more than 2 operations needed."

Can someone explain that? Thanks in advance.

In tutorial of Div1F, I guess it should be d ≥ dp[A] instead of d ≤ dp[A]. Also O(2ⁿⁿ²) seems to be sth like O(2ⁿ n²) (wow it seems to be a bug of codeforces).

can someone explain more clearly for div2D ?

Hey I noticed something strange on div2D/div1B:

When you submit the O(nlogn), its actually faster than O(n) dsu.

Strange right?

My O(nlogn) — 40990303 — 124 ms (path compression)

My O(n) — 40990296 — 155ms (path comp + ranking)

I thought, it must just be me. But I was curious, so I also edited vamaddur's solution to see if similar would happen.

The same pattern happened, even with different implementations (he had some debugging stuff, etc):

O(n) — 40963207 — 483 ms (path comp + ranking)

My edit on his O(n) to O(nlogn) — 40990415 — 311ms (removed ranking, only path comp)

Now of course I understand complexity is not everything, there is constant factor. But I don't understand how even bad constant factor of one O(n) solution can overcome logn factor of slower dsu.

I think this is strange, maybe it has something to do with the data? Why does the nlogn run faster than the linear solution?

Can someone explain more clearly div2B ?I don't understand why at most 2 operations will suffice for an equal pair??

Which problems appeared in EJOI?

HELP with Problem B. I don't understand the editorial at all.

My solution for div1D, finally:

• let's append undeletable 'a' and 'b' at the end of the original strings (trying both ways to do it) and group together consecutive identical letters
• if both compressed strings have equal lengths, it has an easy greedy solution
• the optimal solution will reach this situation in at most 2 steps
• there are only a few types of operations we want to do in these two steps, it seems "move the first group from one string to the other" and "swap approx. half of one string with approx. half of the other string" are the only ones needed (6 types in total)
• bruteforce these at most two steps, do greedy if possible afterwards, pick the best solution obtained this way

It has a large constant, but at least it should be provable more easily. It's still kind of a PITA to code.

Wow, Div1B has an amazing solution in my opinion. What a great problem! It is so easy to code, yet so hard to solve.

Another solution to Div1C (Div2E) is to extend the solution that you found for k and use it to find the solution for k+1.

Let's define used[i] = 1 if the i'th hill contains a flat, otherwise used[i] = 0.

To extend the solution from k to k+1, we need to build one extra flat, so we can make one of the following transformations to one of the contiguous subsequences:
1- Transform 0 0 0 → 0 1 0. That is, build a new house if it's neighbors are not occupied.

2- Transform 0 01010 0 → 0 10101 0. By this, we get an extra 1. Of course the length of this sequence is arbitrary.

Then you simply have to loop over the possible transformations and choose the transformation that minimizes the total cost.

However, keeping track of the total cost and the cost of transformations turned out to be a little bit tedious and that the DP solution is definitely much simpler to code. Anyway, here is my submission if someone is interested: 41124194.

I wrote a slow but correct dynamic programming for Div1D.And I found if the length of any string is large, decision making seems regular. You can found these regular patterns here.(in function g(x, y, d), where x represents the length of the first string, y represents the length of the second string, and d represents whether the first characters are different). Could anyone prove it or hack it?

Please help. What is complexity for this?

https://mirror.codeforces.com/contest/1012/submission/91080831

I thought it was n^3 but it got AC.