Всем привет!
Завтра Сегодня в 20:00 MSK состоится Topcoder SRM 643
Предлагаю обсудить задачи после контеста!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2024 12:53:55 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
Какой стартовый рейтинг на TC?
1200
Спасибо
I deleted my blog, so people do not get confuse. We will do discussion here. Thanks.
Какой у тебя хэндл на топкодер?
Зеленый)
chromeCr, судя по всему.
Странно как-то, только 1100 зарегистрированных. Всегда так мало на TC раундах?
Как можно проследить, ТС в последнее время ощутимо теряет популярность.
Интересно, с чем это связано?
А что, серьезно в SRM 641 было 0 участников? О_о
Div1 medium greedy? How to solve it?
P.S. Answer after the contest will finish.
I solved with DP. I think most, if not all of the greedy solution will fail.
I believe that greedy might work. But I may be wrong.
UPD: It passed.
You only need the "vertical or" operations on "HS" or "SH", because either horizontal operation can be replaced by one "vertical or" without changing the result.
I have a reduction to the "vertical or" operation only: if "HH" is adjacent to "SS", then it's optimal to "or" the "SS" with this "HH", if there's just "HS" or "SH" adjacent to a row of "SS"-s, then we can copy the column with H from either end without changing the answer. That's because each "SS" requires an operation of its own (so the first case is clearly optimal) and a "HS" or "SH" will be converted to "HH" in a "vertical or" operation, which the resulting row of "HS"/"SH" can be made part of. That also gets rid of "SS" columns.
The best course of action at this point isn't greedy, but DP, because it requires practically no thinking. For example, dp[k][i][j] tells you the smallest number of operations needed to convert states[k][i,j) into all "H"-s. The only interesting operations are "dp[k][i][j]+1->dp[1-k][i][j]" and "dp[k][i][l]+dp[k][l][j]->dp[k][i][j]" ("vertical or" operation and merging 2 substrings). In case you ask why I couldn't solve the problem this way, I'll let this pic say it:
what is the "vertical or" operation?
"H" is 1, "S" is 0 (that's why it's or-ing); it's operation 2, since each pair gets or'd vertically; the other 2 horizontal operations can be viewed as one "horizontal or" where we can pick subseequences instead of substrings, and X->Y means Y =min(Y,X) in this case (transition from state X to state Y, use common sense for what operation needs to be done with their values). Of course, we don't need to turn "H" into "S" at all.
What is the k in your state?
I solved it greedy:
First eliminate every index where there is S in top and bottom row by expanding adjacent indexes which have a H with the third operator. It doesn't matter from which side you expand the non SS area.
Then forget every index which have H in top and bottom, and iterate over array and maintain the state HS or SH and count how many times state of HS turns into SH or SH turns into HS while iterating. Now there are count+1 areas. We can use operator 2 in every other of the areas and then use operator 2 into whole array.
Im sure this div1 round has the record for most hacks
What is Div2 1000 ptr solution?
Such a hacky round!
Anyone know how to check the test cases which I got challenged?
You can do after competition is over on Topcoder site by clicking on your last match in profile and clicking on details before that I don't think you could.
ic. thanks.
My first DIV2-1000 passed :D ( but the other 2 failed :D)
Some good challenge cases:
885909753408416474 {2, 999999751}
The complete factorization is 2 * 442954987 * 999999751.
Another common mistake was thinking that you needed to check up to 10^5 instead of 10^6 (cube root of 10^18).
{"SHHHSHHHSHHHS", "HSSSSSSSSSSSH"}
Expected output: 4
Hs on top talk to bottom, fix Ss on bottom with more two moves, bottom talks to top.
Another common mistake in d1 250 was to iterate up to N^1/2 after dividing N by all given primes, which is slow for cases N = 2*P, P — huge prime.
Why it is possible to iterate until 10^7 and get all dividers?
Actually, it's enough to iterate until 106 = (1018)1 / 3. After you do this, you'll get all divisors except the ones which are greater than N1 / 3. Obviously, there can be at most 2 such divisors and they will be on adjacent positions in the sorted primes list. The last observation implies that one of these two divisors will be given to us as a hint, thus we can easily find the second one in O(1).
only 1 prime u need find will exceed 10^6. so u can iterate until 10^6. and then if N still > 1 then N is one more prime.
Actually 10^6 is enought for that. The reason is in the fact that there cannot be more than 2 divisors that are greater than 10^6.
If there is one such divisor — it either will be in the given list, or will be left after all the divisions.
In case there are two such divisors, they will be next to each other in the list, so exactly one of them will be given to you. The second one will be left after all the divisions.
P. S. Too late.
Why should the cube root be considered?
What is the approach for Div 1 250 and how do you get to the solution?
Primes up to
can be found easily and so can the quotient after dividing by them as much as possible. There are at most 2 prime divisors (not necessarily distinct) greater than 
and the quotient we got is their product.
If there are 2 of them, we have to be told one (because they're the largest divisors) and finding the other is trivial.
Alternatively (and that's how I solved it): we have the time to check primes up to
, same for all given primes; if there's anything left, then we can't factorise it in time, so it has to be a prime :D
What is wrong with the practise room; "Run System Test" does not work...