tag:blogger.com,1999:blog-1953325079793449971.post5097632049409828403..comments2024-02-15T20:32:59.333+01:00Comments on Algorithms Weekly by Petr Mitrichev: Joy of solving easy problemsPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-1953325079793449971.post-91889441051003079352013-05-10T11:34:19.184+02:002013-05-10T11:34:19.184+02:00let ia, ic, it, ig be the counts in put. Let oa, o...let ia, ic, it, ig be the counts in put. Let oa, oc, ot, og be counts in output.<br /><br />We know that ia+ic+it+ig = oa + oc + ot + og = len(string). Therefore, for at least one x, ox >= ix; hence in particular the answer >= min(ix).X Ynoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-81847718280744273562013-05-10T11:34:18.209+02:002013-05-10T11:34:18.209+02:00Why "that at least the length of the longest ...Why "that at least the length of the longest common subsequence is the number of occurences of one of the characters A, C, T, G in the given string" in Rahul's comment. I couldn't get this statement. Any intuition ?Siddharth Boranoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-10512743777566871792013-05-10T11:34:17.143+02:002013-05-10T11:34:17.143+02:00Cool problem!
What about finding the lexicographi...Cool problem!<br /><br />What about finding the lexicographically first string, what's the best running time you can achieve?X Ynoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-12872001088500398112013-05-10T11:34:16.148+02:002013-05-10T11:34:16.148+02:00 Intuition:-
1. Think of the input string as supe... Intuition:-<br /><br />1. Think of the input string as superimposition of same character sub-strings ("AAA...", "CC.." etc). Let the sub-string sizes be K1 <= K2 <= K3 <= K4. <br />2. Remember that the second string is of the same length. Again view it in terms of same character sub-strings. Now note that you cannot pick a string where ALL the same character sub-strings are smaller than K1 in size, so K1 is the least amount of overlap between the two strings. <br />3. You will probably see that there are many possible answers now, what Rahul/Petr suggested is just one of them.Jasinghnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-49417589180365996452013-05-10T11:33:58.130+02:002013-05-10T11:33:58.130+02:00I want t o be as good as you. Can you highlight ho...I want t o be as good as you. Can you highlight how one can solve this kind of problemThankGod Ukachukwunoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-38808645579553379672013-05-10T11:33:56.102+02:002013-05-10T11:33:56.102+02:00Create a string of just the same letter, e.g. xxx....Create a string of just the same letter, e.g. xxx...xxx, where x is the character that occurs the least number of times in the given string. The reason is that, that at least the length of the longest common subsequence is the number of occurences of one of the characters A, C, T, G in the given string, and hence greater than or equal to the number of occurences of the character that occurs the minimum number of times.Rahul Gulatinoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-58919598244224338442013-05-10T11:33:55.109+02:002013-05-10T11:33:55.109+02:00 Actually it would be correct the letter G repeate... Actually it would be correct the letter G repeated the least number of times.Sri D Kirannoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-80948086137519013762013-05-10T11:33:54.124+02:002013-05-10T11:33:54.124+02:00Not entirely correct. For an input ACCTTT your alg...Not entirely correct. For an input ACCTTT your algorithm would give AAAAAA while the correct answer would be GGGGGG. But the idea is probably right :)Danil Sokolovhttp://profiles.google.com/daniloveskynoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-3115989584649705142013-05-10T11:33:52.095+02:002013-05-10T11:33:52.095+02:00I don't think that's a coincidence - I bel...I don't think that's a coincidence - I believe the Open Cup contest was ran on the problems from that contest.Petrhttp://petr-mitrichev.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-73660296125402707522013-05-10T11:33:51.110+02:002013-05-10T11:33:51.110+02:00Huh, this problem appeared also in the Polish Coll...Huh, this problem appeared also in the Polish Collegiate Programming Contest 2012 3 weeks ago (problem DNA). Jakub Tarnawskihttp://www.facebook.com/jakub.tarnawskinoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-36146198223749965342013-05-10T11:33:50.098+02:002013-05-10T11:33:50.098+02:00Yes, exactly.Yes, exactly.Petrhttp://petr-mitrichev.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-72215398781651848762013-05-10T11:33:49.231+02:002013-05-10T11:33:49.231+02:00 I don't think this is correct solution. Consi... I don't think this is correct solution. Consider the following test: ATCATCATCATCATCATCGGG. Your solution would output GGG...GG with the similarity equal to 3. While AAA...AA as well as other letters would give 1.<br /><br />But in general I think that the pattern is correct. But rather than taking the least frequent character, I think it is better to take one that is continuously repeated the least number of times. Thus for the mentioned example the output would be on of: AA...A, TT...T, CC...C. At least I failed to come up with the counter-example.Alexander Solovetsnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-52420148982989481102013-05-10T11:33:47.100+02:002013-05-10T11:33:47.100+02:00Indeed I have missed that point. Thanks.Indeed I have missed that point. Thanks.Alexander Solovetsnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-57108114083279093152013-05-10T11:33:46.099+02:002013-05-10T11:33:46.099+02:00You are misunderstanding what a common subsequence...You are misunderstanding what a common subsequence is. For AAA...AA the answer is not 1, but the number of A characters. As Petr has written - the longest string that can be obtained from both strings by dropping some characers. This doesn't mean the characters are consecutive(next to each other).Petar Minchevnoreply@blogger.com