Codeforces Round #493 — Editorial

6 years ago, # ^ |

← Rev. 3 →

let ans=0, step1: 11100100011001 ans+=3, step2: 11110000011001 ans+=3, step3: 11110000000111 ans+=3, step4: 11111111111111 ans+=11,

ans=20

→ Reply

Pannu

6 years ago, # ^ |

-8

Gotcha. Thanks!

→ Reply

sfialok98

6 years ago, # |

← Rev. 2 →

For Div 2 D, I have a few doubts from the editorial :-

what will be the dominating pairs..? I do not understand this..
For {0,4,9,49}, It is mentioned to check all (x,y) <=(50,50), for frequencies of 4 and 9 respectively, but why do we need to check pairs (x,y) with x>8. why can't such pairs be again converted to (X,Y) with detachment of 9..!! ex- These pairs will have same value444444444(9)(49)000.. = 99999(49)00..keeping count of numerals same..

→ Reply

6 years ago, # ^ |

Pair (a, b) is dominated by (c, d) if a <= b and c <= d.

→ Reply

6 years ago, # ^ |

Regarding (2), yes we can check less.

→ Reply

6 years ago, # |

Can someone help me with div2 D? I am stuck on how to figure out such problems, it is not possible to know on pen and paper that n starts increasing by 49 after n=12. I went through the editorial, but could not figure out anything. Can someone help me?

→ Reply

Rafaelcs

6 years ago, # ^ |

← Rev. 2 →

Write a Brute force algorithm and then you can see the pattern

→ Reply

6 years ago, # ^ |

Can you please help me in writing the brute force algorithm?

→ Reply

Rafaelcs

6 years ago, # ^ |

← Rev. 4 →

my code

#include <bits/stdc++.h>
using namespace std;
 
set<int>st;
int n;
int v[] = {1, 5, 10, 50};
 
void gen(int digit, int sum){
	if(digit == n){
		st.insert(sum);
		return;
	}
 
	for(int i = 0 ; i < 4 ; i++){
		gen(digit + 1, sum + v[i]);
	}
}
 
int main() {
	cin >> n;
 
	gen(0, 0);
 
	cout << st.size() << endl;
 
	return 0;
}

→ Reply

Rafaelcs

6 years ago, # ^ |

-8

this works fast for n < 14.

→ Reply

indian_luftwaffe

6 years ago, # ^ |

← Rev. 2 →

#include <bits/stdc++.h>
using namespace std;

/* CODE */
int main(int argc, char const *argv[]){
	//IO();
	FAST_IO();
	int n;
	cin >> n;
	int mem[15];
	set<int> s;
	s.insert(0);
	for(int i=0;i<15;i++){
		set<int >tmp;
		for(auto it :s){
			tmp.insert(it+1);
			tmp.insert(it+5);
			tmp.insert(it+10);
			tmp.insert(it+50);
		}
		s=tmp;
		mem[i]=s.size();
	}
	// for(int i=0;i<15;i++){
	// 	cout << i << " " << mem[i] << endl;
	// }
	if(n<=15){
		cout << mem[n-1] << endl;
	}
	else{
		n=n-15;
		cout << (lli)mem[14] + (lli)n*(49LL) << endl;
	}
return 0;	
}

→ Reply

Traves

6 years ago, # |

How is 998B solvable by greedy? It is a classic zero one knapsack after the cuts are calculated. Whether to include the cut or not, each cut having a certain cost ("weight") with an overall cost limit ("capacity") ?

→ Reply

6 years ago, # ^ |

-13

The case you are talking about is when we have x odd and even numbers in every segment.

→ Reply

Mistra

6 years ago, # ^ |

-8

Since all cuts are independent and you want to maximize the number of cuts, it's always optimal to make the cheapest cuts first. Each cut increases the result by 1, so making a higher-weight cut is never better than a lower-weight one.

→ Reply

nimom

6 years ago, # |

← Rev. 3 →

In DIV-2D/1B why do we solve for {0, 4, 9, 49} ? This part isn't clear to me. And also what does x and y represent?

EDIT: I figured out why we can solve for {0, 4, 9, 49}. I wrote a brute force solution that checks the answer for different arrays. {-1, 3, 8, 48}, {1, 5, 10, 50}, {0, 4, 9, 49}, {2, 6, 11, 51}, {3, 7, 12, 52} all these arrays produce the same number of distinct sums. But why do they all give the same answer?

→ Reply

kuprelis

6 years ago, # ^ |

+14

Because if you add some number x to all n summands, all you do is shift the possible values by x*n.

→ Reply

6 years ago, # |

+12

Can someone explain problem Div 2 D in a better way ?

→ Reply

6 years ago, # ^ |

Maybe I can help you if you formulate an exact question.

→ Reply

6 years ago, # ^ |

I first thought of the problem as to distribute n into 4 (I, V, X, L) such that they get one amount only once (to avoid same number), but as n was large i dropped the idea to go for combinatorics. Then i thought the minimum number that can be generated is n and the maximum is 50*n. Can't we generate all the numbers in between ? I didn't get the intuition behind the editorias approach.

→ Reply

6 years ago, # ^ |

Well, we can't generate them all, but we can generate most of them.

To be precise, we do the following: some numbers have multiple representations, and that is not only about order of digits.

To get rid of it, we introduce some ordering on the representations (by representation I mean (number_of_1, number_of_5, number_of_10, number_of_50).

It turns out, that good ordering is somewhat lexicographic: we want the number_of_50 to be larger, if tie, the number_of_10, and so on.

And then, if we count each number only in it's maximum representation, we win.

So we somewhat need to examine all possible maximum representations, and count how much number have this representation.

Since there are quite a lot of maximum representations, we examine only (number_of_5, number_of_10) part of them -- it turns out that rest can be covered by formula.

→ Reply

6 years ago, # ^ |

Can you share your code with this logic ?

→ Reply

https://pastebin.com/fiZj971x

6 years ago, # ^ |

→ Reply

MoonBall

6 years ago, # ^ |

My submission maybe help you. https://codeforces.net/contest/998/submission/39881689

→ Reply

6 years ago, # ^ |

I am not getting the purpose of loops you are running ? Can you help me understand ?

→ Reply

AlexArdelean

6 years ago, # |

For the editorial of B div. 1 and D div. 2 when you explained about that other solution in the brackets you said that "you can easy proof a lowerbound like 50 or 100, but it is, in fact, 12", but in fact it is grammatically incorrect. Here easy is an adverb so you should write easily.

→ Reply

6 years ago, # ^ |

Grammar Nazi Spotted !!

→ Reply

AlexArdelean

6 years ago, # ^ |

I also don't understand D. Please forgive our stupidity and write an editorial understandable for all of us !

→ Reply

Siriuslight

6 years ago, # ^ |

← Rev. 2 →

It is really difficult to understand. I hope someone explains it in a simple way.

→ Reply

AlexArdelean

6 years ago, # ^ |

saying more simpler is incorrect. just "simpler" is the right way

→ Reply

kuprelis

6 years ago, # |

← Rev. 2 →

Can someone explain the purpose of this factor in the first formula for 997C: (-1)^(i + j + 1)

EDIT: nevermind, it's part of the inclusion-exclusion formula, hadn't heard of it before.

→ Reply

kowalsk1

6 years ago, # |

On problem B Div.2, the limits made possible a three-state knapsack-like DP solution (which was what i did). Was that intentional? Because the greedy solution would easily pass for a larger constraint.

→ Reply

6 years ago, # ^ |

Yes, we decided that it is good to allow dp to pass as well.

→ Reply

lessmeaning

6 years ago, # |

← Rev. 3 →

+20

In div1 D there is naive dp on tree. Lets dp_v, j will be number of cycles that starts in vertice v and ends in vertice v and uses only vertices from subtree (we consider tree roodet in this part). Now how to count for v if you know all dps for children lets sum all the dps of chilren in one vector called for example a in details $\text{[math]}$ minus 2 because we need to go to u by edge and go from u to v. To receive dp_v vector from a we need make following k times: next_i = a_j * a_i - j than a = nx (you know simple convolution without FFT) And dp_v, i will be sum of a_i on every iteration of convolution. After bottom-up do similar second dfs top-down. And thats all. But this solution have time complexity $\text{[math]}$ with a lot of MODULO operations it will never pass 7 seconds (I think). And crucial part of solution is to notice that dp_v, i = 0 when i is odd(because it is a tree and to make a cycle you need to pass edge even times). Thus complexity is O(nk³ / 8) = 2 * 10⁸ which got AC. See submission for details

→ Reply

Swistakk

6 years ago, # |

+104

Design an algorithm in $\text{[math]}$ complexity
Recall Swistakk's comment to make laugh about how bad such complexity is
Design an algorithm in $\text{[math]}$ complexity
?????????????
PROFIT!!!

→ Reply

xuanquang1999

6 years ago, # ^ |

+13

Do you think that $\text{[math]}$ is a good complexity?

→ Reply

kostka

6 years ago, # ^ |

+29

Can we have Swistakk's seal of approval for complexities? :P

→ Reply

majk

6 years ago, # ^ |

+26

I don't know what you're complaining about. Cutting that $\text{[math]}$ is a factor 4 speedup. It's not as good as the famous bitset optimisation, but it still counts!

→ Reply

300iq

6 years ago, # ^ |

+26

Cutting n² from $\text{[math]}$ is $\text{[math]}$ optimisation so it counts too!

→ Reply

-_-_-

6 years ago, # |

Div2 E is really beautiful!

→ Reply

6 years ago, # |

← Rev. 4 →

+122

I think my approaches of Div1 CDE are all different from the editorial...

Div1 C: You can try to count 'unlucky' grids by ensuring that all rows and columns contain more than one color.

If we only need to ensure all columns contain more than one color, that is fairly easy: (3ⁿ - 3)ⁿ

Let's try inclusion-exclusion principle on rows, by enumerating the number of rows i with only one color. If these rows themselves are of same color, the ways are: 3C_nⁱ(3^n - i - 1)ⁿ, because every column should not be filled with that one same color. Else the ways are: C_nⁱ(3ⁱ - 3)(3^n - i)ⁿ.

So we can get a formula for the answer straightforward: $\text{[math]}$

Div1 D: be similar with https://codeforces.net/blog/entry/60357?#comment-441843

Div1 E: (upd: simplified the solution a little bit.)

Notice that a subsegment is good iff max - min - len = - 1, and for any subsegment max - min - len ≥ - 1, so what we need is somewhat minimum.

Let's try to find all good subsegment by enumerating the right end, and use a data structure to maintain the possible left ends. If we just store max - min - len in every left ends, possible subsegments can be found by calculating global minimum and its count. When the right ends move right, max - min - len can be maintained by several range adding (maintain two monotonous stacks, etc.).

For a query [l, r], we need to add up all good subsegments with right end ≤ r, and left end ≥ l. We can maintain a 'count' in every node, and when the right ends move right, we should add 1 to the 'count' of nodes with minimum value. This can be done by simply maintain two tags (one for 'max-min-len' adding, one for 'count' adding) on the segment tree. For details you may refer to 39860384.

→ Reply

vivace_jr

6 years ago, # ^ |

← Rev. 3 →

If we only need to ensure all columns contain more than one color, that is fairly easy: (3^n - 3)^n Can anyone/@TLE explain?

Edit : got it

→ Reply

choutii

6 years ago, # ^ |

A solution for div1D with complexity O(n^2k) also passed :D

→ Reply

manasjoshi241

6 years ago, # ^ |

← Rev. 2 →

Can you explain the last two terms of "ans" for Div1 C in more detail ?

→ Reply

6 years ago, # ^ |

Well I think I've explained thoughly above, they just come from above arguments and the inclusion-exclusion principle. Is there any point unclear?

→ Reply

sheaf

6 years ago, # ^ |

← Rev. 7 →

+11

Let me try to explain the formulae.

I'll assume you didn't get where $\text{[math]}$ and $\text{[math]}$ came from.

As for the first one: you want to colour exactly i rows in a certain colour. How to do it? Just choose i rows, which is $\text{[math]}$ and there are three colours that you can choose, so $\text{[math]}$ . Now you want to choose colours for the rest of the squares, there are (n - i)n left. Normally you'd count the ways like 3^n(n - i) but there can be such painting that there are columns with the same colour, so you have to cross out all such column paintings that have the colour you have fixed on the previous step. To count 'good' column paintings you should apply inclusion-exclusion principle, namely $\text{[math]}$ which is equal to (3^n - i - 1)ⁿ. You should know this formula, or at least be able to prove it. The multiple 3^{(n - k)(n - i)} says that you fix colours of exactly k columns and arbitrary paint (n - k)(n - i) remaining squares.

The second one. You pick i rows again (which is $\text{[math]}$ ) and say that each of them can have any of three colours, there are 3ⁱ ways to choose three colours for i rows. Don't forget, that we dealt with same-colour rows in the previous step, so we should subtract 3 ways to paint these i rows. Now you know where $\text{[math]}$ come from. You choose colours for the remaining n(n - i) squares. You know, that there can't be same-colour columns as at least one of chosen i rows have different colour, thus this is a simple case of 3^n(n - i) ways to choose colours for them.

In the resulting formula, while summing these terms we just need not to forget to multiply ( - 1)ⁱ because of inclusion-exclusion principle.

→ Reply

6 years ago, # ^ |

Thanks for the explanation. Btw, (3^n - i - 1)ⁿ can just be devired from that we can paint the remaining of every column arbitary, under that you should not paint some column with that one same color.

→ Reply

manasjoshi241

6 years ago, # ^ |

Great Explanation. Thanks

→ Reply

mango_lassi

6 years ago, # ^ |

What is "sqrt-blocking"?

→ Reply

traxex

6 years ago, # ^ |

sqrt-decomposition, i.e. divide the array into sqrt-sized blocks.

→ Reply

simp1eton

6 years ago, # ^ |

Hi, can you explain what does "history minimum" mean?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Alright. So what we want to do is that when we move right the right end, record the current value to all left ends, for every left end maintain all records' minimum and count. For the sake of simplicity I just called it 'history minimum'.

I've simplified the solution now, hope it helps.

→ Reply

HIT_TOM

6 years ago, # ^ |

In div1 C, could you please tell me how to calculate all values of pow( pow(3, n — i) — 1, n) for i from 1 to n in O(n) time? I can only understand a O(nlogn) method.

→ Reply

6 years ago, # ^ |

I only know O(nlogn) method too...

→ Reply

scoobydoo

6 years ago, # ^ |

Thanks for explanation and I have used your approach in Div1C but I am getting TLE 39894941 my Java code

→ Reply