sahal's blog

CSES Problemset Editorials (almost all section editorial collection)
By sahal, 4 years ago, In English

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

  • Vote: I like it
  • +32
  • Vote: I do not like it

Comments Comments (24)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thank you, Really helpful.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

couldn't thank you more bro!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

And this

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks added

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok, after I did euler tour on the tree, is it just segment tree? Or are there something else?

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        just that, you can use a BIT if you'd like

        → Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)).

    → Reply
»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

thank you so much, very helpful!

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can also add the NeatlyStructured YouTube channel

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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