Всем привет.
Автором задач сегодняшнего раунда являюсь я. Раунд будет проходить в двух дивизионах. В каждом дивизионе будет предложено по пять задач. Это мой второй раунд на Codeforces. Персонажами в задачах, как и на прошлом раунде, будут моржи =)
По традиции выражаю огромную благодарность команде Codeforces и Alias за помощь в подготовке контеста.
Желаю всем успеха и пусть победит сильнейший!
UPD1:
Разбаловка задач для div1: 500-1000-1500-2500-2500
Разбаловка задач для div2: 500-1000-1500-2000-2500
UPD2:
Победитель в div1: SergeiRogulenko
Победитель в div2: piotr.mikulski
Мои поздравления!
Ну и небольшая шутка юмора в в виде бонуса-картинки =)
Чего не сделешь, чтобы повысить вклад........
Codeforces Beta Round #64
By Connector, 3 months ago
if you wan't to see the problems by the same auther click here
505785
Я на самом деле извращенец, ты это правильно подметил.
Просто периодически возникает желание писать всё вручную не пользуясь библиотеками.
То есть если хочется поделиться решением то лучше сторонние сайты использовать, ога?
Только если через таблицу соревнования снизу в дорешке искать ник пользователя и там для каждой задачи смотреть.
Вот два предложения с reformal по поводу этого (да-да! ненавистники reformal и daftcoder'а могут начинать минусовать меня тут). Они достаточно высоко (5 и 6 место) и ближайшем будущем наверное можно ожидать появления этих фич.
Спасибо, Наталья.
UPD. кому-то не нравится daftcoder с его sqrt-декомпозицией. xD
Вот мой исходник например.
Добавляешь элементы с начала очереди , для каждого поддерева хранишь максимально дальний элемент. Сплитишь дерево по ключу очередного элемента и получаешь дерево элементов строго меньших текущего, после чего вытаскиваешь ответ на запрос.
upd: Получается тупое моделирование . Ну и не забываем склеивать потом обратно
UPD. Спасибо за перезагрузку. Полное решение. Эх, я был близок...
Спасибо автору за контест:)
After I locked C problem. Trying to hack my solution, and my solution got TLE. And I using that test and hacked 5 other coder`s solution. (Therefore test is suitable)
But my solution is accepted in final test.
mesto=v[c][0]+1
и
mesto=*it+1
Так должно быть.
Я написал ваш вариант сначала, и получил WA на претесте.
И зачем использовать массивы чаров, когда есть string? И с cin/cout все задачи нормально заходят.
Правда, все равно, здравствуй, div-2 :(
Офигеть, с одной поздней задачей, в третьей сотне, и всего-то -67 рейтингаЯ для каждой буквы для каждой позиции первого слова посчитал позицию первой следующей после нее такой буквы... А дальше просто "прыгал" по массиву, сохраняя текущий ответ и позицию. Если после данной позиции нужной нам буквы больше нету, то возвращаемся к началу слова (и +1 к ответу - "приписали слово еще раз").
А то, можно ли записать, проверяем просто - все ли буквы второго слова есть в первом.
Kind of guessed the answer in C and was pretty close in D.
I'm waiting for the editorial, especially for the proofs of C and D.
I am very suprised.In problem B,div2,I use string always got RE on pretest 2,but I use char got AC,why??whether it is relative to the head files,I type #include<string.h> and #include <string>
Thanks for the contest! The problems were excellent, varied, the statements were very clear, and I'm very curious about the problems that I didn't solve, which is the way it should be :)
BTW, I thought that more people would implement a brute-force approach in Div1 A (maybe they did in Div2 C). It looked like a good hack target but I only managed to find three slow solutions in my room.
Waiting for the editorial :)
Anyway, learning is always happy:)
Вот например у adry за последнее место в диве 2, рейтинг упал только на 69 пунктов, у durt за последнее место в диве1, рейтинг упал на 70 пунктов. Как-то странно это.
Вот, кажется, основная причина.
Тему эту уже подняли в прямой эфир.
Заметил, ты был на грани
208 daftcoder 1150
Hacks: +6 / -3
A: -1
B: 700 - 01:15
Затем долго думал как же лучше написать B, придумал, и ещё решил поломать непонятное мне, но как оказалось правильное решение. :-)
А вообще я пишу for fun. Rating, конечно, приятно, но это не главное, тем более для меня. :-)
А так иногда пачками беру задачи и решаю/отсылаю.
Ведь Div.2 C в нем совпадала с Div.1 A.
Т.е. решив только две задачи во втором дивизионе получается что в первом ты бы не решил ни одной? Тогда значит рано тебе туда, ведь заметь, там А решили почти все.
И вообще, здесь довольно высокий уровень первого дивизиона, кажется повыше чем на топкодере. Да еще и шкала рейтинга сильно растягивается и тяжело прогнозировать куда все это ведет.
потерялпотратил 25 минут, я могу бы дорешать (D - Div. 2, B - Div. 1)Does anyone know when is the next contest?
Hope it helps, sorry for bad English.
Thanks a lot!It's very kind of you.
I need clarification for problem E(div 2). Specially i m very much confused about the paragraph
"Let's consider the ski base as a non-empty set of roads that can be divided into one or more tracks so that exactly one track went along each road of the chosen set. Besides, each track can consist only of roads from the chosen set. Ski base doesn't have to be connected."
What is meant by this paragraph......................
By checking whether we can find b next-to where we found a , we can save 1 headline-expense. If b is not found next(next does not necessarily mean adjacant) to a . We will have to use another headline. So, then search the source string(that is the headline),from start for b. Doing this again and again will provide you how many headlines you need. But this is SO costly. Every time you will have to search for a character in O(n) time. So, you see, this is very costly , given such constraints. So, we use binary search. We binary search for the next position where the next character to be searched is located. Suppose a was found at 5th position, now we want to find b, nearer to 5th position but on the right side.
I have added few lines to understand what is going on on test case 2 of the example (abcd,dabc)....
forn(i, tn)
{
vi &v = pos[t[i] - 'a'];
// v[3]=3 for 'd'
int j = lower_bound(all(v), p) - v.begin();
// can't understand. have read about lower_bound.but how p=0 will find 3 in vector
printf("%d\t%d\n", j,p);
if (j >= sz(v))
cnt++, p = v[0] + 1;
else
p = v[j] + 1;
}
printf("%d\n", cnt);
and I got this as the output:
0 0
1 4
0 1
0 2
2
could you please explain me little bit more as I am unable to correlate the output to the input with the help of code?
1. If the target is "dabc" and source is "abcd", then after 'd' p=4, so for target: 'a': v[0]=0; then how p=4 in lower_bound will give j=1?
2. What I have learned from Top coder algorithm tutorial and recipes is that to use binary search there should be predicate which is true for some interval and false for other interval. so we continuously divide the search space until found the correct one. But in this case we are maintaining separate container for every alphabet in source and storing its position. then we are applying steps you mentioned but how this is binary search? How have we divided the search space?
Lastly could you refer me more problem like this for practice.
1. "how p=4 in lower_bound will give j=1?"
for case 'a', vector v[0]=0 has only 1 element whose index or position is 0, which is represented by j. but then how j is giving value 1?
All the vectors in this case are maintaining only single element then j must be 0 for all the cases. So why it is giving 1 in case of 'a'.
2. if (j >= sz(v)) cnt++, p = v[0] + 1;
this part of code is incrementing cnt or new headline and if p reaches end of the sorted values in vector then starting once again it from beginning. and
else
p = v[j] + 1;
this part is putting next value in sorted array of vector v in p.
So where are we dividing the search space? I suppose we are only iterating in the vector.
Likewise you mentioned in binary search we first search middle value then look at whether to search in [mid+1,high] or [low,mid+1], then further divide. but in this case how it is binary search.
D was a bit tricky. Spent lot of time in debugging.