Codeforces Round 568 Div2 E, F, G Note
Problem E
For this problem, the main point lies on the fact that the validity of the graph does not depend on time. So, lets think a graph is obtained from a sequence of valid operations, then the resulting graph should not have the following features:
- letter that appears not only in a row or in a column.
- two letters appear alternatively (since the latter letter always covers the previous one)
The first constraint can be checked fairly easily because we just need to ensure that letters only appear in a form of either a row or a column.
The second constraint is slightly harder to be checked if we simply follow it directly. But, we can transform the fact that no two letters appear alternatively to the fact that if we connect the first and last occurence of letters in the graph, then the resulting graph can be achieved through a sequence of valid operations if it is equaled to the given graph.
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false)
const int maxn = 2005;
typedef pair<int,int> pii;
int t,n,m;
char mp[maxn][maxn];
int ans[maxn][maxn];
int ind(char c){
return c - 'a';
}
int abs(int x){
return x < 0 ? -x : x;
}
int main()
{
FAST_IO;
cin.tie(nullptr);
cout.tie(nullptr);
cin>>t;
while(t--){
vector<pii> v[30];
vector<pair<pii,pii> > output;
cin>>n>>m;
for(int i = 1; i <= n; i++){
string s;
cin>>s;
for(int j = 0; j < (int) s.size(); j++){
ans[i][j + 1] = 0;
mp[i][j + 1] = s[j];
if('a' <= s[j] && s[j] <= 'z'){
int idx = ind(s[j]);
v[idx].push_back(pii(i,j + 1));
}
}
}
for(int i = 0; i < 26; i++) sort(v[i].begin(),v[i].end());
bool wrong = true;
for(int i = 0; i < 26; i++){
if((int) v[i].size() == 0) continue;
int s_x,s_y,e_x,e_y;
s_x = v[i][0].first;
s_y = v[i][0].second;
e_x = v[i][(int)v[i].size() - 1].first;
e_y = v[i][(int)v[i].size() - 1].second;
if(abs(s_x - e_x) >= 1 && abs(s_y - e_y) >= 1){
wrong = false;
break;
}
if(s_x == e_x){
for(int j = s_y; j <= e_y; j++) ans[s_x][j] = i + 1;
}
else{
for(int j = s_x; j <= e_x; j++) ans[j][s_y] = i + 1;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(!((mp[i][j] == '.' && ans[i][j] == 0) || (ans[i][j] - 1 == (int)(ind(mp[i][j]))))){
wrong = false;
}
if(!wrong) break;
}
if(!wrong) break;
}
if(!wrong) {
cout<<"NO"<<endl;
continue;
}
cout<<"YES"<<endl;
bool flag = false;
pair<pii,pii> prev;
for(int i = 25; i >= 0; i--){
if(flag && v[i].empty()){
output.push_back(prev);
continue;
}
else if(!flag && v[i].empty()) continue;
flag = 1;
prev = make_pair(pii(v[i][0].first,v[i][0].second),pii(v[i][(int)v[i].size() - 1].first,v[i][(int)v[i].size() - 1].second));
output.push_back(prev);
}
cout<<(int)output.size()<<endl;
for(int i = (int) output.size() - 1; i >= 0; i--){
cout<<output[i].first.first<<" "<<output[i].first.second<<" "<<output[i].second.first<<" "<<output[i].second.second<<endl;
}
}
return 0;
}
Problem F
An intuitive approach to this problem is to enumerate all potential pairs of two pizzas and count the maximum satisfication number for each pair. Obviously, it is too slow since it would take $\mathcal{O}(n^2 + n^2 m)$. Now, if we observe, we find that it is just too time consuming to build all pairs using enumeration on pizzas. Since all we want to do is to see what ingrediants can be obtained through using 2 pizzas, we can simply enumerate on the ingredient set and see if certain pizza with specific ingredient set exist. There are at most $2^9 = 512$ potential ingredient sets, it only takes $\mathcal{O}(2^9 \cdot2^9 \cdot 2^9)$ to check if a combined ingredient set can be achieved using two pizza. And the counting part is at most $\mathcal{O}(2^9 \cdot n)$.
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <limits>
#include <vector>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false)
const int maxn = 1e5 + 10;
typedef pair<int,int> pii;
int n,m,ans_cnt;
int ing_person[maxn],ing_pizza[maxn];
vector<pii> price, min_cost[600];
int ans_cost,min_comb_cost[600],min_choice[600];
pii ans, comb_pair[600];
int main()
{
FAST_IO;
cin.tie(nullptr);
cout.tie(nullptr);
cin>>n>>m;
price.resize(m);
for(int i = 1; i <= n; i++){
int tot;
cin>>tot;
for(int j = 1; j <= tot; j++){
int pref;
cin>>pref;
ing_person[i] |= (1 << (pref - 1));
}
}
for(int i = 0; i < 600; i++) {
min_comb_cost[i] = INT_MAX;
}
for(int i = 1; i <= m; i++){
int num;
cin>>price[i - 1].first>>num;
price[i - 1].second = i;
for(int j = 1; j <= num; j++){
int pref;
cin>>pref;
ing_pizza[i] |= (1 << (pref - 1));
}
min_cost[ing_pizza[i]].emplace_back(price[i - 1]);
}
for(int i = 0; i < 600; i++){
if(!min_cost[i].empty()){
sort(min_cost[i].begin(),min_cost[i].end());
}
}
for(int i = 0; i < (1 << 9); i++){
for(int j = 0; j < (1 << 9); j++){
for(int k = 0; k < (1 << 9); k++){
if(i == (j | k)){
if(j != k){
if(min_cost[j].empty() || min_cost[k].empty()) continue;
if(min_cost[j][0].first + min_cost[k][0].first < min_comb_cost[i]){
min_comb_cost[i] = min_cost[j][0].first + min_cost[k][0].first;
comb_pair[i] = make_pair(min_cost[j][0].second, min_cost[k][0].second);
}
}
else if((int)min_cost[j].size() >= 2){
if(min_cost[j][0].first + min_cost[j][1].first < min_comb_cost[i]){
min_comb_cost[i] = min_cost[j][0].first + min_cost[j][1].first;
comb_pair[i] = make_pair(min_cost[j][0].second, min_cost[j][1].second);
}
}
}
}
}
}
ans_cost = -1;
for(int i = 0; i < (1 << 9); i++){
if(min_comb_cost[i] != INT_MAX){
int cnt = 0;
for(int j = 1; j <= n; j++){
if((i | ing_person[j]) == i) {
cnt++;
}
}
if(ans_cnt < cnt){
ans_cnt = cnt;
ans = comb_pair[i];
ans_cost = min_comb_cost[i];
}
else if(ans_cnt == cnt && min_comb_cost[i] < ans_cost){
ans = comb_pair[i];
ans_cost = min_comb_cost[i];
}
}
}
if(ans.first){
cout<<ans.first<<" "<<ans.second<<endl;
}
else{
sort(price.begin(), price.end());
cout<<price[0].second<<" "<<price[1].second<<endl;
}
return 0;
}
Problem G
This is the most interesting problem of this contest, and there are a lot to talk about. Lets begin with our inital thought again, since I think clarifying my thought flow is more important than understanding the code. So, my intial thought is to calculate ways, $W$, we can use $i$ genre 1 songs, $j$ genre 2 songs and $k$ genre 3 songs to compose a total length of $T$, then I will calculate ways I can put these songs into order that satisfy the fact that no two songs with same genre will stay together. However, a dp with size $50 \cdot 50 \cdot 50 \cdot 2500$ would be too large. So our thought should shift to the goal of reducing the time and memory need. We can see that $W$ can be calculate using two DPs:
- Ways using $i$ genre 1 songs to compose a time of $t$
- Ways using $j$ genre 2 and $k$ genre 3 songs to compose a time of $t’$
If $t + t’ = T$, we can have the ways the anwser to the first problem without considering any permutations. Then, we can try to solve how many ways we can put these songs into a valid order. We can calculate using a 4 dimensional dp with the number of songs of each genre as three dimensions and the genre of last song as the 4th dimension. The reason we are using the fourth dimension is because we want to make sure that there are no consecutive songs with same genre. Then, we get the answer to the this problem without considering any permutation.
Finally, we can have multiply the ways in the first solution together with the the sum of three solutions of the second problems (since we have 3 ways to end a sequence), and the permutation numbers of songs of each genre.
My problem was I did not correctly decompose the solution. By decomposing, I mean how to calculate the combinatorics. Probably more works need to be done.
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false)
const int maxn = 55;
const int maxt = 2505;
const int mod = 1e9 + 7;
int n,T,a[maxn][maxt],b[maxn][maxn][maxt],way[maxn][maxn][maxn][4];
int dur[3], permu[55];
vector<int> song[3];
void preprocess(){
permu[0] = 1;
for(int i = 1; i <= 50; i++){
long long re = (long long)(permu[i - 1]) * i % mod;
permu[i] = (int)(re);
}
}
void inc(int &a, int b){
a += b;
if(a >= mod) a -= mod;
}
int main()
{
FAST_IO;
cin.tie(nullptr);
cout.tie(nullptr);
preprocess();
cin>>n>>T;
a[0][0] = b[0][0][0] = 1;
for(int i = 1; i <= n; i++){
int minute, gen;
cin>>minute>>gen;
gen--;
if(gen == 0){
for(int j = (int) song[0].size(); j >= 0; j--){
for(int k = 0; k <= dur[0]; k++){
inc(a[j + 1][k + minute], a[j][k]);
}
}
}
else{
for(int j = (int) song[1].size(); j >= 0; j--){
for(int k = (int) song[2].size(); k >= 0; k--){
for(int p = 0; p <= dur[1] + dur[2]; p++){
inc(b[j + (gen == 1)][k + (gen == 2)][p + minute], b[j][k][p]);
}
}
}
}
song[gen].emplace_back(minute);
dur[gen] += minute;
}
way[0][0][0][3] = 1;
vector<int> c(3);
for(c[0] = 0; c[0] <= (int) song[0].size(); c[0]++){
for(c[1] = 0; c[1] <= (int) song[1].size(); c[1]++){
for(c[2] = 0; c[2] <= (int) song[2].size(); c[2]++){
for(int lst = 0; lst < 4; lst++){
if(way[ c[0]][c[1]][c[2]][lst]){
for(int nxt = 0; nxt < 3; nxt++){
if(nxt != lst && c[nxt] + 1 <= (int) song[nxt].size()){
vector<int> tmp(c);
tmp[nxt]++;
inc(way[tmp[0]][tmp[1]][tmp[2]][nxt],way[c[0]][c[1]][c[2]][lst]);
}
}
}
}
}
}
}
int ans = 0;
for(c[0] = 0; c[0] <= (int) song[0].size(); c[0]++){
for(int t = 0; t <= dur[0]; t++){
if(T - t < 0) continue;
for(c[1] = 0; c[1] <= (int) song[1].size(); c[1]++){
for(c[2] = 0; c[2] <= (int) song[2].size(); c[2]++){
long long extra = (long long)(a[c[0]][t]) * b[c[1]][c[2]][T - t] % mod;
for(int i = 0; i < 3; i++){
extra = extra * permu[c[i]] % mod;
}
for(int lst = 0; lst < 3; lst++){
if(c[lst] == 0) continue;
inc(ans, extra * way[c[0]][c[1]][c[2]][lst] % mod);
}
}
}
}
}
cout<<ans<<endl;
return 0;
}