Topcoder SRM 715

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

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3655 |

4 | ksun48 | 3547 |

5 | jiangly | 3492 |

6 | Miracle03 | 3480 |

7 | ecnerwala | 3400 |

8 | maroonrk | 3385 |

9 | peehs_moorhsum | 3384 |

10 | sunset | 3338 |

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

1 | 1-gon | 214 |

2 | Um_nik | 191 |

3 | sus | 183 |

4 | Errichto | 180 |

5 | awoo | 179 |

6 | tourist | 178 |

7 | -is-this-fft- | 172 |

8 | Radewoosh | 171 |

9 | maroonrk | 169 |

9 | Ashishgup | 169 |

Topcoder SRM 715

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2021 12:49:45 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Holy Mike and Mother of TopCoder! Schedule announced up to end of May!

We will announce TCO schedule (online and regionals) very soon — it will be up to September. :P

Yes but only 2 rounds a month, how I miss the old days when there were 4 rounds every month :(

Starts in 1 day.

Another reminder because participation in rounds at this time is very less.

What was the point of making div1-250 incredibly easier than usual?

To test people's speedcoding / give randoms a chance to beat reds :)

I was the writer for this round. Here is the code and some short explanations.

div2ImageCompressionFor each pixel, we can find the topleft pixel of the corresponding block. This pixel much match that pixel in order to be compressible.

codeMaximumRangeDiv2We can do dp -> dp[a][b][c][d] -> Can we reach the state where we've processed the first a instructions, we currently have X = b, the lowest value of X we saw is c, and the highest value of x we saw is d?.

Alternatively, you can notice that one optimal solution will just take all the characters of one sign.

codeInPrePostNotice that the pre and post traversals tell us what the root is. We can then look into the in order traversal to know what the size of the left and right subtrees are and recurse. The idea for this is relatively simple, but the implementation can get very complicated if you are not careful.

codediv1MaximumRangeOne optimal solution is to take all the characters of the same sign.

codeClassicTowersConsider how to compute the minimum number of moves given a configuration. We can iterate through biggest disk to smallest disk. Initially, we'll fix the target rod as the rod containing the largest disk. So now, we have some a target rod, and the current disk we are considering. If the current disk is already at the target rod, we do nothing. Otherwise, WLOG, suppose our target is A, and our current disk is on B. Then, we want to recursively solve the problem when the target is C with one fewer disk, then add 2^(current disk number) (this can be derivied by knowing how towers of hanoi work).

We can use this solution to constuct a dp with state (

s_{1},s_{2},s_{3},want), meaning we needs_{i}disks on the i-th rod, and we want to move them all the the rodwant. We can then look at the binary representation ofkto determine when we need to switch our target or stay at the current target.codePreInPostWe can solve this by dp. We'll let dp[L][R] tell us whether or not it is possible to match the numbers in a1[L..R] with the corresponding numbers in a2. Of course, if the numbers in a2 are not adjacent it is impossible.

If t1 or t2 is in "in", this is easy, we can find the root and know the size of the left/right childs and recurse. If they are "post" and "pre", we'll need to try all roots. Overall, this means in the worst case, each dp state may take O(n) time to check.

Overall, the idea for this problem is not too complicated, but implementation can get very complicated if you are not careful.

codeYou were also the writer for the last 2 contests(w/o this SRM) I participated in :O

How to solve hard? I thought that if the solution is not unique (if it exists) then it will be kinda hard to check it. So I wrote some bruteforce with breaks hoping that bad branches will be very short. And it passes.

You can see div2 hard on how to check (in essence, you know the root from pre and post, and the in order traversal tells you how to split into left and right subtrees).

I'm not sure if it's possible to break a solution like yours.

I'm stupid, yeah. I use all that ideas in my bruteforce :)

Haha also thought about some kind of backtracking hoping it will crash shortly :P. But too late in the contest :<.

Actually checking if solution is good is pretty easy. I tried to solve problem recursively and in every execution I was given two orders and two types, but that didn't suffice to make good transitions. But if you are given three orders and three types then you always know what is the root (because you are given both preorder and postorder and can take first/last one in those), what belongs to left subtree and what belong to right (because you know where is root in inorder), so you can proceed recursively and recover whole tree in unique way.

Div1Easy : competitive typing

Div1Med : no clue

We in range 1400-1500 need an intermediate.

I had the following problem when I was an admin:

D1 Easy shouldn't be too hard. Otherwise many people will get zero.

E≤ 1500D1 Hard shouldn't be too hard. Otherwise targets will get bored.

H≥ 3000The difference between Easy and Medium should be small. Otherwise intermediate people will get bored.

M-E≤ 700For the same reason, the difference between Medium and Hard should be small.

H-M≤ 700Infeasible (´；ω；｀)

What is E, H, M? The rating that have 50% chance to solve?

Btw, do you remember why we wanted to set about 1% solve rate for Div1-Hard? (Even bmerry told me that Div1-Hard is unsolvable in recent years, so I'm thinking about lower the difficulty.)

Please don't take the values very seriously, I just wanted to say that it's very hard to find a problemset that suits everyone.

If my memory is correct, CF changed the cutoff between D1 and D2 a few years ago. I think if TC do the same (without changing the difficulties of problems) the situation becomes better. For blue coders D2 Hards look very suitable (they are somewhere between d1 easies and d1 mediums).

I don't remember about 1% rate, but that can be outdated given that recently only around 300 people participate in D1 and still lots of very strong people participate. Now I think anywhere between 1 person and 5% is suitable.

Btw why cant topcoder have more problems in a round? Even 1 extra problem would help decrease the massive jumps in difficulty.

You think the system and the applet are designed enough extensible and tough so that it's possible?

Maybe not. But IMO, topcoder is losing popularity and they have to do something about it before its too late.

I relay think so too :,(

I have 1800 and it's the same for me. Solve easy in 10 min and go AFK — that's my typical round. I stopped competing at Topcoder because of that.

I agree. I have 1799 in Topcoder, but last time (SRM 714), I solved easy in 4 min but I can't solve medium.

What I feel strongly recently is "Div1-Med difficulty is increasing".

The SRM 715-710 Med solved are 20, 45, 22,

2, 107,6. (Average numbers of competitor is about 270)But SRM 515-510 Med solved are 57, 39, 159, 67, 173, 32. (Average numbers of competitor is about 600)

So, I think people who rating is 1500-2200 can solve easy rapidly, but can't solve medium especially Div1-Med's solved is 1-digit.

Recently, I'm practicing in Div1-Med. If I could gain performance to 2000+,... but I couldn't solve Div1Med and I would be sad in contest that Div1-Med's solved is 1-digit.

Thank you always for the round that has a lot to learn, lewin :)

As for Div2-1000, if I assume that preorder and inorder are correct, and generate the postorder traversal of my own as the pseudocode says. Then, if I compare a3 with my_post_traversal, can this be the answer? Please correct me if I'm wrong.

wow, it's my first srm, and the result is no too bad, just learn and try.

ICPC WF spoiler (do not open unless completely sure)Div1 Hard is very similar to ICPC WF 2013 problem K (and, I think, both problems are solved in a very similar way).

Looks like the problem setters have taken this post( http://codeforces.com/blog/entry/51890 ) too seriously.