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

13 месяцев назад, # |

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

→ Ответить

no_oneplb

13 месяцев назад, # ^ |

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

→ Ответить

13 месяцев назад, # ^ |

Can you share your code

→ Ответить

no_oneplb

13 месяцев назад, # ^ |

Sure,here is the link — Code

→ Ответить

213976

13 месяцев назад, # |

← Rev. 2 →

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

→ Ответить

13 месяцев назад, # ^ |

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

→ Ответить

213976

13 месяцев назад, # ^ |

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

→ Ответить

13 месяцев назад, # ^ |

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

→ Ответить

hopium

13 месяцев назад, # ^ |

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

→ Ответить

Imran435

13 месяцев назад, # ^ |

-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";
  }
}

→ Ответить

hopium

13 месяцев назад, # ^ |

lol, we actually dont need to pop out xD

→ Ответить

VinCenzo___

13 месяцев назад, # ^ |

-10

same here,

my soln

→ Ответить

shahi_45

13 месяцев назад, # ^ |

you could have just solved it using heaps tho

→ Ответить

Nandy255

13 месяцев назад, # ^ |

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.

→ Ответить

SilverWing05

13 месяцев назад, # |

Can we solve F using bitsets?

→ Ответить

VinCenzo___

13 месяцев назад, # ^ |

+11

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

code

→ Ответить

13 месяцев назад, # |

Harder version of problem E (with outputting the operations)

Here from Coding Ninjas.

→ Ответить

13 месяцев назад, # ^ |

Any Hint for F

→ Ответить

13 месяцев назад, # ^ |

small to large merging technique submission

→ Ответить

Akil_Newaz_Chy

13 месяцев назад, # ^ |

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?

→ Ответить

13 месяцев назад, # ^ |

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

→ Ответить

Akil_Newaz_Chy

13 месяцев назад, # ^ |

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

→ Ответить

13 месяцев назад, # ^ |

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.

→ Ответить

13 месяцев назад, # ^ |

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

→ Ответить

13 месяцев назад, # ^ |

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

I did without that. Submission

→ Ответить

13 месяцев назад, # ^ |

okay

→ Ответить

13 месяцев назад, # ^ |

okay

→ Ответить

MultiThread

13 месяцев назад, # ^ |

what is the complexity of swapping two sets??

→ Ответить

aditya_108

13 месяцев назад, # ^ |

Its constant time ie O(1)

→ Ответить

MultiThread

13 месяцев назад, # ^ |

really!! how can swap do that?

→ Ответить

13 месяцев назад, # ^ |

+13

It exchanges the reference pointers for the respective variables!

→ Ответить

13 месяцев назад, # |

← 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

→ Ответить

shahi_45

13 месяцев назад, # ^ |

please elaborate

→ Ответить

13 месяцев назад, # ^ |

← 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

→ Ответить

vgtcross

13 месяцев назад, # ^ |

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

Input:
6 3
aaaccc
abc

Output:
No

→ Ответить

13 месяцев назад, # ^ |

← 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

→ Ответить

vgtcross

13 месяцев назад, # ^ |

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.

→ Ответить