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

2 years ago, hide # |

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

→ Reply

no_oneplb

2 years ago, hide # ^ |

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

→ Reply

2 years ago, hide # ^ |

Can you share your code

→ Reply

no_oneplb

2 years ago, hide # ^ |

Sure,here is the link — Code

→ Reply

213976

2 years ago, hide # |

← Rev. 2 →

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

→ Reply

2 years ago, hide # ^ |

-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

2 years ago, hide # ^ |

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

→ Reply

2 years ago, hide # ^ |

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

→ Reply

hopium

2 years ago, hide # ^ |

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

→ Reply

Imran435

2 years ago, hide # ^ |

-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

hopium

2 years ago, hide # ^ |

lol, we actually dont need to pop out xD

→ Reply

VinCenzo___

2 years ago, hide # ^ |

-10

same here,

my soln

→ Reply

slurpieboy

2 years ago, hide # ^ |

you could have just solved it using heaps tho

→ Reply

Nandy255

2 years ago, hide # ^ |

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

2 years ago, hide # |

Can we solve F using bitsets?

→ Reply

VinCenzo___

2 years ago, hide # ^ |

+11

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

code

→ Reply

2 years ago, hide # |

Harder version of problem E (with outputting the operations)

Here from Coding Ninjas.

→ Reply

2 years ago, hide # ^ |

Any Hint for F

→ Reply

2 years ago, hide # ^ |

small to large merging technique submission

→ Reply

Akil_Newaz_Chy

2 years ago, hide # ^ |

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

2 years ago, hide # ^ |

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

2 years ago, hide # ^ |

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

→ Reply

2 years ago, hide # ^ |

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

2 years ago, hide # ^ |

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

→ Reply

2 years ago, hide # ^ |

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

I did without that. Submission

→ Reply

2 years ago, hide # ^ |

okay

→ Reply

2 years ago, hide # ^ |

okay

→ Reply

MultiThread

2 years ago, hide # ^ |

what is the complexity of swapping two sets??

→ Reply

aditya_108

2 years ago, hide # ^ |

Its constant time ie O(1)

→ Reply

MultiThread

2 years ago, hide # ^ |

really!! how can swap do that?

→ Reply

2 years ago, hide # ^ |

+13

It exchanges the reference pointers for the respective variables!

→ Reply

2 years ago, hide # |

← 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

slurpieboy

2 years ago, hide # ^ |

please elaborate

→ Reply

2 years ago, hide # ^ |

← 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

2 years ago, hide # ^ |

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

Input:
6 3
aaaccc
abc

Output:
No

→ Reply

2 years ago, hide # ^ |

← 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

2 years ago, hide # ^ |

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