Всем привет!
Мы рады пригласить вас поучаствовать в раунде #86. Авторами раунда являются Андрей Малевич (aka Kenny_HORROR) и я, Тарас Бжезинский. Мы оба студенты 4 курса Белорусского Государственного Университета. Благодарим MikeMirzayanov , it4.kp , RAD , Gerald и Fefer_Ivan за помощь и советы в подготовке задач и Delinur за перевод.
На раунде вы вспомните вместе с мальчиком Петей его школьные дни и поможете решить ему некоторые задачи.
Раунд будет проводиться для обоих дивизионов, разбалловка задач будет стандартной(500 - 1000 - 1500 - 2000 - 2500).
Во время проведения раунда новый сервис "Виртуальный турнир" будет отключен по причине своей возможной нестабильности.
Всем удачи и высокого рейтинга!
UPD
Контест завершен, рейтинги пересчитаны.
Победители:
DIV1:
1) hos.lyric
2) KADR
3) yaro
4) tourist
5) Egor
DIV2:
2) kelvinlau
3) igor_kz
4) lxn
5) StelZ40494
Доступен разбор, к ночи появятся остальные задачи.
Огромный плюс автору автору сегодняшних задач, если после контеста не найдется никого, у кого "в А где-то была опечатка, а систесты прошло".
Пытаюсь отправить задачу на Java, мне вылазит сообщение
"Исходный код должен удовлетворять регулярному выражению [^{}]*public\s+class\s+(\w+).*"
Что делать?
Контест завершен, можно обсуждать.
Ну что ж, кто как делал С, есть варианты, кроме прекалк+теорема Ферма?
Храним ответы с определенным шагом, остальное досчитываем вручную.
По ТЛ вроде бы заходит. Главное, чтоб багов не было:)
У меня шаг 100000.
"You may resubmit the solution at any moment, but it may reduce your score. It happens if resubmission is successful (i.e. passes all the pretests + previous hacking attempts). In this case, the previous successful attempt would be considered as a reason for penalty"
So has this rule changed?
Впрочем, теперь буду знать.
мало у кого такое зайдет)
ну у меня всего 1 взлом на этом, но должно ловить итерирование
Наконец-то разобрался: все было написано правильно, но эргодические цепи - это сильно связные по ненулевым ребрам.
All prime numbers of the form 4n+1 qualify for it(and 2 also) .But I was getting Time limit exceeded!!!
bool is_prime(int n)
{ for(int c=2;c*c<=n;c++) if(n%c==0) return false; return true; }
If yes, it's slower than calculate alls numbers prime, no?
vector<int> list_prims;
void precompute(int n)
{
list_prims.push_back(2);
for(int c=3;c<=n;c+=2)
{
for(int c2=0;c2<list_prims.size();c2++)
if(c%list_prims[c2]==0) goto end;
list_prims.push_back(c);
end:;
}
}
I don't know if what I said it's stupid, I have not calculated the complexity of the second fonction. But more we have a big number n, more there is space between two number prime...
Ps: I have Time limit Error for the pretest 4, so it seems to not be the good solution.
Upd. Вначале строил матрицу размера (22^2)на(22^2), но т.к. она довольно большая, то получалось засунуть слишком мало итераций, но использовав фичу, что нам нужна неупорядоченная пара вершин, сократил ее размер до 243на243, что уже позволило впихнуть 80 итераций, надеюсь, что хватит.
I guess my opinion right now can't be really true, as I did really bad :-/
P.S. Когда начнется тестирование?
01:10:58 Решение взломано участником AndrewLazarev
So, a sentence with just one word which is a verb should give "NO", isn't ? I'm missing something from statement. Could some one point out that. Thanks.
Hope, proper steps will be taken :)
Во многом согласен.
Хотя в целом - было интересно. Главное - что не было явных фейлов с задачами (вроде "авторское не учитывает...").
Первая - пока писал ее, обматерил соседей по комнате, автора задачи и весь АСМ вообще. Но когда написал - получилось довольно просто и красиво, хотя и много по коду:) На финалах ведь тоже бывают задачи на скучную реализацию?..
Вторая - а она вообще решается строго правильным алгоритмом в пределах ТЛ? В моем понимании, при
таком ТЛтаких ограничениях на вид инпута почти нереально подобрать параметры хеша, которые не будут заваливаться хоть одним теоретически возможным тестом. Другое дело, что все такие тесты перебрать нереально (хватает нам уже 360 тестов по первой).Третья - прекалк есть прекалк... Немного не в АСМ-стиле, но бывают и такие. Ведь решаема и не прекалком, просто труднее. Мне не понравилась разве что тем, что у меня на диске С было 2.5 гб свободной памяти, в результате после выполнения жестоко неоптимального прекалка ноут сильно повешался, надо бы сейчас перезагрузить.
Проблема видимо в том, что один взлом так и не засчитали.
Про A и C тоже согласен...
В общем, сумел сдать только когда считал отдельно для разных длин строк. Хотя, с другой стороны, хорошо, что авторы меня к этому приучили...
У меня двойной хеш из двух интов свалился по памяти (первая посылка в дорешке), почему же один long тогда проходит?
What do you think about Prob C DIV1. ?
I see some people hard-coded primes in the intervals of 10^6 or so .
My AC code from practice http://ideone.com/hMmmm
Edit: hmmmm :p
Can some give a rough idea on how to still reduce space ( if at all we can ).
Thanks.
Case (heh) in point:
Test: #10, time: 4510 ms., memory: 96140 KB, exit code: 0, checker exit code: 0, verdict: OK
Input
100 152262461
Output
4281819
Answer
4281819
Test: #11, time: 4720 ms., memory: 96140 KB, exit code: 0, checker exit code: 0, verdict: OK
Input
200 299399868
Output
8110312
Answer
8110312
Test: #12, time: 5000 ms., memory: 96140 KB, exit code: 0, checker exit code: 0, verdict: TIME_LIMIT_EXCEEDED
Input
300 99050033
Output
2854733
Answer
I would not go that far but, to be honest, I haven't seen a code optimization problem in a contest in a while (meaning, there hasn't been a need to reduce the constant factor).
I did remember seeing Yarin's Sieve a while ago, but I never really had use for it - this time I googled for it and implemented it in Java. For other's benefit, here it is (my code passes if I inline the calls to isPrime(), which is a shame):
[code]
/*
* Convert Yarin's Sieve to Java... bleh :)
*/
private static final int MAXSIEVE = 300000000;
private static final int MAXSIEVEHALF = MAXSIEVE / 2;
private static final int MAXSQRT = (int) (Math.sqrt(MAXSIEVE) / 2);
private byte[] a = new byte[MAXSIEVE / 16 + 2];
private void init() {
Arrays.fill(a, (byte) 0xFF);
a[0] = (byte) 0xFE;
for (int i = 1; i < MAXSQRT; i++)
if ((a[i >> 3] & (1 << (i & 7))) != 0)
for (int j = i + i + i + 1; j < MAXSIEVEHALF; j += i + i + 1)
a[j >> 3] &= ~(1 << (j & 7));
}
private boolean isPrime(int n) {
return (a[n >> 4] & (1 << ((n >> 1) & 7))) != 0;
}
[/code]
waiting for editorial to see the non-hashing solution for Petr#.
I thought to myself..at 1:30(hh:mm) before end of contest."ahh..sieve...surely it will TLE " ......
Again at 1:00(hh:mm) ..."yeah..sieve must TLE ...the limits are very high ... "
Again at 0:30 ..." n^(1+k) must time out [0 < k < 1]" ...
But when I see AC solutions they used sieve only... :(
Just optimizing the sieve can also do the trick.
I get Time Limit on test 21 !!! and my solution is O(n^2) !!
Did anybody has this problem too?
p.s. why does n^2 gets time limit ?
В D оказывается, если в умножении матрицы после вычисления очередного элемента ответа написать строчку вроде
if (res[i][j] < 1e-30) res[i][j] = 0.0;
то программа начинает работать в несколько раз быстрее, хотя операций делает столько же.
Кстати, по поводу В. Говорят тут все - сет падет по тл, даже без него впритык.... Думал, у меня где то 1+ время выполнения.
Теперь посмотрел.
У меня решение работает за 0.2 секунды. При том, что там cin, вектора (которые лучше все же заменить на массивы...), и еще много неоптимальных вещей, на которых еще пару сотых теряется.
Так что... Если написали весьма неоптимальную ерунду - нечего жаловаться. У меня тоже первое решение строки сравнивало по определению - оно на моем ноуте работало секунд 40. На СФ может быстрее, но явно не 2 секунды. Я ведь не жалуюсь, что такое дает ТЛ.
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(something)
s.insert(f[i][j]);
Падало вот такое. Тут всего n^2 вставок в сет.
I used usual polynomial hash,
H(S) = (s1 + s2 * p + ... + sn * pn - 1) modQ, where
p = 31, Q = 263 - 1.
Кто подкинет идею в чем может быть дело?
It seems that I discovered a serious bug in Codeforces. . . . .
Submission judged with MLE:const int N = 3e8+5;
Submission judged with AC:const int N = 3e8+5;
I suppose the authors intend not to accept a solution with O(N) memory. . . . right?May you please explain a bit more on why the memory of a bool vector can be less than a vector of bool? Just wanna learn something.
With bool [] , 148000kb.
and with vector<bool> the memory usage shows 2700 kb.
The difference is more than 8 times.
Can u explain the memory difference please.
Странный раунд, получилось так, что, решив всего одну самую лёгкую задачу, сильно прибавил в рейтинге. Кстати, самому понравилось, как её решил - переводил слово в пару "часть речи - род" и запихивал в вектор. Ну а дальше одним пробегом проверял на одинаковость рода, а другим - оставшуюся часть задачи. Тем самым избежал проблем.
Зато в задаче B отхватил их сполна - сначала строил по строкам префикс-функции, потом по их значениям определял строки... Затем увидел, что нужно найти количество без повторов - попытался как-то поддерживать текущую строку во вложенных циклах, использовал мап и метод удаления символов из строки. Раз 6 посылал с ошибками, но под конец всё-таки добил претесты. И уже после завершения контеста пришёл вердикт взлома Егором :)
Кстати, поздравляю его с неплохим результатом.
Ну и к авторам пару предложений:
1) Наверное, тесты для задач B должны быть более широкими, чтобы уж решения с одной асимптотикой проходили хотя бы.
2) Может, уже пора остановиться в написании условий про мальчика Петю и счастливые числа? :) Уже приелось, как мне кажется, хотя не столь важно.
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(something)
s.insert(f[i][j]);
Падало вот такое. Тут всего n^2 вставок в сет.
note like this in A-Div1 , C-Div2 very important it should be in bold font. too many Div1 and Div2 coders get WA @pretest 4.
my code for problem A:
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
// freopen("sam.txt","r",stdin);
int k,l,i;
cin>>k>>l;
for(i=1;;i++){
int temp=pow(k,i);
if(temp==l){
cout<<"YES"<<endl<<i-1<<endl;
return 0;
}
if(temp>l)break;
}
cout<<"NO"<<endl;
return 0;
}
long long temp=pow(k,i)+0.5;
you should have tried abs(n-floor(n)) < eps || abs(n-ceil(n)) < eps just to be sure.
but for problems like this i always follow KISS rule! Keep It Simple Stupid.
i just used this:
while(n%k==0) n/=k;
10^4? Маловато, наверное, т.к. сорслимит в 64 кб... При 30000 промежуточных ответов... Запихивать каждый ответ в 2 символа - не представляю пока, как.
Следовательно, минимальный шаг надо немного поднять.