Технокубок 2017 — Отборочный Раунд 1

Добрый день.

15-го октября в 12:05 (московское время) стартует Отборочный Раунд 1 олимпиады для школьников Технокубок 2017. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке http://codeforces.net/contests/727. Не забудьте заранее зарегистрироваться на раунд. Впрочем, если забудете — не беда. Через 10 минут после старта будет открыта дополнительная регистрация для опоздавших (ее длительность — 20 минут).

Зарегистрироваться на Отборочный Раунд 1 →
Соревнование открыто для всех для неофициального участия.
Для неофиц. участников из второго дивизиона также будет пересчитан рейтинг.

Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:

Напоминаем, что регистрация на олимпиаду еще открыта. На кону — значительные квоты при поступлении в престижные технические вузы России и ценные призы. Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Второй отборочный раунд будет открыт для всех тех, кто не прошел в финальный этап из первого отборочного раунда. Причина (не участие или недостаточный результат) — не важна. Второй отборочный раунд состоится в ноябре.

Желаем удачи на олимпиаде,
MikeMirzayanov и команда Технокубка

UPD 1: Раунд будет являться рейтинговым соревнованием, то есть на основании его результатов будут пересчитаны рейтинги: официальных участников и неофициальных участников из второго дивизиона.

UPD 2: Если вас нет в списках http://codeforces.net/technocup2017/registrants, то вам необходимо в срочном порядке связаться с нами. Напишите нам на почту [email protected], и мы постараемся решить вашу проблему в самое ближайшее время.

UPD 3: Разбалловка 1000-1000-1500-1500-2500-3000.

UPD 4: Спасибо за участие! Надеемся, что вам понравились задачи. По результатам этого отборочного раунда в финал приглашаются лучшие 100 официальных участников. Следующая сотня попадает в резерв, из которой мы, возможно, доберем финалистов в случае отказов, расширения онсайт-площадки или слабых результатов следующих отборов. Рекомендуем и им продолжать участвовать в отборочных раундах — вас ждет еще два отборочных раунда.

2 (количество игр, верно?) 3 (длина каждый игры, верно?) приветizaron 5 (количество популярный игр) вет при рив етi ron ... (что угодно, включая nпр) 1 символ — п, второй — р и т.д.

include <bits/stdc++.h>

using namespace std; int main() { int n; cin >> n; int a[n]; int x,y,z; cout << "?" << " " << 1 << " " << 2; cout << flush; cin >> x; cout << "?" << " " << 2 << " " << 3; cout << flush; cin >> y;
cout << "?" << " " << 1 << " " << 3; cout << flush; cin >> z; int s=(x+y+z)/2; a[0]=s-y; a[1]=s-z; a[2]=s-x; for (int i=3;i<n;i++) { cout << "?" << " " << 1 << " " << i+1; cout << flush; cin >> a[i]; a[i]-=a[0]; } cout << "!" << " "; for (int i=0;i<n;i++) cout << a[i] << " "; cout << flush; }

Комментарии (157)

Показать архивные | Написать комментарий?

Adel_SaadEddin

8 лет назад, # |

+14

Would the problems be in English ?

→ Ответить

MikeMirzayanov

8 лет назад, # ^ |

+13

They will be in Russian and in English.

Ok,Thanks

zscoder

+93

3 Div.2 only Contests in 3 Days O_O

shahidul_brur

Bad luck for Bangladeshi contestants ! We will miss it, because we have ACM-ICPC Preliminary Contest starting at the same time (3:00 PM UTC+6) today! Missing a CF round is very painful to me. But wish to participate in this round virtually, as there is no alternative.

AlexandruValeanu

+16

I'm sure you will survive! ;)

FizzyDavicl

What will be the difficulty of the problems like?

demon1999

Рейтинги официальных участников из див.1 будут пересчитаны?

Sehnsucht

При регистрации неофициального участия выскакивает окошко с информацией, что рейтинг пересчитается у официальных участников (у всех) и у неофициальных участников только из Div2 (вероятно, из-за соответствующей сложности заданий?). Пока что официальных Div1 единицы http://codeforces.net/contestRegistrants/727?order=BY_RATING_DESC

Tiny

Almost missed this round since there was no notification yesterday. hope I won't do so bad at this very unusual time.

repeating

-21

unusual round with unusual time

khaledzag

-16

Rated ?

only for div2

bzh

I am new here.How much rating is div1/div2?

div2 ]-INF,1900[

div1 [1900,+INF[

Thanks.

Ninjo

Thanks

chessmaster

Там где логотипы организаторов перепутали названия двух универов. Вместо МГТУ пишет МФТИ, и наоборот при наведения мышки!

-17

Looks like there'll be no trivial problems : 1000-1000-1500-1500-2500-3000

allllekssssa

-22

I am really happy because we have so many rounds in few days. Thanks !

But when I saw in description of the task that is interactive + looked at inputs in the second and fourth problem, my wish for doing round dissapeared :(

LoveYayoi

I've got my D running on pretest 3 for about ten minutes

Can anybody tell me what's wrong with this?

gamezovladislav

← Rev. 2 →

+15

Всем привет :) Классные задачи)
скажите, что может быть в 3 претесте на D?

King

What was pretest 4 on problem B?

C137

I think something like:

a0.50a0.50

answer is just 1, you shouldn't print 1.00

I am sure this is not the pretest since my code accounts for this

MKopchev

Maybe a999.999b0.01c0.99?

This is not it either

SarvagyaAgarwal

for me , a case when answer is 1 not 1.00 worked for getting past test case 4 .

well, in this kind of problems you never know where the WA comes from :(

arnold518

how about a13.523.532.01b0.98c0.01

Diplomate

I got this pretest working after I changed int to long long. This stupid mistake took so much time and score from me...

Rudy1444

I did the same mistake and I didn't get blue because of that :C Well better luck next time :D

Sophie

← Rev. 3 →

+25

Problem B was unusually horrible ;[

Even #passed C is greater than #passed B...

+12

I Agree, but for some reason I thought it was easier than A and thus tried to solve it first.

stas.matskevich

Пытался загрузить задачи написанные на Pascal, но ресурс отказывается их принимать. Выдаёт либо ошибку в компиляции, либо ошибку на претестах. Два часа убито в пустую? Можно как-то исправить положение?

hloya_ygrt

Дело не в Pascal.

Выдает вам не "ошибку на претестах", а сообщает, что ваше решение вывело неверный ответ. То есть, правильный ответ на данный тест отличается от выведенного вами. Ошибка компиляции в вашем случае происходила из-за того, что вы отправляли паскаль-код на не тот компилятор.

Советую ознакомиться с этим

szawinis

Is D completely greedy?

areke

Yep!

Daniar

matching problem but can be solved greedy

N=1e5 so greedy is safer to code

gongy

<_< I stupidly forgot about the bound that preference will be adjacent sizes so I actually did max flow. You only need ~50 nodes for your max flow though, because you can group together people with the same preference specification.

I struggled for quite a time but still couldn't understand the greedy algorithm. I am more stupid as I didn't notice the "neighboring" constraint until reading you comment T_T

pimenta

How do we construct a network small enough for a flow algorithm to pass the time limit?

foundLoveOfMyLife

Problem E Pretest 5:Anti Hash?

creatnx

Do you pass this test:

3 1
aba
4
a
b
c
d

Seems like i have tendency to miss the statement given in bolds.

I dont know the answer to problem D. please tell me the approach. I thought it like putting shirts which are sure over and over again.

And after the contest I read prob F, and is it greedy???

green_frog

i used dp but did not code it

Sort the people by their tshirt choices sizes . Say you want to assign x "S" tshirts , you greedily assign them to people with only one choice . If you cant the answer is NO . Next assign tshirts to people with one of the choices as "S" . After that remove "S" from the choices of people who havent been assigned any tshirt yet . Similarly for other tshirt sizes .

eulerscheZahl

Problem D: assign T-shirts for participants with only one size first. Then sort the remaining participants by size, always try to give them a smaller T-shirt if possible, bigger one otherwise. If any of the counts for remaining T-shirts in negative, print "NO".

a sample code please?

&& and also is F greedy?

Sorry, I couldn't solve F.

My C# Code for D (as submitted, added some comments):

Code

using System;
using System.Linq;
using System.Collections.Generic;

class Solution
{
	static void Main(string[] args)
	{
		int[] nums = Console.ReadLine ().Split (' ').Select (int.Parse).ToArray ();
		int n = int.Parse (Console.ReadLine ());
		List<string> shirts = new List<string>(new string[] { "S", "M", "L", "XL", "XXL", "XXXL" });
		string[] take = new string[n];
		Dictionary<int, int> allow = new Dictionary<int, int> (); //participant number, index of smaller allowed t-shirt
		for (int i = 0; i < n; i++) {
			string str = Console.ReadLine ();
			if (!str.Contains (",")) { //only one t-shirt fits
				take [i] = str;
				nums [shirts.IndexOf (str)]--;
			} else { //two fitting t-shirts
				str = str.Substring (0, str.IndexOf (","));
				allow [i] = shirts.IndexOf (str);
			}
		}
		List<KeyValuePair<int, int>> myList = allow.ToList(); //sort participants by t-shirt size
		myList.Sort(
			delegate(KeyValuePair<int, int> pair1,
				KeyValuePair<int, int> pair2)
			{
				return pair1.Value.CompareTo(pair2.Value);
			}
		);

		foreach (KeyValuePair<int, int> pair in myList) { //for each participant with two sizes
			if (nums [pair.Value] > 0) { //try to assign smaller one
				nums [pair.Value]--;
				take [pair.Key] = shirts [pair.Value];
			} else { //assign bigger one
				if (pair.Value == 5) { //well, that should actually never happen
					Console.WriteLine ("NO");
					return;
				}
				nums [pair.Value + 1]--;//assign bigger one
				take [pair.Key] = shirts [pair.Value + 1];
			}
		}
		if (nums.Any (num => num < 0)) { //did I assign a t-shirt size more often than allowed?
			Console.WriteLine ("NO");
			return;
		}
		Console.WriteLine ("YES");
		foreach (string s in take)
			Console.WriteLine (s);
	}
}

Why is this correct?

assign T-shirts for participants with only one size first

You can't do anything wrong in this step, so it should be obvious, that this is correct.

Then sort the remaining participants by size, always try to give them a smaller T-shirt if possible, bigger one otherwise.

I should clarify, that I start with the contestants having the smallest size. So, if I have T-shirt S and M (one each), participants S/M and M/L, then I assign the S T-shirt to the S/M participant. If I would not do that, noone else would have use for the T-shirt. So, if I assign it in this step, I can't break anything. There might be some more participants with the same size, but not enough T-shirts of the lower size, so these get a larger one (if they wouldn't, there would be no way to give them any T-shirt). Now we have handled all participants with the smallest size. We can go one with the next bigger size, that works in the same way as the previous one.

If any of the counts for remaining T-shirts is negative, print "NO".

That means, that I assigned more T-shirts of a size than possible. That obvoisly doesn't work.

One could solve that problem with a max-flow algorithm too, but it would be quite overkill.

Well, that's good enough to me... Thanks!

One more question: how do we construct a flow network small enough to Edmonds-Karp fit the time limit?

The graph is actually quite small: you have vertices for each T-shirt size as well as each participant type (2*sizes-1 types here). Two more vertices (source and sink), that's all. The edges are the capacities (from source to participant: count of participants of that type, from t-shirt to sink: count of t-shirts). Numbers are random, change them depending on the testcase:

+21

I hate tasks like B . C and D were way easier . I wish I'd read D before B :(

abhishek_saini

-8

B took lot of time. F was not that hard either. I needed some more time for F.

gfn

How to solve E ?? without hashing

step_by_step

Aho–Corasick algorithm

can you please explain your approach ?

haleyk100198

I haven't coded it yet, but it should be something like this.

Build the aho-corasick tree.
Build an array, mark the possible "jumps" for each position. This can be done by searching the CD through the aho-corasick tree. (You can handle the name that goes cyclic by extending the string) Also check if it is possible to reach that position. For position i<k we will assume it is always possible, for others check if s[i-k] is possible.
Finally check if it is possible to reach s n*k+d . If yes, print the combination.

This should be O(n*k + g*k), which is guaranteed to be about O(1e6 to 1e7) and fits into the 4s TL easily.

UPD: My implementation: http://codeforces.net/contest/727/submission/21471422, remember to handle repated usage of a certain name.

Merln

Maybe Suffix-Array. Use Binary-Search to match all the names of the game to the string on the CD. Then find some positions which can make the string on the CD filled by these names.

vsp4

-6

I did that stupid mistake str.size() — 3 and leading to integer underflow issue.

But can anyone explain why this happens? is integer underflow also compiler dependent? o.O This code http://ideone.com/QU5GRm doesn't work as on ideone on my system?

I_will_win_a_div1_round

This is unsigned integer (not unsigned int though) overflow, meaning that it is defined. The thing is that string::size() is of type size_t which depends on the platform. On your computer it is stored in 64 bits, on ideone it is stored in 32 bits — http://stackoverflow.com/questions/1119370/where-do-i-find-the-definition-of-size-t.

Thanks i get it now. The value 184467440.. also overflows when assigned to (signed) long leading to negative value -1 in my system.

rhezo

str.size() returns an unsigned integer. Always use (int)str.size().

dush1729

This might help

Funny Bug

shubhamgoyal__

Approach for problem D?

http://codeforces.net/blog/entry/47759?#comment-320501

radoslav11

F hack test:

3 1 
-6 -3 -3 
6

Answer: 1

Glebodin

Добрый день, мое решение по задаче А в запуске работает правильно в Gnu G++ 5 и на моем компьютере!Прошу посмотреть мое решение еще раз!

Решение и в контест, и в запуск отправлялось под одним компилятором!

jwplaster.com2327

Посмотри ошибки в ЛК. Там указаны все выводы твои и правильные. Сравни)

Проблема в том,что перед отправкой я тестил почти такой же тест в запуске и он зашел! А на контесте не знаю почему, не зашел! Хотя я отправлял под одинаковыми компиляторами!

Any ideas why one could get WA50 on E?

masonsbro

Assuming you're using a hash-based solution, I think that test case makes a bunch of games' hashes collide, so that if you try to keep a map "hash -> game", it won't work: this would have to be a multimap, since several games can hash to the same value. To solve this problem, I used two different hash functions.

What's the intended complexity for F?

We have proven complexity $\text{[math]}$ and unproven O(m + n²).

anta

+24

Isn't my O(n² + m) DP trivial (and trivial to prove correctness)?

Maybe I'm missing something?

Edit: I have missed $\text{[math]}$ factor so the correct complexity of my implementation is $\text{[math]}$ . (integer sorting can be used to get O(n² + m) (under reasonable bounds of values and on a reasonable model), though).

+11

It is great. Please write it!

satyaki3794

dp(i, r) is the minimum possible non-negative value you can start with at position i and go till position n, removing at most r elements, such that the value never drops below 0. Complexity of this step is O(n^2).

For a given query b, you can use binary search on the number of elements r you need to remove, using dp(1, r). I have used 1-indexing. Complexity of this step is O(m*logn).

Total complexity is O(n^2 + m*logn).
Code

King_George

Using a greedy algorithm, the complexity will be O(n^2 * log n * log m), which also gets accepted. 21472657

+96

Rating changes for unofficial Div2 participants ?

Vinay_Goel_

Problem D: http://codeforces.net/contest/727/submission/21454057 when i run same code on my system i am getting correct output :(

an2609

check ur ans on online ide. here

flk

Anyone else cannot find their name in the standings although they participated?

deathsurgeon

Are you sure you are checking the unofficial standings?

Mark the checkbox "Show unofficial".

WTF !!!

This is bullshit , where's the rating change for div2 !!!!!

That feel when you fail the round but still improve your rating and become blue. https://www.youtube.com/watch?v=BinWA0EenDY

AmericanPsycho

Div 2 will be rated?

+17

hmrockstar

Waiting for div. 2 rating changes!

orb

Is the rating updated? I'm from div.2 and was not rated.

c4big2

Me too...

TooObvious

is the round gonna be rated for Unofficial Div.2

duckladydinh

I am an unofficial div 2 participant and my rating stays the same after rating change. Can someone explain?

Amiri

for all unofficial div.2 participants still doesn't change.

I think rating change in this round will be in two part for us and for officially participants separately.

Kareem_Mohamed

That's a common problem for DIV2 unofficial participants

+40

It will be updated soon.

Здравствуйте! Можете разъяснить 1 момент? В задачи Е программа-жюри выдала мне результат "Неправильный ответ", однако, мой вывод соответствует правильному (Доказательство на скрине). Т.е. подходит cj и kd (выведенный мной результат), но cj jk (выведенный жюри результат) НЕ СООТВЕТСТВУЕТ ПРАВИЛЬНОМУ! Мой ответ не засчитан верным.

Ну или же я неправильно что-то понял о.о p.s. Второй правильный ответ — 2 4 ведь.

У вас выбраны строки jk и cj. Из них надо составить строку kdcj, но это невозможно, так как в ваших строках нет символа d.

← Rev. 4 →

Я взял cj и kd. Составляется же просто: kd + cj = kdcj. Или нужно обязательно, чтоб поочерёдно шли названия? Этого нет в условии.

А вот ЖЮРИ и правда выбирает cj и jk!

krock21

Строчки:

1ая - cj
2ая - kd
3я  - jk
4ая - dc

1ая и 3я строчка, это cj и jk (ваш выбор)

3я и 4ая строчка, это jk и dc (выбор жюри)

Я прекрасно понимаю условия задачи. Если на нормальном варианте, всё выходит так:

У нас строка kdcj. Жюри выбирает строку, начиная с 3-го символа: cj и с 4-того jk.

Я выбираю с 3-го — cj и с 1-го — kd.

Во вторую строку выведите n целых чисел — номера популярных игр, записанных на диске Толи, а вы выводите первые символы нужных строк

необходимы номера, а не позиции начала

Вы неправильно поняли условие. Вы думаете, что надо просто вывести фигню вроде "1, (1+k), (1+2k), ...", как позиции начала подстрок главной строки, тогда как задача намного сложнее. Для чего, по-вашему, последние 4 строки в тесте?

ankeshgupta007

thanks for clearing!

PaneerPakora

Hi. Could someone please clarify who will have ratings changes for this round? It appears that all those who were official participants have had ratings changes, unlike what was said — that it will be rated for div 2 and official participants are Russian school students. If it is clarified, it will be great!

This is the best comment I read :D

EbraM96

What about the editorials ? there will be editorials like regular CF rounds ?

Of course, there were editorials for the previous Technocup.

MrFoxPro

+10

Ничего не понимаю. Код прошел все претесты, естественно, я его протестировал на данных примерах, но почему-то на первом главном тесте код не прошел, причем тест дан из примера, который я протестил. Запустил отправленный код у себя — ответ правильный Я совсем не понимаю, почему так происходит, мне кажется, что произошла ошибка. Что делать?!

fr0st

Скорее всего у тебя проблемы с культурой при приведении к строке или парсинге из строки.

Я тоже об этом подумал, но тогда почему прошли претесты?

Добавь вначало программы Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture И запусти, твой ответ будет неправильным и будет совпадать с ответом на сервере

Rating changes are weird for unofficial participants . In usual rounds any rank < 300 fetched me a positive rating change , today even a rank of 177 fetched me negative change o.O

That's because number of users were much lesser today.

daga

In problem D, flow worked. Constraints were not tight.

Nams

Do you mean to say that the test cases are weak. Or your algorithm worked in linear time? As far as I know max flow works in O(E*V^2).

ooOOOOoooOOOOo

Why didn't I get any rating changes? (I registered during the contest)

AnasAbbas

the same here

Do you registered during the contest as well?

Ice_Cream

My rating hasn't changed 1 hour ago, but now it has changed . Sorry for my sorry English.

Still didn't get any rating update.

yes

+48

Achievement unlocked! Gotta change my handle now!

wspolbiezneRlz

I was so close to rain on your parade :D

The same way you were so close not to be so close "to rain on my parade" :D

I see that some div2 participants have their rating changed after the contest. But still no change for me :( ?

alex_bucevschi

same here.

Thats weird.

I thought that with other div2 participants my rating will also be updated but it didn't happen.

khaledafify

where is the editorial ?

Кстати вот параметры для одинарного хэширования в E, которое заходит:

const long long MOD = 2999999989LL;
const long long BASE = 43;

21455919

Monster_king

Для неофиц. участников из второго дивизиона также будет пересчитан рейтинг. Но мне рейтинг не дали, почему???

4 балла же вроде вам начислили.

philologist

problem E. I have written hash as described here but failed on 14 test. What is wrong? It is not good approach here or should I search bag in my code?

Vergara

Лукас, если тоже писал с планшета на уроке на задней парте))

corwinn

Предупреждайте,пожалуйста,о наличии интерактивных задач заранее.Это была первая интерактивная задача которую я тут решал.Я придумал алгоритм решения довольно быстро,а следующий час пытался ее сдать...Неуспешно.

Объясните,пожалуйста,что исправить,чтобы оно работало.Вердикт-зависло на 1 тесте

dalex

Перевод строки не выводишь. В семплах есть перевод строки? Есть. А почему не выводишь?

А еще можно было нагуглить, как решать интерактивки, прямо во время раунда. "site:codeforces.com" и вперед.

Смотрел,не заметил перевод строки...( Сделал перевод,сдал Обидно( Спасибо большое!

Killever

Is there any python solution passed for D ? my Python code got TLE, it's frustrating when you have to rewrite the same code with another language to get accepted.

Would someone mind help take a look at this code for Div2F? It seems to over-estimates the answer but I don't know why.

http://codeforces.net/contest/727/submission/21475250

Logic: Solve the queries offline, answer them in non-increasing oreder as the solutions are monotonic. Always keep the minimum prefix sum, whenever the guessed mood is not sufficient to compensate the prefix sum, keep removing the worst quality question from the array and increase the counter by one.

frankbozar

Removing the worst isn't optimal. We should remove the one that maximizes the minimum of new prefix sum.

3 1
-2 2 -3
1

When will the editorial be posted?

ivanilos

It is already posted (and translated, as the Russian version was available before the English one)

http://codeforces.net/blog/entry/47773

How did u know that it was posted ? I log in daily and didn't notice it in "Recent actions" section !

I guess it was posted in recent actions, though I am learning Russian and sometimes I go to Russian version of the website (maybe it was only posted there and then I changed the language to English — as I know less Russian than a 5 year old kid. I don't know how blogposts work, but I saw it in recent actions).