USACO 2023 US Open Contest Bronze Division - Moo Language#
Problem link: here
Solution Author: Stefan Dascalescu
Problem Solution#
A very difficult bronze task, one of the hardest ever I would say. In order to solve this problem you need to be very careful as far as implementation goes, but also to be careful when it comes to dealing with various cases and other corner cases too.
First let's group the words in four types based on the type of word they are. 0 will be nouns, 1 will be transitive verbs, 2 will be intransitive verbs and 3 will be conjunctions.
I will define the basic sentences as 0+2 respectively 0+1+0, with 0+1+0 potentially being completed by +(c+0), where c is a comma
Now the idea is that all sentences will be basic except for one of 0+1+0 where we have all additions.
We will fix the number of sentences of each type and see how many full sentences we can actually construct with respect to limits as far as conjunctions, periods and words go. The best option will be chosen as the final string to reconstruct. (more details on that in the two for loops where I fix the number of verbs of each type.
As far as reconstructing goes, I prioritize sentences of type 0+2 and then 0+1+0, but one has to be careful as far as periods go. Make sure to add a period after the end of each sentence but also if there is no conjunction to separate distinct sentences (not all "sentences" are made of two parts, some are made of one part).
Source codes#
The source codes in C++ and Python can be seen below.
#include <bits/stdc++.h>
using namespace std;
vector<vector<string> > words;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
for(; t; t--)
{
int n, c, p;
cin >> n >> c >> p;
words.clear();
words.resize(4);
for(int i = 1; i <= n; i++)
{
string word, part;
cin >> word >> part;
if(part == "noun")
words[0].push_back(word);
if(part == "transitive-verb")
words[1].push_back(word);
if(part == "intransitive-verb")
words[2].push_back(word);
if(part == "conjunction")
words[3].push_back(word);
}
int nouns = words[0].size();
int cnt_v1 = words[1].size();
int cnt_v2 = words[2].size();
int conjunctions = words[3].size();
int bst = 0;
int nouns_used = 0;
int v1_used = 0;
int v2_used = 0;
int conj_used = 0;
int xtr = 0;
for(int i = 0; i <= cnt_v1; i++)
for(int j = 0; j <= cnt_v2; j++)
{
if(i + j > 2 * p) // not enough sentences
continue;
if(i + j >= p && (i + j - p) > conjunctions) // not enough conjunctions
continue;
if(i + j == 0)
continue;
int min_nouns = 2 * i + j;
if(min_nouns > nouns)
continue;
int max_conjunctions = min((i+j) / 2, conjunctions);
int extra_nouns = min(c, nouns - min_nouns);
if(i == 0) // no extra nouns when we don't have transitive verbs
extra_nouns = 0;
if(i + j + min_nouns + max_conjunctions + extra_nouns > bst)
{
bst = i + j + min_nouns + max_conjunctions + extra_nouns;
nouns_used = min_nouns + extra_nouns;
v1_used = i;
v2_used = j;
conj_used = max_conjunctions;
xtr = extra_nouns;
}
}
cout << bst << '\n';
int total = 0;
int is_conj = 0;
while(v1_used || v2_used)
{
total++;
if(v2_used) // 0+2
{
cout << words[0].back() << " " << words[2].back();
words[0].pop_back();
words[2].pop_back();
nouns_used--;
if(is_conj == 0 && conj_used && (v1_used + v2_used >= 2)) // conjunction
{
cout << " " << words[3].back() << " ";
conj_used--;
words[3].pop_back();
is_conj = 1;
}
v2_used--;
}
else // 0+1+0 + (maybe) (,+0)
{
cout << words[0].back() << " " << words[1].back();
words[0].pop_back();
words[1].pop_back();
nouns_used--;
cout << " " << words[0].back();
words[0].pop_back();
nouns_used--;
if(v1_used == 1) // extra (, + 0)
{
while(xtr)
{
cout << ", ";
cout << words[0].back();
words[0].pop_back();
xtr--;
nouns_used--;
}
}
if(is_conj == 0 && conj_used && (v1_used + v2_used >= 2)) // conjunction
{
cout << " " << words[3].back() << " ";
conj_used--;
words[3].pop_back();
is_conj = 1;
}
v1_used--;
}
if(is_conj % 2 == 0) // dealing with periods
{
cout << ".";
if(v1_used || v2_used)
cout << " ";
is_conj = 0;
}
else
is_conj = 2;
}
cout << '\n';
}
return 0;
}
t = int(input())
for _ in range(t):
n, c, p = map(int, input().split())
words = [[] for _ in range(4)]
for _ in range(n):
word, part = input().split()
if part == "noun":
words[0].append(word)
if part == "transitive-verb":
words[1].append(word)
if part == "intransitive-verb":
words[2].append(word)
if part == "conjunction":
words[3].append(word)
nouns = len(words[0])
cnt_v1 = len(words[1])
cnt_v2 = len(words[2])
conjunctions = len(words[3])
bst = 0
nouns_used = 0
v1_used = 0
v2_used = 0
conj_used = 0
xtr = 0
for i in range(cnt_v1 + 1):
for j in range(cnt_v2 + 1):
if i + j > 2 * p:
continue
if i + j >= p and (i + j - p) > conjunctions:
continue
if i + j == 0:
continue
min_nouns = 2 * i + j
if min_nouns > nouns:
continue
max_conjunctions = min((i + j) // 2, conjunctions)
extra_nouns = min(c, nouns - min_nouns)
if i == 0:
extra_nouns = 0
tot = i + j + min_nouns + max_conjunctions + extra_nouns
if tot > bst:
bst = tot
nouns_used = min_nouns + extra_nouns
v1_used = i
v2_used = j
conj_used = max_conjunctions
xtr = extra_nouns
print(bst)
is_conj = 0
while v1_used or v2_used:
if v2_used:
print(words[0].pop() + " " + words[2].pop(), end="")
nouns_used -= 1
if is_conj == 0 and conj_used and (v1_used + v2_used >= 2):
print(" " + words[3].pop() + " ", end="")
conj_used -= 1
is_conj = 1
v2_used -= 1
else:
print(words[0].pop() + " " + words[1].pop(), end="")
nouns_used -= 1
print(" " + words[0].pop(), end="")
nouns_used -= 1
if v1_used == 1:
while xtr:
print(", " + words[0].pop(), end="")
xtr -= 1
nouns_used -= 1
if is_conj == 0 and conj_used and (v1_used + v2_used >= 2):
print(" " + words[3].pop() + " ", end="")
conj_used -= 1
is_conj = 1
v1_used -= 1
if is_conj % 2 == 0:
print(".", end="")
if v1_used or v2_used:
print(" ", end="")
is_conj = 0
else:
is_conj = 2
print()