yaksha's blog

By yaksha, history, 3 years ago, In English

Since I was not able to find an announcement for ARC99 , maybe we can discuss some problems here?!

I wanted to ask about the problem D of ARC99, how did you solve it? The editorial way is incomplete .. I was trying to find some pattern in snuke's numbers but was not able to find any!..

Read more »

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

By yaksha, history, 3 years ago, In English

Hi, So I recently attempted this problem, I was not able to solve it , and went to read the editorial.. The editorial however did not give proof for the DP state and transition , and I am having a lot of trouble actually understanding how the DP transition is working...

Problem : 543C - Remembering Strings

Solution : 11035719

My Thoughts:

the DP state is "mask" which denotes the strings that have been already made easy to remember.. The editorial says , we pick up the "lowest bit" which is ON and then find the most optimum result while focusing only on that 'lowest bit' (by checking all the columns)

However , in my opinion , for the current state "mask" we should check the same thing not just for the lowest bit , but infact for all of the bits that are ON . .

Please help, I think I am conceptually very wrong in this problem..

Read more »

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

By yaksha, history, 3 years ago, In English

Hi,

I have seen the editorial of Div1B of the recent round and completely understood it. .

There is this recursion there that , f[i...j] = f[i...j-1] ^ f[i+1 ... j]

Now I get that some people noticed this via observation of patterns and some mentioned in comments that we can prove it through induction .

I want to ask people who solved this fastly in contest timings , how did you get to this solution?

If you made observations only , how did you make fast observations?

In case you actually "GOT" to the solution mathematically ( not proved through induction , but constructively ) , how did you do that?

Read more »

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

By yaksha, history, 3 years ago, In English

Hi , So I was trying this E problem which was 900 points ,

This problem requires rotation of axes and I know how that is done and also know all the details behind that ,

But the editorial says "rotate the axes by 45 degrees and then find maximum of ... " . . I was not able to follow the EDITORIAL from that point onwards!

I believe this is a nice GEOMETRY problem and I am weak at it ,

Please open this problem and help me know what that one line means , "Now we are intersted in a pair of points such that max ( dx, dy ) = D"

Thankyou!

Read more »

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

By yaksha, history, 4 years ago, In English

Hello all , Lately I am trying to learn more about kuhn's algorithm , But whenever I type "Kuhn's Algorithm" on google the result shows "Hungarian Algorithm"

So I thought both of them are the same ,

After some surfing on topcoder blogs , I found that Kuhn's algorithm works in O(VE) whereas hungarian takes O(V^3) , so are they not same?!

But the way it's given in the topcoder blog , I think that Kuhn's can only be applied on a bipartite graph when all the edge weights are same . .

Is it true , can Kuhn's only be applied when when all the edge weights are same?

Also can someone tell me all the most used flow algorithms / matching algorithms and where to best study them from ? So far I only know the basic Max Flow problem and the Kuhn's algorithm!

The topcoder blog I studied from ==> Matchings

Thanks for helping!

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By yaksha, history, 4 years ago, In English

Hi, Lately , I am not able to even touch the atcoder 'D' tasks , Last Regular round , which was Regular round 93 , there was a nice thinking 'D' task which was a constructive algorithm problem and I was not able to solve it. .

Same was the case in the last to last regular round on Atcoder. . Round 92 , Task D — Two Sequences . .

The problem is I have come to realize that maybe problems of these types are in general hard for me and I should train on them more ,

I am weak at greedy problems and constructive algorithm problems . . Are there any other places except for Atcoder where I can practice problems similar to Atcoder problem D ? I want to become fast and accurate at solving D , particualrly greedy and constructive , but I cant find the same quality problems anywhere except for atcoder , and the quantity of problems there is very less ,

Please help me. I need problems similar to Atcoder D for practice!

Also tell me some good sources to practice my greedy and constructive problems!!

Read more »

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

By yaksha, history, 4 years ago, In English

Hi, So this has happened before , and it happens from time to time , only this time I really got frustrated and hence am asking this question . . Why is my segment tree so slow?

Some problems like this -> 301D - Yaroslav and Divisors , have the official solution, the same as the solution that I code but somehow my segment tree is always very slow. This has happened before in live contests as well . Maybe my implementation is very bad , that's why I want to learn where I am making mistake , and please provide me with a better implementation if I am making a mistake..

My implementation to the above problem,using segment trees, which TLE's --> 36075338 . Help me out on this please!

UPDATE: I solved the problem doing some minor optimizations like scanf/printf and using int instead of long long , but my solution is still very slow compared to other solutions..

Read more »

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

By yaksha, history, 4 years ago, In English

Hi, I was solving a problem and it required printing euler path on a directed graph Now,I was unaware of the how to do euler path finding on a directed graph, I tried to search on google but no luck..

What exactly are the conditions that are to be fulfilled to KNOW that a euler path exists and also what are ways to print it... I know of "Fleury’s Algorithm" , but as far as I know (and I know little), this algo is for directed graphs only.. Also came to knew about " Hierholzer’s Algorithm" but this also seems to be working on undirected graphs..

The problem that I was attempting -- 508D - Tanya and Password

The editorial of this problem mentions some points regarding finding euler path on directed graphs but it's not very clear and provides no explanation...

Please can some one help me and also possibly provide me with resources where I can study this?!

Have a nice day!

Read more »

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

By yaksha, history, 4 years ago, In English

Hi all, I have been doing some dynamic programming problems and I stumbled around a Never seen before type of problem

Ofcourse the problem is new to me maybe because I am not much experienced but I still feel like the problem uses a unconventional style of DP and I am NOT able to understand it,

If some people have not tried DP , or want to try new problem on DP, attempt the problem,its a good one ( when doing with DP) : Problem : 276D - Little Girl and Maximum XOR || Author's DP solution

Please help me understand the DP state and the transition,I tried understanding with editorial but was not able to after my best efforts,

Thankyou,looking forward to your help.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By yaksha, history, 4 years ago, In English

Hello,

I was doing this problem and the editorial was in russian, I tried to convert editorial to english but it did not work.. Can someone help me with this problem? 295B - Greg and Graph

Thanks!!

Read more »

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it