Совсем скоро стартует новый сезон командного студенческого чемпионата ACM-ICPC. Например, регистрация на Южный (Саратовский) Четвертьфинал уже открыта. Уверен, среди участников соревнований Codeforces полно тех, кто будет участвовать в ACM-ICPC в этом году.
Чтобы не было мучительно больно за бесцельно прожитые годы, мы открываем серию еженедельных тренировок на Codeforces. Конечно, они будут проходить в рамках Codeforces::Тренировки. Приглашаются все желающие!
Время старта тренировок — примерно 16:10 еженедельно по средам (московское время). В качестве тренировок будут использованы задачи различных соревнований прошлых лет. В дополнение к здравому смыслу несколько простых правил:
- Мы не будем публиковать до старта тренировки источник задач, прошу решать задачи честно и самостоятельно. В случае использования чужих решений или какого-то другого чита – будем дисквалифицировать. Не хотите тренироваться сами – не тренируйтесь, а портить тренировки другим нельзя.
- Давайте не будем обсуждать задачи до окончания тренировки.
- Мы редко будем давать ответы на вопросы по задачам. Если вы нашли какой-то явный баг, то дайте нам знать — исправим, сделаем рассылку с информацией о правке.
- Если у вас есть тренерский аккаунт (и вы не участник тренировок), то будем рады помощи.
- Регистрируйтесь на тренировку вашим актуальным составом тех членов команды, кто участвует в ней.
- Иногда я буду просить кого-то из жюри прошедших соревнований или тренеров других вузов помочь с подготовкой или поделиться материалами – надеюсь на ваше понимание и помощь!
- Если вы уже решали эти задачи, то либо переключитесь на другую тренировку, либо сообщите об этом через форму вопросов по задачам и вас переведут на внеконкурсное участие.
Первая тренировка 2013-2014 CT S01E01: Extended 2000 ACM-ICPC East Central North America Regional Contest (ECNA 2000) состоится 11-го сентября, примерно в 16:10.
А почему не по субботам или воскресеньям? Люди работают же.
Конечно, можно писать виртуально, но вроде бы интереснее, когда пишут все в одно время.
Именно в среду будут происходить тренировки всех саратовских команд, этот день, как выяснилось, наиболее подходит всем командам. Думаю, исходя из этого тренировки и сделаны в среду.
Неужели в Саратове никто не работает?
пока ты работаешь... враг качается! )
Из тех, кто тренируется для участия в ACM-ICPC — практически никто.
В воскресенье обычно проходят этапы Открытого Кубка, по субботам тоже часто бывают различные соревнования.
По воскресеньям будут кубки, по субботам тоже много других контестов бывает. Кроме того, не забывайте, что в выходные мы иногда хотим иметь выходные :) Для моего расписания и расписания студентов СГУ: среда — наиболее подходящий день из оставшихся.
Идея хорошая. Но поставить первую тренировку ровно на десять минут позже времени окончания четвертьфиналов в Украине — забавно =)
this contests would be really useful. thanks for this.
If there is good amount of participation, try to increase frequency of contests.
Are the problems original or from past regionals?
Sorry, I didn't read the announcement carefully. They are from past regionals.
А когда будет? На http://contest.sgu.ru/ пока пусто
Как я понимаю, условия задач будет даны на английском языке?
Great work !
what will be the difficulty of the problem set in comparison with Codeforces's regular contest ??
It depends on a contest. I hope in most cases it will be interesting for the wide range of participants.
Will these be rated in any way?
Contests at GYM are not rated.
Thanx a lot... We were really waiting for this wonderful oppurtunity... :)
I know you guys probably know, but,
This is awesome. round of cheers
Задачи будут только на английском? А то школьники тоже бы могли присоединиться к этим тренировкам (в рамках подготовки к ВКОШП).
Скорее только на английском. Качественные переводы текстов — большая работа. А учиться читать английский полезно и школьникам.
Can I participate in the Pratice without team?
Yes
looks like a good training for icpc…
No , contests at GYM are unrated !
Had you seen this !?
Очень тормозит полигон, вылогинивает каждую минуту. Не из-за грядущей тренировки?
This should be really helpful. Thanks a lot!
how many episodes are in a season ?:D
how can i participate to this contest when i click contest area threre is no contest availble.
re i found it :D it was in the gym section
Will the editorial of these problems be published after the contest?
I doubt it... editorials aren't normally published for gym trainings. But you can try googling the contest that the problems are taken from, there should be an analysis or something...
When can we get to see the test cases?
Tests and other's solutions are available if you solved the problem.
How does one view the test cases? They're not below the source code even for problems I have solved.
You can get test cases of problem in GYM only when your max rating is greater than 2200 (When you become Grandmaster).
Did anyone get javascript alert box when announcement came? Somehow i didn't get it and it cost me problem B. I thought long means 64bit, at least in my compiler it is 64bit.
Edit: What is the best way to solve B? I've pre-generated all the k-gon numbers and searched in them, runtime is not good.
My solution: we store one polygonal number for every "index", in a heap, starting with the smallest ones ≥ s (we can binary search or bruteforce those). Along with the value in the heap, we remember the "index" and order (as in "this is the k-th smallest") of the polygonal number, so we can easily increment it — change it to the k+1-th smallest.
Now, we keep looking at the 2 smallest entries in the heap; if they're equal, we have one of the numbers we need — take out of the heap all the entries with value equal to that, print them, increment and return them to the heap. So the time complexity, if x = how many polygonal numbers are ≤ the largest one we print, is
per test case.
Why should this work? We have guarantee that the largest number we print, L, is at most 232; polygonal numbers grow quadratically (and with large constant for large indices), so it's
. For small n, that's enough. For large n, we find out that L is much smaller than 232, because there are quite a lot of chances for poly-poly numbers to occur if we have many polygonal numbers to choose from. So the constants play in our favor if we cut down our searches to the range we need :D
Surely you notices how many polygonal numbers there are in total for indices ≤ k:
. Despite the good constants for large indices, those are too many if there's a log-factor or bad constant added. Maybe you could make such an idea pass the tests, but it must be hard.
"We have guarantee that the largest number we print, L, is at most 2^32" But in the question it was mentioned that the solution that we will print will fit in long. Then how the 2^32 assumption ? Any intuition would help
It's a 32-bit "long" (the one in C++, not Java). That's at most 2^32.
C++ long is 64bit too, at least in modern compilers. I am using g++ 4.7.2 , before writing the solution i wrote following lines to check
This works fine,no overflow. So i obviously assumed problem setters meant 64bit. I saw the announcement when there was 6-7 minutes left, so i couldn't finish coding.
C++'s
long intis only guaranteed to hold values up to 231 - 1. Also, on many modern platforms it is 32-bit.Is each episode about a particular topic or like regular contests there are questions from different topics in each episode?
Is it possible to see contestants' solutions?
Not before you solve the problem yourself. But Egor posted his solutions in this comment, if that helps.