### cgy4ever's blog

By cgy4ever, history, 17 months ago, ,

Topcoder SRM 706

Update: Sorry but the link to the time was wrong, please click again and see local time in your timezone.

•
• +65
•

 » 17 months ago, # |   0 Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
 » 17 months ago, # |   0 Update: we added one more SRM on Jan 11th and moved the SRM on 14th to 21st.So we will have 3 SRMs in January! See details: 705, 706, 707
 » 17 months ago, # | ← Rev. 4 →   +13 This SRM conflicts for 35 minutes with the Facebook Hacker Cup Round 2 on the same date. Given that Round 2 is only 3 hours long this 35 minute overlap is fairly significant, and given that Facebook announced their time first, I think there should be some consideration given towards moving this SRM round in my opinion. Edit: For reference here is the link to the time of the Facebook Hacker Cup Round 2, as we can see it starts just 1 hour after the Topcoder round begins.
•  » » 17 months ago, # ^ |   +13 Ok, we moved it to 1 hour earlier, so you can see the system test result of this SRM before Facebook Hacker Cup.
 » 17 months ago, # |   0 Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
 » 16 months ago, # |   0 cgy4ever is this time correct for SRM 706?
•  » » 16 months ago, # ^ |   0 Yes, you can confirm it here: https://www.topcoder.com/community/events/
•  » » » 16 months ago, # ^ |   0 The link title says EST but it leads to 11 am UTC
•  » » » » 16 months ago, # ^ |   0 Thanks for notice that. Now fixed.
•  » » » » » 16 months ago, # ^ |   0 So is the current link correct? That would mean that it is in 2 hours from now on. Is that right? Because when I connect to topcoder site, SRM 706 doesn't appear.
 » 16 months ago, # |   +4 Finally, you did it! The contest will be on weekend and I can participate! What a pleasure =)
 » 16 months ago, # |   0 SRM is coming ... Get ready!
 » 16 months ago, # |   0 Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).
 » 16 months ago, # |   +9 Can someone login to arena.topcoder.com?
•  » » 16 months ago, # ^ |   +18 I usually open arena in Incognito to avoid cache issues and stuff — works for me at the moment.
 » 16 months ago, # |   0 Is arena working?
 » 16 months ago, # |   0 Anyone using KawigiEdit on the Topcoder Arena?I get an alert saying java.lang.Exception: actGenerateCode is currently disabled. Used to work fine before. Has any one else experienced this error from KawigiEdit?
 » 16 months ago, # |   +12 Does it possible to open code editor in web arena in fullscreen? Challenge someone while reading only 11 lines of code at a time isn't comfortable. Also I noticed that code from the web arena can be copied without any effort. I don't think that code extraction during challenge phase comply with topcoder rules :)
•  » » 16 months ago, # ^ |   0 I couldn't copy code within the Java applet as well. I don't know if that's a bug or a feature :(However I was able to copy-cut-paste using KawigiEdit.
 » 16 months ago, # |   +6 How to solve Div 2 1000 ? Thanks in advance.
 » 16 months ago, # |   0 How was Div2 1000 supposed to be solved?My initial idea how was to sorta map the given integers to new integers — for example: 5 2 5 4 -> 1 2 1 3and then find no. of increasing subsequences of length 3. However this seems to not consider several subsequences that may be allowed.
 » 16 months ago, # |   0 I am getting redirected from Topcoder Web Arena indefinitely. How do I fix this?
•  » » 16 months ago, # ^ |   0 This issue has been there for over a month. I don't even know where to report it.Either clear your browser cache or log in from incognito.
•  » » » 16 months ago, # ^ |   +1 They don't think they have a problem: Hi Egor,We've not been able to replicate on our side nor have we received any other complaints so I would like to make sure we're going about it the same way. Can you please send me a short video of the issue when you get a chance?Thank you, Valerie Can all of you, people, report the problem so that they start thinking that this is a serious issue?
•  » » » » 16 months ago, # ^ |   0 Where do I report the issue?
•  » » » » » 16 months ago, # ^ |   0
 » 16 months ago, # | ← Rev. 2 →   +73 div2 codes: http://ideone.com/CSvHORshort description for every solution: ThreeIncreasing (div2-easy)You should never remove candies from the last box because it doesn't help in making a sequence increasing. You must remove some candies from the second box if there isn't fewer of them that in the last box — you must decrease their number from b to c - 1. Finally, maybe you must remove candies from the first box, depending on the new number of candies in the second box. See my implementation for details. SellingFruits (div2-med)You can either try to find a formula or write a binary search. I recommend the latter approach because it requires less thinking. For fixed number of days you should calculate how many extra fruits you must buy (if any) and how much money it would cost you. Finally you should check if you have enough money to live that fixed number of days after buying extra fruits. MappingABC2 (div2-hard)This is an easier version of div1-med. In div1 version N was up to 3000 instead of 50. In a sequence that has "ABC" as subsequence there must be the first place (index) with letter 'A', the first place with 'B' after that, and the first place with 'C' after that. You can iterate over those three indices and for each of O(N3) cases compute the number of matching strings in O(N). For fixed three indices a string is divided into four parts. The first part (before first 'A') can't contain any 'A' (because otherwise the first 'A' would be earlier). The second part can't contain any 'B', and the third part can't contain any 'C'. You should apply those conditions and for every number check to how many letters it can be transformed. For example, if a number 10 appeared in the first part and in the second part, it can be transformed to 'C' only. Multiply numbers of ways to choose a letter for each number, and add it to the answer. See my code (given at the top of this comment) for details.div1 codes: MovingCandies, MappingABC, CoprimeNeighborsshort description for every solution: MovingCandies (div1-easy)There is a known problem: for given grid how many cells we should change to allowed, to make it possible to traverse between some two cells. It can be solved with something similar to BFS: create an array int dp[row][col] — for each cell compute the smallest cost to get to this cell (from the starting cell). But in this problem we can make a cell allowed only by making some other cell forbidden. Clearly, the final path between two corners can't exceed the total number of allowed cells in the initial grid. The problem turns out to be equivalent to: how many cells should we mark allowed so that there will be a path between corners of length not exceeding some number (initial number of allowed cells). Now it's enough to add one dimension to our previous BFS/dynamicProgramming, for example use an array int dp[row][col][len] — for each cell compute the smallest cost to get to this cell with a path of length at most len. Since len is up to h·w, this gives us solution. In the code above you can see an alternative, slightly easier approach in O((h·w)3) with an array bool reachable[row][col][len][cost]. MappingABC (div1-med)Find an O(n4) solution first (see div2-hard editorial). First try to decrease complexity to O(n3) — when we iterate over three indices, we don't have to recompute everything in O(n) each time. When we move the index of "first C after the two first fixed indices", only O(1) things change.Getting O(n2) is a bit trickier. This time iterate over only two indices: first 'A', and first 'B' after that. Let X denote the number of strings with "AB" subsequence matching those two fixed indices, and let Y denote the number of strings satisfying an additional condition that there should be no 'C' after our fixed 'B'. Then we should add X - Y to the answer because it's the number of matching strings with "ABC" subsequence. So now we can iterate over two indices only and apply a trick that allowed us to get O(n3) complexity. The final complexity is O(n2). CoprimeNeighbors (div1-hard)A tester (bmerry) found a deterministic solution but let me describe my intended randomized solution. Let's use x = 32 primes and let's say that every element of the sequence will be the product of exactly y = 11 primes. I create a sequence from left to right, randomly choosing every new element so that everything will be good so far (it should be coprime with a previous element and not coprime with other ones). For every new element I find x - y primes that aren't divisors of a previous element (I can't use them) and in a loop I try the following. I choose y of those x - y primes and compute the product of them. If the product exceeds 1018 or it's coprime with one of previous elements (I check that in O(n)), I repeat. It turns out that with well chosen values of x and y this solution doesn't repeat generating new numbers a lot — it computes a whole sequence under 1 second in my computer. You may wonder that new numbers will often be not coprime with any previous elements. Assuming that each number is chosen independently (they aren't obviously, but we only talk about the intuition) then the probability of two numbers being coprime is equal to the probability that two sets of y elements from the set of x elements are disjoint — you can check that this probability isn't much bigger than 1 / n so we can hope that new numbers will often be fine with all O(n) previous elements.
•  » » 16 months ago, # ^ |   0 hello Errichto can u describe problem-> MappingABC2 (div2-hard) more clearly . i did not understand your solution .
•  » » » 16 months ago, # ^ |   0 Do you understand the meaning of the "three indices" in my solution? For a moment forget about the initial sequence with numbers. Do you know how to e.g. count strings of length 10 with letters A, B, C, so that those three indices will be at positions 2, 5 and 7?
•  » » » » 16 months ago, # ^ |   0 i didn't understand meaning of three indices and also example given in 2nd comment. total strings will be -> 3 * 1 * 3 * 3 * 1 * 3 * 1 * 3 * 3 * 3 = 2187 may be....
•  » » » » » 16 months ago, # ^ | ← Rev. 3 →   0 It should be 2 * 1 * 2 * 2 * 1 * 2 * 1 * 3 * 3 * 3. (EDIT: small typo)Do you know how to check if one string is a subsequence of the other? For each letter in a shorter string we should greedily choose the closest possible matching letter in a longer string. The "three indices" are indices of letters matched in a longer string (assuming that a shorter string was "ABC").For a string BCCBACABABCABCC the three indices would be at positions marked bold: BCCB A CA B AABBA C ABCC
•  » » » » » » 16 months ago, # ^ |   0 ok i got it . in given example BCCBACABABCABCC first occurrence of shorter string "ABC" at position BCCB A CA B AABBA C ABCC. but above if we want to count 10 length strings where restrictions that at position 2 -> "A", at position 5 -> "B" and position 7 -> "3" than these position contain 1 but remaining position can contain any three characters ( A, B, C) so all remaining position contain 3.
•  » » » » » » » 16 months ago, # ^ |   0 If we say that the first 'A' is at position 2, the very first can be only 'B' or 'C'. Similar thing happens later: we say that the first 'B' after first 'A' is at position 5.
•  » » » » » » » » 16 months ago, # ^ |   0 u want to say that at 2nd position -> 'A' and after it first 'B' will be at 5th position so between 2 and 5 there will be only two character possible which are -> A or C so we uesd ..... 1 * 2 * 2 * 1 ....
•  » » » » » » » » » 16 months ago, # ^ |   0 yes
•  » » » » » » » » » 16 months ago, # ^ |   0 ok i got it.i understood meaning of indices. can you explain last concept which is , how can i transformed given numbers in letter (A, B, C)
•  » » » » » » » » » 16 months ago, # ^ |   0 It's described in my first comment. After fixing the three indices we know for which position what letter(s) can't be there and thus we know for every number (value) what letters it can't be transformed into. We should multiply numbers of allowed letters for all appearing numbers.
•  » » » » » » » » » 16 months ago, # ^ |   +1 okk i got it completely . thank you ... thank a lot .. can i ask one more question , which type of technique or algorithm use for this type of problem. how can i think mathematically for this type of problems...
•  » » » » » » » » » 16 months ago, # ^ |   0 I don't how to call this technique. Don't care about it, just solve problems.
•  » » » » » » » » » 16 months ago, # ^ |   0 okkk Errichto.. thanks for help
•  » » 5 months ago, # ^ |   0 Dear Sir, Can you explain please why the time complexity of Div 1 MovingCandies is O(h.w.(h.w).log(h+w)) unable to understand log(h+w) part? Thanks in advance.
 » 16 months ago, # |   +31 Here is a very similar problem to Hard: http://artofproblemsolving.com/community/c6h627236p3763526 about existence of such an infinite sequence. However unfortunately its solution doesn't help in any way to today's problem (even though it exists, but all given examples grow exponentionally). I used a pretty simple approach (I was relieved it worked because it was by far not obvious that it will produce an answer). My elements will correspond to subsets with 9 elements out of 19 elements set (then I will multiply some primes to get actual numbers). I implicilty create edges between all pairs of subsets that their intersection is empty and I use a backtrack to find an induced path of 500 vertices. Fortunately, works very fast :).
 » 16 months ago, # | ← Rev. 2 →   0 Never mind, Invalid testcase!
 » 16 months ago, # |   +19 I wondered why div2 easy was so hard and didn't realize I was in div1 during contest ...