Starts in less than 24 Hours.

https://www.timeanddate.com/worldclock/fixedtime.html?msg=Topcoder+SRM+729&iso=20180210T12&p1=179

Contest is running

Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)

01:34:02

Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)

01:34:02

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

1 | tourist | 3434 |

2 | OO0OOO00O0OOO0O0…O | 3280 |

3 | Syloviaely | 3274 |

4 | Petr | 3233 |

5 | Um_nik | 3213 |

6 | ko_osaga | 3124 |

7 | mnbvmar | 3096 |

8 | Radewoosh | 3061 |

9 | fateice | 3058 |

10 | Benq | 3056 |

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

1 | Radewoosh | 167 |

2 | rng_58 | 162 |

3 | tourist | 159 |

4 | Petr | 153 |

5 | Swistakk | 151 |

5 | csacademy | 151 |

7 | Vovuh | 145 |

7 | Um_nik | 145 |

9 | Errichto | 144 |

10 | PikMike | 142 |

10 | Nickolas | 142 |

Starts in less than 24 Hours.

https://www.timeanddate.com/worldclock/fixedtime.html?msg=Topcoder+SRM+729&iso=20180210T12&p1=179

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/19/2018 17:15:59 (f1).

Desktop version, switch to mobile version.

User lists

Name |
---|

Reminder: Contest starts in 2h. Let’s enjoy!

Can you please announce the round a bit earlier next time?

I really like the TC problems but one literally needs to ruin his plans to be able to participate. I guess this is one of the main reasons for the low participation.

You can subscribe to TopCoder's Google Calendar, and then set up your own notifications any way you please:

https://calendar.google.com/calendar/embed?src=qshn4jb7pq3f8l46nvvilj5c6o%40group.calendar.google.com

How to solve div2 800?

Calculate the probability of picking each item and then apply bitmask dp on states.

http://blog.quantitations.com/stochastic%20processes/2013/02/07/expected-number-of-steps-of-a-markov-process/

Answer will be dp[0]

In div1 450, is there any simple solution or do we greedily do a bfs using only vertices on edges(is this right)??

Bfs on edges definitely works (just passed in practice room). I doubt there's a simpler way to do it since this is already pretty straightforward.

How to solve div2 2nd and 3rd problem?

For div2 medium, you can use dynamic programming (there are non DP ways to solve it as well). The state consists of the following:

For example, if I have rectangles 0,4,6,8 (the 0 is x1, the 4 is y1, the 6 is x2, the 8 is y2) and 5,2,9,5, then the intersection rectangle would be 5,4,6,5.

So for each state, we either try to include the current rectangle, or we skip it. We take the best of those two results. When we include the current rectangle, we have to calculate a new intersection rectangle based on the current state's intersection rectangle and the rectangle at the current index. If there's no intersection rectangle for these two, then we can't use this rectangle. Otherwise, we pass this new intersecting rectangle to the next state.

Can we solve this problem using Coordinate Compression in 2D ?

Yes, this is what I did.

The division winner (who was also in my room) wrote the code below (retyped by me without macros). I too solved it in O(n^3) by sorting coordinates but I used midpoints of each adjacent pair of coordinates to ensure I avoided corner/edge overlaps. I don't understand why the code below works despite staring at it for a while. Can anyone help explain? Why does he take "-1" of the x2 but then check x+1 <= x2 in the inner loop? (I can see the 'x' in the inner loop includes both x1/x2).

This is my code,I was the winner of SRM729 div2:) x,y means a square of size 1*1 at (x,y,x+1,y+1). I check every "useful" pair of x,y and updata the ans. Sorry for poor English.

Fantastic, what a great method. I thought it was "point within rectangle" but now I see, it is actually checking "1x1 square within rectangle".

I can see this "Useful 1x1 square" idea being applicable in many such problems.

Thanks for explaining! And congrats on your win :-)

Video solution to Div2 Problem 2 here: https://www.youtube.com/watch?v=WG7RguNSNC8

What is the corner case for div2 500? I see many people (including me) failed system tests.

4 indian members get sponsorship for hello india programming camp (2 Div1, 2 Div2 (Logic TC??))

This fag probably 2nd div2 top, registered account like 15 mins before start

Well played!

We wanted to give a chance to the newbies too as the camp has three divisions of difficulty. Moreover, it is easy to verify 2 genuine coders out of the Div II list easily, their identity and information will be required for booking their bootcamp tickets. Also as per the rules, individuals are only allowed to have one account. If they create a new account, all of accounts may be suspended. Rest assured we will make sure deserving and genuine competitors get the chance

What makes you think that all people who are in div2 are newbies? The Indian guys who did well in div2 aren't. It's just that they don't take part in SRMs. I know in the end it's your wish, but it doesn't sound fair at all.

How to solve div1-800?

If I understand correctly, the problem can be reduced to the following (which, I believe, should be easier):

Given up to 100 positive integers (each up to 10

^{18}), you can replace value at positioniwithXORof some values from its prefix (we have to includea[i] into XOR, and can decide separately for each ofa[0]..a[i- 1] whether to include it or not), find LIS.However, I haven't found a way to solve this [hopefully correctly] reduced version.

The key subtask is: given numbers

x,b, and a set of numbersy_{i}, what is the smallest number of formxxor (xor of some subset of {y_{i}}) that is ≥b?If we solve that one, we can apply it inside the standard DP to find the LIS.

And to solve the subtask, we iterate over which bit will be the first difference with

b, and then we have a subtask: a set of numbersy_{i}, find a xor of its subset with certain higher-order bits and the remaining bits as low as possible. This is essentially solving a system of equations in Z/2Z, so we use Gaussian elimination in the right order (from higher bits to lower bits).My screencast with commentary: https://youtu.be/Ugf5kbxmV_8

In div 2 — 800 points. I don't understand why the result of {2, 2} is 3.0. Can anyone tell me about the way to caculate the result.

For Div1 Medium, is there a proof that it is sufficient to use only cells on edges?

Yes, actually the proof is not so hard.

Suppose that there is a valid path, .

v_{i}is the coordinate of where the frog is oni-th step. Note that the placev_{2},v_{3}, ...,v_{k - 1}is not necessarily on edge of the square.Let's think about "modifying" the path with following way, that it remains still valid, and the length of path is same or improved.

Look at the following picture: This represents two cases (left one is case #1, and right is #2).

The first case is that "x and y is both increasing or decreasing". In this case, you can compress the path, from , to . If you do this, the number of vertices decrease by one, and also the distance remains greater than or equal to

d.The second case is the other pattern. Without loss of generality (because you can rotate arbitrarily), suppose that the y-coordinate of

v_{x + 1}is greater thanv_{x}one andv_{x + 2}one. In this case, if you change the y-coordinate ofv_{x + 1}inton- 1, obviously the distance will increase or stay equal so distance remains greater than or equal tod, and obviously the number of vertices doesn't change.If you repeat the process until no change occurs for any

x,v_{2},v_{3}, ...,v_{k - 1}will be on the edge of the square. Proved.Thank you for your clear explanation! I noticed that I tried to prove the following statement instead:

If

x→y→zis a valid path, there exists a celly' on edges such thatx→y' →zis a valid path.Thus I could't think of a shortcut in the left case.

By the way, the statement above is correct. It seems important here that the given board is square-shaped.

Is there any editorial of problem div 2 — 800 points?