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

13 months ago, # |

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

→ Reply

no_oneplb

13 months ago, # ^ |

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

→ Reply

13 months ago, # ^ |

Can you share your code

→ Reply

no_oneplb

13 months ago, # ^ |

Sure,here is the link — Code

→ Reply

213976

13 months ago, # |

← Rev. 2 →

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

→ Reply

13 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

13 months ago, # ^ |

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

→ Reply

13 months ago, # ^ |

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

→ Reply

hopium

13 months ago, # ^ |

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

→ Reply

Imran435

13 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

hopium

13 months ago, # ^ |

lol, we actually dont need to pop out xD

→ Reply

VinCenzo___

13 months ago, # ^ |

-10

same here,

my soln

→ Reply

shahi_45

13 months ago, # ^ |

you could have just solved it using heaps tho

→ Reply

Nandy255

13 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

13 months ago, # |

Can we solve F using bitsets?

→ Reply

VinCenzo___

13 months ago, # ^ |

+11

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

code

→ Reply

13 months ago, # |

Harder version of problem E (with outputting the operations)

Here from Coding Ninjas.

→ Reply

13 months ago, # ^ |

Any Hint for F

→ Reply

13 months ago, # ^ |

small to large merging technique submission

→ Reply

Akil_Newaz_Chy

13 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

13 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

13 months ago, # ^ |

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

→ Reply

13 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

13 months ago, # ^ |

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

→ Reply

13 months ago, # ^ |

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

I did without that. Submission

→ Reply

13 months ago, # ^ |

okay

→ Reply

13 months ago, # ^ |

okay

→ Reply

Honeynutz

13 months ago, # ^ |

what is the complexity of swapping two sets??

→ Reply

aditya_108

13 months ago, # ^ |

Its constant time ie O(1)

→ Reply

Honeynutz

13 months ago, # ^ |

really!! how can swap do that?

→ Reply

13 months ago, # ^ |

+13

It exchanges the reference pointers for the respective variables!

→ Reply

13 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

shahi_45

13 months ago, # ^ |

please elaborate

→ Reply

13 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

13 months ago, # ^ |

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

Input:
6 3
aaaccc
abc

Output:
No

→ Reply

13 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

13 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