Topcoder SRM 706

Time: 11:00 am EST Saturday, January 21, 2017

Calendar: https://www.topcoder.com/community/events/

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

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | Um_nik | 3337 |

3 | Petr | 3298 |

4 | W4yneb0t | 3218 |

5 | Radewoosh | 3216 |

6 | OO0OOO00O0OOO0O0…O | 3188 |

7 | Syloviaely | 3168 |

8 | izrak | 3109 |

9 | anta | 3106 |

10 | fateice | 3099 |

# | User | Contrib. |
---|---|---|

1 | tourist | 184 |

2 | rng_58 | 170 |

3 | csacademy | 165 |

4 | Petr | 158 |

5 | Swistakk | 154 |

6 | lewin | 149 |

7 | Errichto | 147 |

8 | matthew99 | 146 |

9 | adamant | 141 |

9 | Zlobober | 141 |

Topcoder SRM 706

Time: 11:00 am EST Saturday, January 21, 2017

Calendar: https://www.topcoder.com/community/events/

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

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2018 08:47:05 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).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

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.

Ok, we moved it to 1 hour earlier, so you can see the system test result of this SRM before Facebook Hacker Cup.

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).cgy4ever is this time correct for SRM 706?

Yes, you can confirm it here: https://www.topcoder.com/community/events/

The link title says

ESTbut it leads to 11 amUTCThanks for notice that. Now fixed.

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.

Finally, you did it! The contest will be on weekend and I can participate! What a pleasure =)

SRM is coming ... Get ready!

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).Can someone login to arena.topcoder.com?

I usually open arena in Incognito to avoid cache issues and stuff — works for me at the moment.

Is arena working?

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?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 :)

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.

How to solve Div 2 1000 ? Thanks in advance.

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 3`

and then find no. of increasing subsequences of length 3. However this seems to not consider several subsequences that may be allowed.

I am getting redirected from Topcoder Web Arena indefinitely. How do I fix this?

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.

They don't think they have a problem:

Can all of you, people, report the problem so that they start thinking that this is a serious issue?

Where do I report the issue?

support@topcoder.com

div2 codes: http://ideone.com/CSvHOR

short 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

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

Nwas 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 ofO(N^{3}) cases compute the number of matching strings inO(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, CoprimeNeighbors

short 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 toh·w, this gives us solution. In the code above you can see an alternative, slightly easier approach inO((h·w)^{3}) with an array`bool reachable[row][col][len][cost]`

.MappingABC (div1-med)Find an

O(n^{4}) solution first (see div2-hard editorial). First try to decrease complexity toO(n^{3}) — when we iterate over three indices, we don't have to recompute everything inO(n) each time. When we move the index of "first C after the two first fixed indices", onlyO(1) things change.Getting

O(n^{2}) is a bit trickier. This time iterate over only two indices: first 'A', and first 'B' after that. LetXdenote the number of strings with "AB" subsequence matching those two fixed indices, and letYdenote the number of strings satisfying an additional condition that there should be no 'C' after our fixed 'B'. Then we should addX-Yto 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 getO(n^{3}) complexity. The final complexity isO(n^{2}).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 exactlyy= 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 findx-yprimes that aren't divisors of a previous element (I can't use them) and in a loop I try the following. I chooseyof thosex-yprimes and compute the product of them. If the product exceeds 10^{18}or it's coprime with one of previous elements (I check that inO(n)), I repeat. It turns out that with well chosen values ofxandythis 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 ofyelements from the set ofxelements are disjoint — you can check that this probability isn't much bigger than 1 /nso we can hope that new numbers will often be fine with allO(n) previous elements.hello Errichto can u describe problem->

MappingABC2 (div2-hard)more clearly . i did not understand your solution .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....

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

ACABAABBACABCCok i got it . in given example BCCBACABABCABCC first occurrence of shorter string "ABC" at position BCCB

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

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

yes

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)

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.

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

I don't how to call this technique. Don't care about it, just solve problems.

okkk Errichto.. thanks for help

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.

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

Never mind, Invalid testcase!

I wondered why div2 easy was so hard and didn't realize I was in div1 during contest ...