Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:54:14
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:54:14
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 Round 451 (Div. 2)
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 03:40:47 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Is there any solution for F without using hashing/probabilistic approaches?
Big integer types
That should be TLE as it is O(n^2)
Well, you can get 100% right answer by brute-force checking after the hashes match, and that allows the hash to be wrong a few times, because then you still won't get a TL... ofc that still uses probabilities ;(
Yeah, that's indeed the actual (and almost never used) Rabin-Karp algorithm. First time that I used it (with the O(n) check each time hash collisions occurred).
We can delete some variants (if len1==len2 and len3=len1+1, then 1st digit in third number is to be 1, if len1==len2==len3 then first digit in first number + first digit in second nubmer is to be not bigger than first digit in third number and so on (look at my code to find more dependencies)). Then we should check the other situations. Just iterate in our strings (like long arithmetic) and try to get third number. If we can do it, just print the answer. I'm not sure, if this approach is good, but it can pass all the tests. Also I can't prove it, but it so obviously that too many combinations (len1, len2, len3) is not considered in this solution. This is my solution and sorry for my bad English.
How many people used 'exgcd' in 898B ? ...
I used it,but failed
After the contest I realized that I was thiking too much...
so do I...I though brute force will get TLE btw somenoe know how to solve by exgcd?
you can check my submission
Nice and clean code dude (y)
I used and got AC.
I exceed time limited at 40th test,,,,,,
+1
takes me quite a time to code...
me too.
I used and accepted the problem
For problem E. My code gives correct input on my system but wrong on codeforces. for 1st test case on my system it gives 2 as output. On server it's giving 0. http://mirror.codeforces.com/contest/898/submission/33309260
edit: It gives 2 on codechef as well.
you have declared "s" twice , and there can be more bugs in your code. on my machine it gives 0 as output
I understand that's a wrong practice but shouldn't change the output as the one inside main must be considered.
An alternative solution for E: let f(x) be the minimum number of operations needed to make x a square number, and let g(x) be the minimum number of operations needed to make x a non-square number. We can sort the input array a using the following comparator: a[i] <= a[j] if and only if f(a[i])-g(a[i]) <= f(a[j])-g(a[j]). Then, in the optimal solution, the first n/2 smallest numbers in the resulting order will be transformed to square numbers while the remaining n/2 largest numbers will be transformed into non-square numbers, so the result is (sum i=1 to n/2: f(a[i])) + (sum i=n/2+1 to n: g(a[i])) for the sorted (using mentioned above comparator) array a .
My solution here[submission:33309059] uses a greedy, sort for min distance to square, then claculate the first half as squares and the other as non-square sort for min distance for non-square and sum like before but in reversed order
the solution is the minimun of the two previous
Why E is so easy? :D
I wrote a pretty easy solution, but it gives WA on testcase 13? Plz can u tell me my mistake?- http://mirror.codeforces.com/contest/898/submission/33306957
Thanks in advance
In the first place you don't need double, they bring bugs. You can just put the sqrt into an integer. Then you see if the sqrt(a[i])*sqrt(a[i]) == a[i] it means that a[i] is a perfect square otherwise it's not.
Read my solution
Yeah, double can bring precision issues,but i took care of that by adding a safe offset of 0.01. Our idea was the same, so what is the bug in my code though?
you are right is the same idea but i can't fibd the bug
I wish I would have seen it during the contest. Spend the entire time trying to solve D but couldn't get it to pass. Lesson Learnt-Read all the problems atleast once during the contest
Same lesson learned
problem C. why is my output wrong for the first test case http://mirror.codeforces.com/contest/898/submission/33310053
my output :
2
ivan 100123
masha 100123
jury output:
2
masha 100123
ivan 100123
In the question it is mentioned that we can output in any arbitary order.
update: found the mistake .My code was printing an extra space in first line of the output .But i have a doubt like the judging code should have ignored such things ??
The Linked submission is marked as correct...?
srry my mistake copy pasted some other link. now it's ohk .
I think there is extra space after 2
Thank you so much Minhazul_Islam ,will be careful from now onwards but will the judging code check those extra spaces ??? ac code just removed the space after 2 link: http://mirror.codeforces.com/contest/898/submission/33320542
Can someone elaborate the solution of F? I am not very comfortable with hashing plus the language of the author is a bit rusty(sry).
Solution of D without set : Sliding window question :) Using Hashing :)
http://mirror.codeforces.com/contest/898/submission/33305287
Your hashing can be called identity hashing :D
33320897 I have used a list of a structure node to do the C-Phone Numbers problem. It is a clumsy method but I believe it will work for some test cases. It is running perfectly in my system but giving runtime error Exit code is -1073741819 in codeforces' ide. Could anyone help me out here?
Do not erase from the set inside the loop in case iterator pointing to undefined value after the change.
Why in problem E we need a long long?
Come on guys.. Problem E was actually the easiest one.. I know I should have read all the problems first but... E is just.. straight up bad(no offense).. it isn't suited to be an E question and this caused a lot of rating spikes...
I am not aware about the concept of hashing. I can not understand the solution to the problem F.
The editorial says, "At first we should calculate "hash" by big prime module from the given string, and the base must be equal to 10 because we work with numbers. We can use prime module about 1015, if we will use multiple of long longs by module with help of long doubles."
I don't understand this.
How to proof solution of problem D? Why just turn off current alarm is right?
Let's process from left to right. If we come to an alarm that would give us k alarms in the interval (i — m, i], then we must turn it off or there will be too many alarms in the interval. The only other option is to turn off alarms preemptively, that is, before we're forced to. But it is optimal to turn off alarms as late in the day as possible, because these will affect the most intervals in the future.
Can anyone please explain the solution idea for problem F and it's complexity. I have read the editorial several times, but can't understand it properly. Thanks in advance.
Does this help?
Can someone explain me_ 898F — Restoring the Expression_ .Could not understand a word in editorial.thanks in advance
Hello . My submission for 898F gives error on Test Case 19.
http://mirror.codeforces.com/contest/898/submission/33383748
I'm using the Hash Function, where I'm using 2 prime numbers as given in the array prim[], and I'm using base 10. What is the possible problem in my code. Please help.
Can someone please explain problem F ?
In F problem what are we trying to hash in the editorial?
I have solved problem 898F-Restoring the Expression just now and I want to share my idea for this problem with the community.
The key idea or observation for this problem is —
Let a+b=c. and length of a,b,c is x,y,z respectively. Then z-max(x,y) will always either 0 or 1. It means the maximum number between a and b must have length z or z-1 otherwise we can't obtain c by adding a and b.
After this observation now you can check for every possible length of c from 1 to n (where n is the length of the given input string) and from the length of c now you can calculate length of b and c and check whether the a+b=c property is present for the current substrings of the given string. Hashing is the only way to do this check in O(1) complexity. Overall complexity of this solution id O(n).
Here is my submission 33521860
Problem F I understand that the only way to compare it, it's using hashing. In fact, in the virtual contest, I thought about it. But the problem I've encountered was how to decided the size of the prime number. I thought about some very small prime numbers, see that it didn't work, and stop thinking about it. Is there any further explanation about hashing that could help me solve problems like this in the future? Maybe something with more theory, that helps me prove what I'm doing is right. Thanks in advance.
Please add this editorial to contest dashboard.