→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
28:56:11
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
28:56:11
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 12:38:51 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
It will be my first topcoder round from a long time. I wish all good luck tomorrow.
Страные вы люди вам дали нормальную кодфорсу а вы на всяких непонятных сайтах задачки ищите....)))))) Нате вот порешайте если хочеться http://mirror.codeforces.com/problemset Или я чегото не знаю???
Div1 300 was repulsive and made this round a little boring.
Div1 300 was an okay DP. I didn't think it needed 300 points instead of 250, even.
Your reply does not make sense . I am not talking about the difficulty of the problem but that this problem did not have any 'nice idea' that topcoder problems usually have to make the coding part less painful.
The coding part wasn't painful, at least for me. And DP is a good enough idea for the easiest problem.
If you think having different experience and opinions is not making sense... oh well.
Btw, my idea was that we try all lengths of the first, second lucky number, and if we know the lengths, then DP = min. number achievable if we've filled in the last i digits of both lucky numbers and the i + 1-th digit of the sum from those digits is j (0 or 1). The limits are small, so a lot of things can be bruteforced.
Actually, you could speed up obvious 414 ( {4, 4}, {4, 7}, {7, 4}, {7, 7} for every position) bruteforce to 314 with observation that you don't need to check (7, 4) after you tried (4, 7), since it leads you to the same state of the backtracking. So we have a little observation/proof + easy code, which is quite TC style.
I actually coded this initially because the code was relatively short, but because I also had to brute force over the lengths of the two numbers it ended up running slightly too slowly, at least in Java.
My solution in Java has passed the test data. Actually, we have only two options for the bigger number's length. So it's runtime is roughly 14 * 28 * 314 = 1.8 * 109. Seems like it runs faster because of "if currentSum >= ans return" condition and trying to put lesser digits first.
I tried to generate all possible numbers as you said, This is my code.
some time's it gives TLE on some cases, and some times it returns wrong answer for other cases.
What is still missing ??
Can anyone (well, I guess there are 4 candidates) describe their solution to div1 hard?
There is a wrong solution, suggesting that the answer could not be more than 625. Egor convinced jury that it's possible to get more. Now there is no proof you can't get more than 861. And still a problem with 500. I got hacked on the test "5,5,5", "5,5,10", and my hack "1", "1" wasn't successful. :)
I can make anything up to 861, but cannot prove more is impossible
For Div2 900, I tried to find greedy solution as this:
1- generate all possible lucky numbers up to 1^15, which results in almost 65600 numbers.
2- for each number generated, try subtract it from the
notedigit by digit.3- if some digit in
noteis not a question mark then check if it is a possible summation of the corresponding digit with a '4' or a '7', if not then ignore this number and proceed to the next one4- if the digit is a question, I try to take the summation of the corresponding digit with 4 or 7 and replace the question mark with the first digit of the sum, and this way I am sure the resulted number is a summation of two lucky numbers.
of course I will minimize the resulted numbers each time.
is this approach correct ?
Any one ??
Yet another fail
At least this time I had same bugs as jury :)
Just wanted to say I am so excited that you are back to uploading screencasts! Now finally have a few more of yours and Petr's to watch!
"As it seems the D1 hard may not actually have a solution, D1 will be unrated (at least for now). Division 2 will still be rated, however."
Well, that's one more unrated match for me...
oh well, not much of a loss considering how little I solved.
is it settled that the round won't be rated ?
There are no results yet even for the medium problem. And no solution for hard.
I don't understand this decision to be honest. I'm looking if TopCoder has some official policy concerning unrating matches.
What's wrong in this solution for Div1 300?
I do not wish to dicuss problems. Go away.
I am surprised when i open the division summary and see tourist hasn't solved Div. 1 Hard. And a few minutes later comes an announcement: "It seems the D1 hard may not actually have a solution".
Tourist doesn't solve a problem -> Problem is unsolvable :P
I was thinking about Div1 Hard and assuming that favorite number is smaller or equal than 625 (exactly how it was supposed to be during the match; for values bigger than 625 the author expected to return an empty vector) is the following solution working? (I've implemented a tester and it seems so, but I'm still not sure) (SPOILERS):
Isn't this solution obvious and pretty simple, assuming it is correct? It seems actually too simple for a Div1 Hard :-D. What do you think? Thank you!
A construction similar to this was actually the intended solution and will always construct numbers 625 or less. The implementation is quite simple but the idea seemed hard to think about or not super obvious to try. I actually proposed the problem as a d1medium but we decided it worked better as d1hard.
To make the problem work I had a bounding proof to show that you cannot form a construction with over 625 paths. (Most of the difficulty of the problem was proving/convincing yourself more was not possible) Unfortunately, proofs can have bugs. :( My proof had a subtle error in it and as we see with Egor's solution, trees with larger number of paths can be constructed.
The proof is not a total wash though; you can fix my proof to bound the number of balanced paths that start with weight 4 and end with weight 7. If I had noticed the mistake earlier, this would have been an easy fix to save the problem. (Add the additional requirement that such paths must start with 4 and end with 7)
If anyone is interested in the details of my bounding proof, I'd be happy to spend some time posting on my bounding method and the stupid mistake I made in the original proof.
I tried to form a new upper bound for the stated version of the problem but haven't found any bounding that result's in an upper bound close to Egor's construction. :( I also don't have a construction that forms more paths.
Many things went wrong during the preparations of this round. (Resulting in the errors for the d1medium and the removal of the original d1easy and replacing it with the d2hard) The result of the SRM was very sad to me because I liked the ideas for the d1 problems but everything seemed to fall apart during testing. :( The thing that seemed the most stable after testing was the d1hard because we had a straightforward bounding proof and the solution was simple. Sadly, even that problem had an issue.
Why TC doesn't want to post correct results for Div1 on the website?
Are the tests for Div1 Medium correct in practice room?