### atcoder_official's blog

By atcoder_official, history, 3 months ago,

We will hold Sky Inc, Programming Contest 2023 (AtCoder Beginner Contest 329).

We are looking forward to your participation!

• +57

 » 3 months ago, # |   +13 I <3 AtCoder. When I visit Nihon, I want to visit AtCoder office.
 » 3 months ago, # |   0 Completely clueless on E :( Saw 3 WAs of Forested, got demoralized further.
•  » » 3 months ago, # ^ |   +3 M is bounded by 5,it's a simple bfs solution.
•  » » » 3 months ago, # ^ |   0 Can you share your code
•  » » » » 3 months ago, # ^ |   +3 Sure,here is the link — Code
 » 3 months ago, # | ← Rev. 2 →   0 today's D realize me, how poor I am in building logic :(
•  » » 3 months ago, # ^ |   -27 If you know segment tree you can do it easily. Codevector > st; void build(int node, int s, int e){ if(s == e){ st[node] = {s, 0}; } else{ int mid = (s + e) / 2; build(2 * node, s, mid); build(2 * node + 1, mid + 1, e); st[node] = st[2 * node]; } } void update(int node, int s, int e, int idx){ if(s == e){ st[node].second++; } else{ int mid=(s + e) / 2; if(s <= idx && idx <= mid) { update(2 * node, s, mid, idx); } else { update(2 * node + 1, mid + 1, e, idx); } if(st[2 * node + 1].second > st[2 * node].second) st[node] = st[2 * node + 1]; else st[node] = st[2 * node]; } } int get(){ return st[1].first; } void solve(){ int n, m; cin >> n >> m; int a[m + 1]; for(int i = 1; i <= m; i++){ cin >> a[i]; } st.resize(4 * n + 2); build(1, 1, n); for(int i = 1; i <= m; i++){ update(1, 1, n, a[i]); cout << get() << endl; } } 
•  » » » 3 months ago, # ^ |   0 it's just a if logic block bro! segment tree is OVERKILL!!
•  » » » » 3 months ago, # ^ |   0 Right, its an overkill. Just saw this beautiful solution:
•  » » » » » 3 months ago, # ^ |   0 Thank for the compliment, cuz my solution is exactly the same, lol
•  » » » » » » 3 months ago, # ^ |   -10 Yeah, exactly once u realize that u don't have to pop and update, simply just keep pushing into max heap, it's piece of cake. My Codevoid testcase() { int n, m; cin >> n >> m; map mp; priority_queue, vector>, myComp> maxHeap; for (int i = 0; i < m; i++) { int x; cin >> x; mp[x]++; maxHeap.push(make_pair(mp[x], x)); cout << maxHeap.top().second << "\n"; } } 
•  » » » » » » » 3 months ago, # ^ |   0 lol, we actually dont need to pop out xD
•  » » » » » » 3 months ago, # ^ |   -10 same here,
•  » » » 3 months ago, # ^ |   0 Me with my vector and unordered_map solution be like: AMATEURS.. Link: https://atcoder.jp/contests/abc329/submissions/47726639
•  » » 3 months ago, # ^ |   0 you could have just solved it using heaps tho
•  » » » 3 months ago, # ^ |   +1 Array is enough. One additional variable to keep track of smallest id, You can just keep track of largest one yet on-line. Like the maximum subarray problem, but not exactly.
 » 3 months ago, # |   0 Can we solve F using bitsets?
•  » » 3 months ago, # ^ |   +11 you can merge small sets to large sets to reduce time complexity,here is the code
•  » » 3 months ago, # ^ |   0
 » 3 months ago, # |   0 Harder version of problem E (with outputting the operations)Here from Coding Ninjas.
•  » » 3 months ago, # ^ |   0 Any Hint for F
•  » » » 3 months ago, # ^ |   0 small to large merging technique submission
•  » » » » 3 months ago, # ^ |   0 I got tle for 6 test cases but passed all 38 cases. I Didn't check small and large set. Is this the reason for the tle?
•  » » » » » 3 months ago, # ^ |   0 Yes.That will cost $O((n - 1) * (n - 2) / 2)$assume all the boxes contain exactly $1$ ball of distinct color than all others.Suppose adding left set into the right set in merging. Now if you start merging like below. ${ \newline \text{1 + 1 (costs 1 iterations)} \newline \text{2 + 1 (costs 2 iterations)} \newline \text{3 + 1 (costs 3 iterations)} \newline \text{....} \ \newline \text{n - 1 + 1 (costs n - 1 iterations)} \ \newline \text{total iterations} = (n - 1) * (n - 2) / 2 }$
•  » » » » » » 3 months ago, # ^ |   0 Thanks. Can u explain problem E also. I have no clue how to solve it!
•  » » » » » » » 3 months ago, # ^ |   0 I couldn't solve problem E during the contest but upsolved it by seeing a beautiful submission by callmepandey.So we can solve this problem with dp (ofc), as we can see size of stamp is so small so for each index we can match the character to the character of the stamp.For string $S$ the first character should be matched to the first character of the string $T$ same for the last character. Now we will check for each index in $S$ in the range $(2, N - 1)$ so will try match the current character with the character in $T$, based on the previous matched indices. There are few case works.
•  » » » » » » » » 3 months ago, # ^ |   0 Why we need to check for both original and reverse string?
•  » » » » » » » » » 3 months ago, # ^ |   0 No we need not to check twice! (maybe he tried to be safe).I did without that. Submission
•  » » » » » » » » » 3 months ago, # ^ |   0 okay
•  » » » » 3 months ago, # ^ |   0 okay
•  » » 3 months ago, # ^ |   0 what is the complexity of swapping two sets??
•  » » » 3 months ago, # ^ |   0 Its constant time ie O(1)
•  » » » » 3 months ago, # ^ |   0 really!! how can swap do that?
•  » » » » » 3 months ago, # ^ |   +13 It exchanges the reference pointers for the respective variables!
 » 3 months ago, # | ← Rev. 2 →   +3 E is just a modified DP version of this problem (but it took me too long to recognize that)Not a bad problem though
•  » » 3 months ago, # ^ |   0 Can you share your submission?
•  » » 3 months ago, # ^ |   0 please elaborate
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 We want to build a string $S$ and in this case our "dictionary" contains $\frac{m(m + 1)}{2}$ strings (some of the substrings of $T$ might be the same).The only difference between Word Combinations and today's problem is that some prefix of $S$ should be a prefix of $T$ and some suffix of $S$ should be a suffix of $T$ as well (not just any string from the dictionary). After this the problem is reduced to the cses problem, also we don't even need a trie to solve it, brute-forcing all substrings of $T$ at each position works as well due to a small $M$.P.S. I just call every check if some target is reachable with given parts problem a knapsack problem, not actually sure if that is accurate
•  » » » » 3 months ago, # ^ |   0 Can I see your code? How does your solution handle this? Input: 6 3 aaaccc abc Output: No 
•  » » » » » 3 months ago, # ^ | ← Rev. 3 →   0 It's not the prettiest piece of code that I've written, but it works Spolier#include using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; string s; cin >> s; string t; cin >> t; bool dp[n + 1][2]; rep(i, n + 1) { dp[i][0] = false; dp[i][1] = false; } bool ok = false; rep(i, m) { string temp = s.substr(0, i + 1); string t2 = t.substr(0, i + 1); if (temp == t2) { dp[i + 1][0] = true; ok = true; if (i == m - 1) { dp[i + 1][1] = true; } } } if (!ok) { cout << "No"; return 0; } rep(i, n) { if (!dp[i][0]) continue; rep(j, m) { int max_len = m - j; max_len = min(max_len, n - i); rep(l, max_len) { string t2 = t.substr(j, l + 1); string temp = s.substr(i, l + 1); if (t2 != temp) continue; if (dp[i][1]) { dp[i + l + 1][0] = true; if (l == m - j - 1) { dp[i + l + 1][1] = true; } } else { if (j != 0) continue; dp[i + l + 1][0] = true; if (l == m - j - 1) { dp[i + l + 1][1] = true; } } } } } if (dp[n][1]) { cout << "Yes"; } else { cout << "No"; } return 0; } Here state 1 means that some suffix of $T$ has matched fully. If before some suffix hasn't matched fully — I need to start with a fresh prefixNot sure if I actually need the extra 0-1 dp state, maybe just checking that a prefix and a suffix have matched is enough
•  » » » » » » 3 months ago, # ^ |   +1 Ah, okay. Now I see why it works, it seems like your explanation before wasn't complete.I wouldn't suggest calling this knapsack dp since it isn't that — it's just dp. People will get confused and you'll need to explain further. And also, your solution didn't actually reduce to Word Combinations since you need the check with fully matched suffixes, but I admit that the solutions are still quite similar.
•  » » » » » » » 3 months ago, # ^ |   +10 My bad, the explanation was incomplete indeed. The similarity with Word Combinations only occurred to me after the contest has ended and I was frustrated with myself that I didn't see the correlation earlier
 » 3 months ago, # | ← Rev. 3 →   0 1st Code: https://atcoder.jp/contests/abc329/submissions/477404042nd Code: https://atcoder.jp/contests/abc329/submissions/47740408Why is the first code giving WA and Second code AC?The only difference is the order of loop(forward in first and reverse in second).
•  » » 3 months ago, # ^ |   0 Can you explain your idea?
 » 3 months ago, # |   0 Passed ABCDF in 19min, but E was always WA x 1 :(
 » 3 months ago, # |   0 The "swap" in question F is the key if you use map or set, otherwise it will TLE