Sky Inc, Programming Contest 2023 (AtCoder Beginner Contest 329) Announcement

7 months ago, # |

Completely clueless on E :(
Saw 3 WAs of Forested, got demoralized further.

→ Reply

no_oneplb

7 months ago, # ^ |

M is bounded by 5,it's a simple bfs solution.

→ Reply

7 months ago, # ^ |

Can you share your code

→ Reply

no_oneplb

7 months ago, # ^ |

Sure,here is the link — Code

→ Reply

213976

7 months ago, # |

← Rev. 2 →

today's D realize me, how poor I am in building logic :(

→ Reply

7 months ago, # ^ |

-27

If you know segment tree you can do it easily.

Code

vector<pair<int, int> > 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;
  }
}

→ Reply

213976

7 months ago, # ^ |

it's just a if logic block bro! segment tree is OVERKILL!!

→ Reply

7 months ago, # ^ |

Right, its an overkill. Just saw this beautiful solution:

→ Reply

foundnt_Alice

7 months ago, # ^ |

Thank for the compliment, cuz my solution is exactly the same, lol

→ Reply

Imran435

7 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 Code

void testcase() {
  int n, m;
  cin >> n >> m;

  map<int, int> mp;
  priority_queue<pair<int, int>, vector<pair<int, int>>, 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";
  }
}

→ Reply

foundnt_Alice

7 months ago, # ^ |

lol, we actually dont need to pop out xD

→ Reply

VinCenzo___

7 months ago, # ^ |

-10

same here,

my soln

→ Reply

sarthakjoleya

7 months ago, # ^ |

Me with my vector<set> and unordered_map solution be like: AMATEURS..
Link: https://atcoder.jp/contests/abc329/submissions/47726639

→ Reply

shahi_45

6 months ago, # ^ |

you could have just solved it using heaps tho

→ Reply

Nandy255

6 months ago, # ^ |

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.

→ Reply

SilverWing05

7 months ago, # |

Can we solve F using bitsets?

→ Reply

VinCenzo___

7 months ago, # ^ |

+11

you can merge small sets to large sets to reduce time complexity,here is the code

code

→ Reply

whymihere

6 months ago, # ^ |

Small-To-Large Merging

→ Reply

7 months ago, # |

Harder version of problem E (with outputting the operations)

Here from Coding Ninjas.

→ Reply

7 months ago, # ^ |

Any Hint for F

→ Reply

6 months ago, # ^ |

small to large merging technique submission

→ Reply

Akil_Newaz_Chy

6 months ago, # ^ |

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?

→ Reply

6 months ago, # ^ |

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 }$$$

→ Reply

Akil_Newaz_Chy

6 months ago, # ^ |

Thanks. Can u explain problem E also. I have no clue how to solve it!

→ Reply

6 months ago, # ^ |

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.

→ Reply

6 months ago, # ^ |

Why we need to check for both original and reverse string?

→ Reply

6 months ago, # ^ |

No we need not to check twice! (maybe he tried to be safe).

I did without that. Submission

→ Reply

6 months ago, # ^ |

okay

→ Reply

6 months ago, # ^ |

okay

→ Reply

Honeynutz

6 months ago, # ^ |

what is the complexity of swapping two sets??

→ Reply

aditya_108

6 months ago, # ^ |

Its constant time ie O(1)

→ Reply

Honeynutz

6 months ago, # ^ |

really!! how can swap do that?

→ Reply

6 months ago, # ^ |

+13

It exchanges the reference pointers for the respective variables!

→ Reply

7 months ago, # |

← Rev. 2 →

E is just a modified DP version of this problem (but it took me too long to recognize that)

Not a bad problem though

→ Reply

StarrGazerr

7 months ago, # ^ |

Can you share your submission?

→ Reply

shahi_45

6 months ago, # ^ |

please elaborate

→ Reply

6 months ago, # ^ |

← Rev. 3 →

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

→ Reply

vgtcross

6 months ago, # ^ |

Can I see your code? How does your solution handle this?

Input:
6 3
aaaccc
abc

Output:
No

→ Reply

6 months ago, # ^ |

← Rev. 3 →

It's not the prettiest piece of code that I've written, but it works

Spolier

#include <bits/stdc++.h>

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 prefix

Not sure if I actually need the extra 0-1 dp state, maybe just checking that a prefix and a suffix have matched is enough

→ Reply

vgtcross

6 months ago, # ^ |

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.

→ Reply