Блог пользователя sahal

CSES Problemset Editorials (almost all section editorial collection)
Автор sahal, 4 года назад, По-английски

CSES Problemset

All Section Mixed Editorial
Sorting and Searching
Dynamic Programming
Graph
Range Queries
Tree
Mathematics
String

If I have missed some, let me know...

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

I think you should add Williams 12 hour CSES problem set stream too. It has one of the neatest solutions to these problem.
Here's the link to it.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

That Link Introduction to DP on Trees || CSES Tree algorithms || Video lectures is broken, it should be Introduction to DP on Trees || CSES Tree algorithms || Video lectures

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Thank you, Really helpful.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

U can add this too under dp section- video editorial Youtube Link

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

couldn't thank you more bro!

→ Ответить
»
21 месяц назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

And this

→ Ответить
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks added

    → Ответить
    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      hello sahal,I bet you've solved the whole cses problem set by now, but you're still in pupil...does that mean even after knowing all those algos and techniques and solving more than 2000 problem on cf, it's still not worth to reach stable specialist

      → Ответить
      • »
        »
        »
        »
        21 месяц назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        He obviously hasn't solved every problem on CSES. Finding blogs with solutions is not the same as actually solving the problems. Also, you definitely don't need to know everything from CSES to become a specialist.

        → Ответить
»
19 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

There isn't a topic for problem "path queries" in trees problems, is it similar to a problem before it ?? I tried to solve it but couldn't figure out the solution, any hints please ? Thanks in advance.

→ Ответить
  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    It uses the same technique as in the previous one, "Subtree Queries," which is euler tour.

    → Ответить
  • »
    »
    18 месяцев назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    For each node v, call value[v] as the value assigned to the node and sum[v] as the sum from root of the tree to that node v.

    For each node v, we will store sum[v] in its euler tour location.

    Incrementing the value of node v by x, increases root to node sum values for all the nodes in the subtree of v by x. Since subtrees correspond to subarrays, this is an equivalent range increment operation on an array.

    Finding the sum of values on a u-v path is equal to sum[u] + sum[v] — 2*sum[lca] + value[lca]. sum[u], sum[v], sum[lca] are all just values in the euler tour array.

    So effectively, we need to support two operations on the euler tour array: 1. Performing Range increment on an subarray. 2. Querying value at index on an array.

    Both of these operations can be simultaneously supported by either a binary indexed tree or a segment tree. (with segment tree you'll need to implement lazy prop, but with BIT its far simpler).

    → Ответить
    • »
      »
      »
      18 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, I already did that thanks for your explanation but my question was for the next problem "Path Queries II", in this problem a simple euler tour and segment tree won't be enough you need something more complex which is heavy-light decomposition. but even the HLD solution is not enough because its time complexity is O(q * log^2(n)) and that is a TLE for sure. so my question is what is the approach for this problem after knowing that HLD is not enough? is it link-cut trees? or there is something else ?

      → Ответить
»
12 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

HELP, Can anyone point it out? What I am missing in Coding Company , submission I am thinking of open close interval dp solution. But it doesn't pass all test cases

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I didn't understand the intuition behind your approach, but it seems not to count cases where teams are formed as a subsequence, not a subarray. Consider the following case: 3 3 2 3 5 Your code outputs 4, when the real answer is 5 (most likely didn't consider such division : (2,5),(3)).

    → Ответить
»
5 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

thank you so much, very helpful!

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can also add the NeatlyStructured YouTube channel

→ Ответить
»
3 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My one testcase is failing (7th testcase only) in this problem Edit Distance I am unable to understand why. If someone can explain it will be really helpful. Thanks in advance.

void solve() {
	string s1,s2;
	cin>>s1>>s2;
	ll n=sz(s1);
	ll m=sz(s2);
	s1='@'+s1;
	s2='@'+s2;
	vector<vl> dp(n+1,vl(m+1,1e18));
	ll temp;
        dp[0][0]=0;
	FOR(i,1,n+1){
	  FOR(j,1,m+1){
	    if(s1[i]==s2[j]){
	        dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j]+1,dp[i][j-1]+1));
	    }
	    else{
	      temp = min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]));
	      dp[i][j] = temp+1;
	    }
	  }
	}
	cout<<dp[n][m]<<nl;
}
→ Ответить