| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Starts in few hours.
Date and Time : https://www.timeanddate.com/worldclock/fixedtime.html?msg=Topcoder%20SRM%20724&iso=20171128T1600&ah=2&am=0
Redoing this blog as it appears people liked it last time. (If there is someone from TC that prefers to post these kind of blogs, I will happily delete this).
Reminder: Registration closes in 45 minutes.
Why possibility to select reward has disappeared while registration still going?
Forget, it is present on registration page on arena.
I really like today's problems, is TC back?
Problems were good but not many participants even though SRMs at this time slot used to be most popular
How to solve Div2 1000 — point problem?
The contest was really tough. Div.1 250 pts solution?
a + b = (a|b) + (a&b)
Now that you have pairOr and pairAnd, note that you can check solution for each bit individually as they are independent. Now, do a dp[n][2] for each bit where dp[i][j] is whether there exists a prefix of length i ending at j. Check if dp[n][0] or dp[n][1] is true for each bit.
Another one solution: we can simply say a = (a|b) and find b = (a + b) - (a|b). Then if our a|b = a|b from data then ok else no
Wut? It works for n=1, but how does it work for bigger n's?
If a + b = (a|b)+(a&b) then b = (a + b)-(a|b) = (a&b) and a = (a|b). If (a&b)|(a|b) = (a|b) so we could use these a and b.
Can you explain your solution for these cases?
What means pairOr = {3, 3} ? Is it a|b = 3|3 or what?
pairOr and pairSum are bitwise OR and sum of adjacent numbers in the required sequence. (The arguments of function in original problem)
Can you please elaborate on it ?
When browsing codes to easy I wonder if people realize that (a&b) + (a|b) = a + b ;p
Btw, does anyone have a promising idea to hard? I got it passed using random but I am not satisfied with such approach. I thought about some kind of standard idea of determining lowest and biggest possible variance and if our goal is within allowed interval then making changes from solution with lowest variance to one with biggest and arguing that somewhere along this road we will encounter good answer, but I was not able to think of solution based on that.
But why (a&b) + (a|b) = a + b ?
And what about the carry value of (A+B)? For example, A == 10, B == 11, the result is longer that 2 digits, because of carry. How can you prove that (A&B) + (A|B) == A+B in that case, when some carry exists in the sum process?
a + b = Σ (ai + bi)2i
a|b = Σ max(ai, bi)2i
a&b = Σ min(ai, bi)2i
Here ai and bi are the ith bits.
And what about the carry value of (A+B)? For example, A == 10, B == 11, the result is longer that 2 digits, because of carry. How can you prove that (A&B) + (A|B) == A+B in that case, when some carry exists in the sum process?
10 + 11 = 0 + 1 + 10 + 10 = min(0, 1) + max(0, 1) + min(1, 1) * 10 + max(1, 1) * 10 = 0 + 1 + 10 + 10 = 101
Thanks a lot for the explanation! :))
There'll be a carry in the addition of corresponding max and min as well. The point is I have written the binary number in decimal form, so equality in base 10 implies equality in base 2.
Thanks a lot, I understand now! :)) great idea))
How to solve Div1 500?
First, one observation is that it is enough to do at most one of the moves {"left", "right"}, and at most one of the moves {"up", "down"}. There is no point to do both of the moves in one of the sets, so any reachable board would be reachable in at most two steps.
Let's say "left" is true if there exists a block that has a free cell on its left and false otherwise. (similarly, define "right', "up", and "down"). Intuitively, these are the moves which we shouldn't use, since we can't use these and get to our final configuration.
Then, we have the following cases:
1) If all of left, right, down, and up are true, then the answer is 1 (i.e. no moves are possible).
2) Let's say that both left/right are true (similarly for up/down). Then, we can't ever do left/right moves, so we can treat each column independently. Since one of up/down must be false (otherwise, we would be in case 1), then, we can just place the blocks anywhere in the column, as long as the number of such blocks matches. The number of ways to do this is just the binomial coefficient (n choose number of blocks in column). We take the product over all columns.
3) Now, without loss of generality, let's say left is false and up is false. Then, that means all blocks are in the upleft corner. For example, it may look like a shape like this:
There are two options: We either can do the moves "left" then "up" to get the blocks in the correct place, or we can do the moves "up" then "left".
For, "left", then "up", we can arrange the rows in an arbitrary order, then arrange the blocks within each row independently. The number of ways to arrange the rows is the multinomial coefficent (n choose a_0, a_1, ..., a_m), where a_i is the number of rows with exactly i blocks. The number of ways to arrange blocks within each row can be computed similarly to case (2).
Similary, we can do the same thing for "up" then "left" (using columns instead of rows).
However, we double counted the boards that can be solved with both types of moves. Luckily, that is just the number of ways to rearrange rows multiplied by the ways to rearrange columns. We can also use multinomial coefficients here in this case.
Is it me, or Web Arena has some issues with 64-bit integers in input in 250? For me, the 5th (1-based) sample is ["261208776456074180", ...], ["333333333333333300", ...] when I run it in the batch test panel, and produces other answer than expected. It was extremely confusing, but I decided to submit the solution anyway, and it passed.
Btw, don't know how it was for others, but for me it was pretty confusing that when coding hard my compiler was replacing every occurence of "??-" by "~" and I was getting this "~" on input :|. oldG=(-??, ?-?, ~, )
UnfinishedTournament.cpp:253:3: warning: trigraph ??- converted to ~ [-Wtrigraphs] "??-"};
The problems were really good.
Although I got 0 point, the round was interesting.
I wonder if there is a solution using deterministic algorithm to solve div 1 Hard?