Всего через 6 с половиной часов начнётся Раунд 2 чемпионата по программированию VK Cup 2016! Если вы не зарегистрировались на раунд — не беда! Есть дополнительная регистрация!
В этом раунде могут принять участие все те команды, которые отобрались в Раунде 1 или в Уайлд-кард раунде 1. Участников ждет соревнование по правилам классических раундов Codeforces. Одновременно с основным раундом будет проведена интернет-трансляция, которая представляет из себя обычный рейтинговый div1/div2-раунд по правилам Codeforces. В трансляции может участвовать любой участник, не зарегистрированный на основной раунд в составе отобравшейся команды.
Раунд для вас подготовили AlexFetisov и winger. Это первый для нас раунд на Codeforces в качестве авторов. Огромное спасибо Глебу Евстропову (GlebsHP) за долгое сотруднечество и помощь в приготовлении раунда. Глеб делает колоссальную работу, и я хотел бы это отметить еще один раз! Также большое спасибо Kamil Debowski (Errichto), Mateusz Radecki (Radewoosh), Боре Минаеву (qwerty787788), Паше Кунявскому (PavelKunyavskiy) за прорешивание задач и дельные советы. Огромное спасибо Мише Мирзаянову (MikeMirzayanov) за все, что он сделал для всех нас!
Напомним, что в Раунд 3 пройдут все те команды, которые наберут положительный балл, не меньший, чем у команды на 100-м месте. Также обращаем ваше внимание, что все команды, проходящие в Раунд 3, получат фирменную футболку Чемпионата. Помимо этого, фирменной футболкой будут награждены топ-50 участников интернет-трансляции Раунда 3.
Желаем удачи и интересной борьбы!
Обновление
Раунд завершен. Надеюсь, задачи вам понравились! Поздравляем победителей!
Официальный VK Round 2:
- Who`s On First Base!: -XraY-, ershov.stanislav
- Beer and lemon tea: sankear, Zlobober
- MYCOPOBO3: V--o_o--V, LHiC
- Never Lucky: subscriber, tourist
- 33% less bad jokes: ifsmirnov, Arterm
Результаты Div1:
Результаты Div2:
Разбор
Auto comment: topic has been translated by AlexFetisov (original revision, translated revision, compare)
Stay away tweety :p .
lol
tweety :P
Is this Silvistar???
now many participants wish tweety was here :p
What the difference between the VK round 2 and the codeforces round. Like for example if a div 2 coder participated in the codeforces round and solved few problems can he participate in VK round 3 or do I have to participate in VK round 2 exclusively. And can't I just participate in VK round 2 AND codeforces round so if I solve a problem in one of them I solve 2 so my rating will go sky high. :-)
"Also note that all teams advanced to Round 3 will get a special edition t-shirt of the competition. Also top-50 participants of the round 3 will get this t-shirt as well"
Is there a mistake here?
"All teams advanced to Round 3 and TOP-50 participants of online-mirror of Round 3 will get t-shirts."
(Translation from Russian)
Does it make sense? Shouldn't it be TOP-50 from today's contest? Top participants from VK round 2 are awarded with shirts, so why unofficial round 3? Am I right?
Does that mean I won my first shirt ever??
Nope, this was Round 2, and T-shirts will be devlivered in Round 3
is Div 2 for Russian speakers only ?
No.
.
First: I have opened the announcement. Second: Ctrl+F Rated, Ok, then let's go on.
Wtf?
What is it???
A rated CF contest???
Yes, will you participate?
Yes, if I am still awaken at that time~~
how can i delete my comment?
No skeleton images saying waiting .... till now .
Wierd!
Skeleton is too busy throwing bombs ;)
rated round??? is that an extinct dinosaur ???
что-то никто не спрашивает про количество задач и разбаловку:)
Если вы не зарегестрировались
за долгое сотруднечество и помощь в приготовлении раунда
:)
The number of downvoted comments is too high!
The first rated round in forever and I can't compete! This sucks lol. The wait for Friday begins.
Scoring — standard or dynamic?
nice problem in Div.2, 669D - Little Artem and Dance
How to solve it.
You can sum all the rotations and remember that value. And for swaps, only parity of the current rotation sum matters. When you do two swaps with the same parity, they cancel each other. So you simply need to count the final number t of non cancelled swaps, and the parity of the first swap in this sequences.
Each number goes to t positions left or right, depending on the first swap parity and the parity of the number. And then you rotate the whole array by the sum of all rotations.
Solved it in 5 minutes, spent the rest of the contest debugging. Fix a test another one fails, fix the other the first one fails. I wanna kill myself >_<
very well , do it.
maybe we will get more rated contests :v
Well that's rude...
Was similar for me. I had the solution which passed all samples and all my tests. But got 7 WAs. And 3 minutes before the end I realized that parity of the first swap matters, and managed to submit it.
just store number of moves for odd positioned boy and even positioned boy and finaly calculate the position of all I don't know its right or not but it has passed pretest :)
Was it possible to avoid TLE on problem D with a O(n+q) solution ?
I got TLE using even
ios_base::sync_with_stdio(false);,cin.tie(NULL)andcout.tie(NULL)AC after switching to printf and scanf.
It was weird.
TLE with iostream
Pretests passed with stdio and small optimizations
At the end I did, but I had to buffer my readers and writers directly instead of using Scanner and StringBuilder.
How could we do in Python, then ?
Очень некрасиво давать задачи, где решения без printf/scanf получают TL. Дизреспект.
У меня решение работало за ~1900. Перезаслал на всякий случай :(
Да, в Д такая же тема
Подтверждаю.
В задачах C и D слишком большой ввод-вывод
Плюсую! 31 контест из-за этого слил(
зажрались вы со своими cin/cout'ами
те, кто на Java и Python пишут, тоже зажрались?
Где я упомянул про эти языки?
На самом деле, к ситуации с java уже все привыкли, а вот к cin/cout ещё нет.
И ещё, одно дело жаловаться, что решение не прошло, а другое — обзывать из-за этого авторов. Вот я и написал, что настольно зажрались, что грань не видна.
"обзывать из-за этого авторов" -- Чего? Где вы видите обзывательства? Мне ваши замечания про настольное зажирательство что-то совсем непонятны стали.
Я всего-то написал, что некрасиво давать задачи с такими ограничениями, где меряется не эффективность алгоритма, а скорость считывания данных. Очевидно, что для тех, кто пишет на Java и Python это крайне существенно.
А ещё ты написал "дизреспект". Раз не понимаешь — то у нас разные взгляды на мир, не иначе. Я когда получаю такой TLE, виню в первую очередь разработчиков языка/компилятора, НО НИКАК НЕ АВТОРОВ ЗАДАЧИ. Сейчас, для меня, это так же смешно, как "у меня в решении вместо int[] написан map<int,int>, я получил TL, плохая задача, много инпута, дизреспект". Несколько лет назад такая ситуация была с векторами против массивов — сейчас всё ок.
Вообще не очевидно. Обычная читалка для java, которая есть у всех, кто выбрал этот язык как основной, быстрее cin'a — значит у джавистов проблем с этим нет.
А про python — там, вроде, проблемы и с самим быстродействием языка, а время считывания в таких задачах равносильно времени работы алгоритма.
Успокаиваю, дизреспект -- это не обзывательство=)
How to solve Div2E?
Hash table mapping an integer to a binary search tree of integers.
Hi, My solution was maintain a Binary index tree with unordered_map<int,int> in each node, which is o(1) , then just do classical update, query on it.
I used one Segment Tree for each unique value. Just store ± 1 for each insertion/deletion and perform sum queries.
Shouldn't having a big array for each unique value memory limit?
I used STL map which maps each integer to a set of time.The solution passed pretest but it got TLE in Test case 11.
I think that this solution take O(n*(log(n)^2)) Can you please tell me time complexity of the solution that uses segment tree or fenwik tree?
Mine is O(nlog(n)) using Fenwick Tree
Ok, Thank you. I tried another solution where I stored pairs of integers in c++ STL sets and this solution is O(nlog(n)) still it is giving time limit exceeded. Can anyone explain why the solution is slower than than other O(nlog(n)) solutions?
Your submission is actually N^2; std::distance used on set iterators takes time linear in the distance between the two iterators.
My solution with Segment Trees: 17494007
This is O(NlogN)
I have a doubt : Sometimes like today's D scanf/printf seems to perform exceptionally well over cin/cout. Though I was using ~~~~~ ios::sync_with_stdio(0); ~~~~~
with no endl i.e. flushing of output yet my program ran in about 1.9 seconds changing cin/cout to scanf/printf reduced time by 3.
What is the reason behind it? I lost more than 150 points due to re-submissions
I realy don't understand why linear solution for D (O(n + q)) gets TLE...
You need very optimized I/O... this particular problem pushed the limits of what can be done in 2 seconds in that regard.
I always use C#. And never got this problem before. Something went wrong today...Of course i will investigate the problem after systests. But I think time limit should be such that the solution has passed not only on C++...
I passed it with Java but needed to do several things I wasn't used to with the I/O (namely, use a BufferedReader directly instead of a Scanner, and use a BufferedWriter rather than println()ing a string made with a StringBuilder).
got 4 TLE on pretest 11, even by using ios::sync_with_stdio(0) on a O(n+q) solution. But as anh1l1ator told that scanf/printf were running on time, I think it was more of language based question.
Am I the only one who consider that precision problems in div1C were more than annoying? I still don't consider I've made any mistake and I don't know why sometimes I get WA on pretest 8 sometimes on 9...The intended solution was with product and sum of the partial sums?
Div. 1 D maybe?
I don't think so. I was talking about div1C from unofficial contest. Maybe in official contest they were numbered some other way
Oh, my bad :)
Its very weird. My solution with long double didn't pass pretests but when I changed it to double it did. B/w I also did the same thing.
... Nice avatar :)
Thanks! you too :P
My solution uses long doubles, fails pretests under G++, passes pretests under MS VC++ (when all else fails: change compiler :) ). Let's see after systests, though...
Btw, MSVC doesn't have
long doubletype, it's the same asdoubleon it.I also got a few WA on pretest 8. It seems it was because I was taking the square root of a negative number when it should have been 0.
I tried to hack a solution with O(n) on problem A div2 but it was unsuccessful (n=10^9) :(
why?!
If it was just a while loop with addition/subtraction it's more than possible they could have gotten a billion operations done in 2 seconds.
the same happened to me, I tried to hack a O(n^2) in B div2 and it passes!!!!!
I hacked O(N^2) solution succesfully.
Some sort of compiler optimization?
Like This
I try it on custom invocation and this is the result
How to solve problem 4 Div 2. i was encountering the problem when x is odd.
Свапнуть бы D и E.
E вообще выкинуть надо, ИМХО.
I think ABCD should be circular-shifted.
In problem B div2, little artem and grasshopper,
second sample test
3 >>< 2 1 1area starts from 1 and ends at 3.start from cell 1, jump 2 steps right, reach cell 3. direction is again right, jump 1 step ahead reach cell 4 and get out of the area. but the note in the problem says, Second sample grasshopper path is 1 — 3 — 2 — 3 — 2 — 3 and so on. can someone explain why?
Because each cell had a direction and length associated with it... this was not a sequential list of commands but rather the grasshopper sees a sign on the cell giving the directions... the problem asked whether the grasshopper would ever step out of bounds or whether it would keep hopping in an infinite cycle.
In the example given, the grasshopper sees a sign on the first cell saying to go right 2. Then it sees a sign on the third cell saying go left one. The dutiful grasshopper then sees a sign on the second cell saying go right one. These last two loop forever, and hence the solution is infinite.
understood, thanks.
No you should move in the direction of the '<' in cell 3 you will back 1 cell so you will be in cell 2
Solution to problem E: #66TUPO
I mean you really think it is a bit hard? Or I should expect some unexpected verdict?
Nice! I mapped each x to a segment tree :D
I didn't write the round, but it's the first thing came into my mind. Very straightforward. Even without this cheat, coordinate compression + fenwick trees don't make it less straightforward.
This problem is very hard when you are shocked by unknown WA of C. (and this problem makes one angry, when you realize some crappy precision error was the one who blewed up such easy problems)
Actually, I searched for your policy-based data structure article in contest — because n <= 1000000 and segtree solution will get MLE. (I calculated 240MB with dirty compression) sadly OSX clang can't compile gnu__pbds, so I used ideone to debug — it was painful.
Soon it turned out that these efforts were useless because 1. n <= 100000 2. I read statements wrong.
I can't compile that either, but what I do is use a set and once I'm sure it works I just change the code to use the policy based ds, which should be around 2-3 lines, go into custom test and check if my code still works, worked fine for me during contest :)
Too bad there wasn't a lot of hacking happening this round — strong pretests I suppose
problems were relatively easier than previous round #347
На не-плюсах в C и D ( O(N) ) вообще реально получить AC?
Да, на C
Edit : Div2 A
Div1 C:
I wonder, how many solutions will fail because of this case? Mine certainly will :/ EDIT: Actually, it seems like I passed.
https://www.dropbox.com/s/08m764rlxuvnd6q/hack.txt?dl=0
I will get WA too. I tested it on your hack and my program output all nan. It was meant to be purely a math problem, not a programming problem -_- EDIT: I somehow passed systests...
Is there anything specific in this case? My solution works fine with it.
I think people who use sqrt function in their solution will see something like 1.00007 and 0.999934 when they add up the sum of their output, which will be > 1e-6 error.
I can see that you did not make any hack with this case.. Thank you, I can still hope to pass systest! :)
Is that a good probability? They are produced by my solution that passed pretests :P
a[i]=15083328916245932279840823609130527921079628476947190293794832049848427950033787764642925414628390330310916731933701947465371533061711148760114759803382653601121625233155946862022851427067088008522984157822017083296402464626853429590473211951849790874316769424402880358084931661613943529882190463340932869005131383232439121936748517148328737418372810911926497042735900081847898594371012194165746830896795480609079081172302829734639014034645165655017825088703634305866700555015137682443072942387017868033906236880579419521133614288513156362590844990804612816574232074299859735223614812296545257397381507457860747751574308225499542843354186170024701235438344817574100140731253729526497350066797319223996129851165727915197654461897429418079299555662797004798095895094086282391980738121825921877282118365893597035261873904749959394553190509543153197575014620757453443744428830827654721563319109783119882310723355051640716023096845418774027557237149504187519938022673234264064.0000000000, b[i]=-15083328916245932279840823609130527921079628476947190293794832049848427950033787764642925414628390330310916731933701947465371533061711148760114759803382653601121625233155946862022851427067088008522984157822017083296402464626853429590473211951849790874316769424402880358084931661613943529882190463340932869005131383232439121936748517148328737418372810911926497042735900081847898594371012194165746830896795480609079081172302829734639014034645165655017825088703634305866700555015137682443072942387017868033906236880579419521133614288513156362590844990804612816574232074299859735223614812296545257397381507457860747751574308225499542843354186170024701235438344817574100140731253729526497350066797319223996129851165727915197654461897429418079299555662797004798095895094086282391980738121825921877282118365893597035261873904749959394553190509543153197575014620757453443744428830827654721563319109783119882310723355051640716023096845418774027557237149504187519938022673234264064.0000000000
What is the correct answer to this test? My solution said that there is no such one, because of negative discriminant(it is not precision issue).
According to statement,
When each die has equal probability for each number that condition is satisfied. Specifically, 12500-sided dice with each number occurring with probability 8 × 10 - 5.
Yes, but that doesn't say anything about validity of the input. Values from the input should represent exact probabilities of min(a, b) and max(a, b). So I assume probabilities from your input are rounded probabilities for the dice you described.
Problem would be way harder if you just had to find probability distributions such that min(a, b) and max(a, b) are within 10^-6 from ones given in the input.
This generator produces right probabilities. My solution works ok on such test.
Announcement that n is up to 1e6 not 1e5 in D after 1h and 20 min passed, really --__--???
EDIT: Ofc, I meant the other way around xD
Be happy it wasn't the other way around :)
Actually it was.
Wait, it was the other direction. We announced it was 1e5 NOT 1e6. But still this is no ok (
well, not sure if changing TLs (in at least two problems) sliently is much better
О чём авторы думали на счёт задачи A,D ну и E,в плане большого ввода. Из-за этой проблемы я сегодня стану не серо-зелёным,а светло-зелёным. Прошу переделать и всем у кого из-за этой ошибки выводился вердикт "Превышенно ограничение времени на претесте 8",на вердикт "Претесты пройдены". Спасибо за внимание.
Предлагаю вам изучить вопрос ускоренного ввода на языке Java( к примеру открыть решения топкодеров пишущих на Java, к примеру:Petr, Egor). И да, вердикт осуществляется тестирующей системой, и менять его никто не будет (:
I don't know why i read rotation being done as right rotation instead of left rotation initially in Div 2 C.
How to solve Div 2 D?
The relative positions of boys at odd position will remain same and boys at even position will remain same. So count shifts of odd places and even places individually. After counting, just check from which position you have to start.
Code
Why did this solution of mine get TLE on pretest #9 on problem div1C? (I can virtually see no way it will do worse than O(n))
http://codeforces.net/contest/668/submission/17498093
Or pastebin: http://pastebin.com/0hCpNWx6
Could it be because of the use of cin, cout?
Can not wait for system testing!
What was the pretest 4 Of Little Artem And Dance ?
I don't know what exactly was the test case, but my solution which failed on test case 4 gives wrong answer on this test.
The answer should be
1 2 3 4 5 6I got TLE on pretest 3(problem F). I tried to optimize my code in ~20 min, finally found(after contest) my code failed on testcase n=1,k=1. T_T
My solution passed after fixing this small bug. T_T (what a sad story.
I guess it was too difficult to find during the contest...
Can anyone explain why this solution gets WA3 and this solution passes pretests?
Can someone explain why my solution with scanf/printf gets WA on pretest 6 and the exact same solution with cin/cout passes the pretests?
http://paste.ubuntu.com/16038368/
http://paste.ubuntu.com/16038378/
I'm assuming it is because z is uninitialized.
oh, you're probably right. I can't believe I missed that!
как решать Д?
я в цикле от 1 до н составлял два уравнения: для максимума и минимума, от туда получал квадратное уравнение и главный вопрос как выбрать знак при дискременанте?
У меня прошло претесты, когда я всегда выбирал знак одинаково. Почему, не знаю.
Утверждается, что если нужно выбрать порядок в парах pi, qi так, чтобы pi ≤ pi + 1, qi ≤ qi + 1, то можно просто брать в качестве pi меньшее, а в качестве qi большее — если решение вообще есть, то нет никакого смысла брать разный порядок в соседних парах — если минимум одной пары не меньше максимума другой, то первую пару можно располагать как угодно.
я пробовал всегда плюс — не проходит ВА 3
добавил проверку, если меньше нуля или больше единицы — меняю знак — не прошло ВА 3
идти с конца — не прошло ВА 8
идти с конца проверить решение -если не проходит — идти с начала — ТЛ 9
Can anyone tell why did I get MLE verdict on my solution of Div2B 17492812 ?
No one can view your code now, so you have to wait after system test or you can write it on Ideone and give us the link
Here it is in ideone Solution . Thank You
Try this case:
what was the pretest 6 of div2 C
-deleted-
isn't the answer
7 2 53 2 4?
EDIT: so hard editing...
Yes!,It's
7 2 5
3 2 4
Could anyone solve F with matrix-tree theorem? It seems possible but when unfortunately diagonal cell becomes 0 modulo 10^9+7 I cannot continue anymore...
I think the solution is based on tree decomposition. The tree width of this graph is very small.
What makes you think the treewidth is small? I can't really construct a good example (always hard with treewidth) but it seems to me that you could make some very unfriendly graphs.
Because it's k.
The treewidth is k? How would you construct the decomposition? I'm guessing every time you add some vertex you want to put it in a bag with its k neighbours, but how would you build the tree?
Think of it as following:
Ah, I get it now, thanks :) Then the DP-state for a bag {v1, v2, ..., vk + 1} in the tree would probably be something along the lines of: for each partition of the bag into non-empty subsets: in how many ways can we create a spanning forest covering all vertices in the subtree rooted at the bag, according to the partition we are considering (that is, two vertices are in the same set in the partition iff they are covered by the same spanning tree). Does that make sense?
EDIT: Nevermind, you overestimate the answer a lot this way, for some edge {u, v}, u and v may be in a lot of different bags together, and this way you're counting adding this edge (between two spanning trees) in a lot of different bags. You probably have to somehow single out the one vertex that is added each step.. I'll think about this some more :)
Maybe solution can be obtained on the following way. DP over the tree decomposition. State is a bag + some tree that spans vertices from the bag. And in transitions one should preserve edges which are already added in the parent bag. Number of states would be N(k + 1)k - 1 ≈ 1.2·107 and one should be careful with transitions (perhaps some precomputing will help). Does it make sense?
Gah... cin and cout in Div 2 D
Well I guess lesson learned: Be wary if they put such an easy problem as a Div 2 D. It literally took me 3 minutes to think of. This means that there's a trap.
Wasn't it obvious? The limits for q are too big.
I used fast i/o with cin and still got tle :(
It's jqdai0815 to start system testing!
Please start system testing, I wanna go to bed :-(
me too! But i will wait system testing!
it's 12 pm in my region
UPD: 12 am
It's 4 am in my region
You made me hopeful :)
I think you mean 12 AM
You are right
They removed the three contests from the contests' list, which is unusual...
This error is probably because wild card round 2 starts before the end of this contest
Требую повышения квоты за конченные косяки в условиях, которые изрядно подпортили положение нашей команды. (Задача E и C)
И провести потом раунд 2,5.
Так ведь и так wild card будет
В задаче Е все было норм. Нормальное решение и для 10^6 тоже будет работать.
Разве что для тех, кто пишет на Java немного неудобно было.
Да, но мое решение которое я придумал сначала, было за n log^2 n, и соответственно не проходило. Я думаю на соревнованиях высокого уровня, такие косяки просто недопустимы.
Все были в одинаковых условиях!
Когда я начал ее решать на 25 минуте, а изменения пришли только в 1:30. Думаешь это правильно и все в равных условиях, если кто то дошел до нее только в 1:30? Время было потрачено зря.
Но такие вещи добавляют рандома. Одна команда может думать над задачей, как бы оптимизировать константы, чтобы заходило с этими ограничениями, а другая в это время вообще решать другую задачу. И тут сообщают, что ограничения в 10 раз меньше. В результате первая команда потратила время впустую, а вторая — нет.
Waiting for sys testing is worse than waiting for game of thrones season 6 :/
Waiting for sys testing is worse than waiting for game of thrones season 6 :(
is it!?
Yes, it is worse
I had a doubt. When your were white then your handle was also white? o_O
Oh, atleast you know what it will start.
Here
is it worse than waiting for rated contest?
From now on, I will try not to trust problem setters' problem difficulty estimations.
Wrote a wrong and unnecessary special case. FeelsBadMan
when you find out that you mistyped m to n in problem A after the contest had finished.... Nezzar
Ребята, нажмите кнопку "НАЧАТЬ СИСТЕМНОЕ ТЕСТИРОВАНИЕ", плез. Неужели только один Мирзаянов может на нее нажать?
Problem B write too difficult to know :( :( At least for me... And I waste so many time to understand... Down to 1k5 again :(( :((
Could anyone find the contest on contests page? Has it gone???
you can access them from here
Здравствуйте Мы писали контест VK Cup 2016 — Раунд 2 и у нас появилась чужая посылка . Можно ли ее убрать?вот эта посылка
Хаха, может это твой сокомандник? :)
waiting for t-shirt...
any hacks on Div2 B?
3
>><2 3 2
Ouput: INFINITE ???
yep.
Someone please tell me... is System Test starting or should I go to sleep? :(
1:38 AM in Bangladesh. Still waiting! Hope
In Div2D=Div1B it is algoritmically easy to find O(n) solution, but what the hell the bounds of input are of order 10^6?? Very intelligent method to make the problem more difficult:( Is it really interesting to play a game "Who didn't forget about scanf/printf?"?
(I have 1964ms on pretests using cin-cout with standard accelerators and I noticed that it is so close to TL only after the end of the contest.)
4:46 AM here, wating for system test.
By the way, my mid-term exam starts at 1:00 PM..... (cries)
В проге на С++, заходит ли программа в assert или нет?
То есть с -o2 вроде же не должен туда заходить, не так ли?
У меня на assert'ах RUNTIME_ERROR иногда вылазил. Думаю заходит
PS: помню даже один раз выкорчевывание ассертов сделало AC из TL. Правда не уверен что на кодфорсах
Печально, когда ставишь assert(D > -1e-9) в задаче D :C
UPD: Здорово, когда это решение все равно заходит:D
Зависит от компилятора. Стандарт не регламентирует, что с какими-то уровнями оптимизации assert не должен выполняться, в g++ это не так, а вот в Visual Studio в Release действительно все assert выпиливаются.
System testing of div 2 finally started!
I am rather waiting for tutorial...
I had some difficulty in understanding DIV 2 E / DIV1 D's problem statement.
1 1 1
2 3 1
3 2 1
Should the answer of this case be 1 or 0?
The answer is 1.
You add the number at time 1 and remove it at time 3. So the number is in the multiset at time 2.
Когда поймал Мирзаянова)
А к чему это к "VK Cup Round 2"?
I got TLE in fourth task. I think it isn't possible. My complexity is O(n+q) + I done it in Pascal and I don't have bad loops.
My code
same happened to me. I think we needed to use fast I/O
This is really bad. My appeal to codeforces to check it again.
they should have mentioned to use faster I/O but there were 4*10^6 IO operations
Can I use fast I/O in Pascal ?
Try delphi.
I am not supporting the authors , i am just saying that faster I/O was needed for this problem
I got TLE too, fast I/O was needed I believe. I always trusted in codeforces servers but it looks like reading and writing 10^6 numbers isn't fast in off using cin/cout even here.
why did O(n+q) get TLE in div 2 D? And we weren't even given any warning to use faster I/O :(
System testing pausing at 95% is like watching a football penalty shootout and boom, there comes the blackout. T^T
Разница между 100-ым и 101-ым 1 балл :)
Рейтинг будет сразу?
Frankly saying, it would be good to have it unrated XD (inb4 I'm 29th, so that's not that bad). That one zero too much in D's (or E's) was really something with very bad influence on contest (n<=1e6 and TL=1s doesn't look like even n log n should pass and it was announced after 2/3 of contest has passed) and tests to C were really weak. I got AC in C, however in test posted by FatalEagle here my solution produces completely shitty output and I expect a big part of solutions having similar precision issues which are really hard to omit in that problem (which is pretty sad, that makes this problem a bad fit for a contest).
Also using cin and cout with
ios_base::sync_with_stdio(0);cin.tie(0);passes pretests in div1B but fails system tests...I got lucky, because I got TLE on pretests xD. But if it is the case for some people then it really sucks.
On FatalEagle's test case, I got WA too. In addition, it took about 5 seconds to run, and n=12500,so I have no idea how I didn't get TLE for n=1e5.
I am getting a deja vu. Tweety is that you?
And I used to think that people in Poland find giving TL=1s, n<=1e6 for NlogN solutions completely OK, after looking at some of your problemsets :)
Let us be able to practice please.
How to solve E(about 2-SAT)?
Build directed graphs like what we usually do in a 2-SAT problem.
Claim: If u is reachable from not u, u must be true. After you deal with these variables, you can assign other variables in any order you like.
First you should check whether they are satisfiable. If both of them are satisfiable, check whether there exists a vertex pair (u,v) s.t. v is reachable from u in one graph but not the other. Then set u=True and v=False, and find a solution in the graph where v is not reachable from u.
I haven't got AC though :p
Edit: AC :)
Note: I use bitset to build the transitive closure too.
Suppose that both expressions are satisfiable. Let's try to find a solution for the second expression that doesn't satisfy the first one (then we can swap the expressions and repeat this again).
If the set of variables doesn't satisfy the first expression, there should be a clause which is equal to false after substitution. Let's iterate over all clauses from the first expression and try to find a solution of the second expression which makes this clause's value equal to false. If the clause of the form
contains both x and !x for some x.
(a or b)is false, we know the values of these variables (in this case they should be both false). So we need to check whether there exists a solution for the second expression in which the values of these two variables are fixed. Let S(a) be the set of nodes that can be reached from vertex a in implication graph (the graph where each variable has 2 vertices and where we add edges!a -> band!b -> afor each clause(a or b)). What we need to check is whetherWe can use bitsets to find transitive closure of the graph and also we can use them to check if
contains a pair of x and !x. If it doesn't, then we know there exists a solution where the values of the given two variables is fixed and we just need to find any such solution. First, we need to fix values of the variables reachable from a and b. Then we can repeat the following: pick any variable which is not fixed yet, try to fix any value for it and then fix all values of the variables reachable from it. If there's a contradiction, flip the value of the current variable and repeat the process again. Note that we don't need to do dfs for this as we already have transitive closure computed.
Overall complexity is O(N3 + M·N) which is fast enough if you're using bitsets (my solution got AC with time 378ms).
Хочу узнать мнение Codeforces: хорошо ли, что все претесты в B были квадратными?
Мой небогатый опыт подготовки раундов подсказывает, что баг
forn(j, n)заслуживает бревна на претестах, но никак не на финальных тестах. А что думаете вы?Если в этой задаче сделать претесты не квадратными, то вообще одним тестом обойтись можно и тестировать нечего будет. С другой стороны, надо хотя бы сделать неквадратный тест в сэмплах, отражающий неквадратность матрицы в целом.
This is my first win on a rated (don't make it unrated please) Codeforces round ever!
In problem F, my solution will fail on a test case that their answer is 0 (a multiple of 10^9+7) (I could add one line to fix this bug). Can anyone construct a hack input?
PS: I was wrong. The condition of the bug of my solution is not just "answer is 0" but that must satisfy a specific condition in addition to that.
Why can't I submit solution to problem E now?
Because they didn't enable the practice mode yet
Please don't make this round unrated. As is codeforces has very few rated events nowadays. Yes there was a minor issue with testing in problem C, but when people take time out of their schedule for a rated contest, it's really disappointing to see it made unrated just because the problem setters didn't make good tests for one problem.
Rating has already been changed :)
Tutorial please !?
Was reading comments... All these people saying things like "oh lord so many numbers, i'm too slow for it", "it's not right", "it's not fair!!!!!", "oh look at me I'm little girl and bad authors gave me too much numbers", "CF servers isn't good enough to provide fast I\O so my perfect solution pass all systests". Guys, are you OK? It's your problem that you didn't know that 4·106 I\O operations work not really fast. It's only your problem, not author's fault, not CF's slowness, it's your amateurism, that's all. If you want to improve your skills, stop crying like a little girls, blaming everybody for you fails and start learning from your mistakes.
When I started to code on Java, I looked through code of people with high rating, found out some hints and of course took fast I\O from Petr's code. And I'd never had problems with I\O. Same with C++: when i started to use this language, Burunduk1 showed me his fast I\O template, I really liked it, and since then I use it almost always. It's nice and several times faster then usual I\O, so I never think about I\O time.
What about contest... I hate myself so much! I ruined it for my team by planting amazing bug in my C solution.
if (x % 2 == 1) changeParity();See what's happening here? That's right, bullshit (-1 % 2 == -1). And I was searching for this bug more than a hour of contest. My teammate also wasted a lot of time helping me. Finally I wrote stress-testing and first test with query1 -1failed my solution.In conclusion I would like to say that contest was good, problems were interesting, just don't understand why E is E, but it doesn't really matter, such things happen sometimes and don't spoil anything. Thanks to authors! Now looking forward to marathon, hope I'll have chances there.
Thanks! That comment made my day :)
I used
x & 1instead ofx % 2so hadn't any troubles :DOh, i told this short stupid boring story to my teammate after contest:
In my Java-days I was always using bitwise operations, because it worked faster. But in C++
x /= 2, x *= 4and all other similar operations work the same time, because of compiler optimizations. So when I started using C++, I stopped using bitwise operations and began to use usual operations, because it looks clearer and more logical, as for me. And today, when I was writing thisif, at first I wanted to writex & 1, but then said to myself: "Come on, boy, why do you need to do this? Use division, it looks nicer, but works just as well". So I agreed with myself and wrotex % 2with stupid smile on my face (I'm sure it was stupid).Come on, why should "little girl" know when this freaking CF compiler work slow(Normal gcc's IO is not as slow, with speed approx. the same as scanf), which functions it doesn't support just because it doesn't (I'm about to_string, for example), etc
After all, that's an algorithmic competition, where ability to construct algo's is intended to be checked not the knowledge of pitfails of specific wierd compiler
PS: checked all your public c++ submissions, and didn't see anything like fast template.
And what if next contest will contain a problem with 107 I\O operations? You'll also be talking about freaking CF compiler getting TLE with cin\cout? What does "Normal" mean? On your computer? I think you know that CF servers are not your computer, maybe have different compiler options and for sure different perfomance. So if you see some weak parts of your code which can cause some negative verdict, you should perform actions to prevent it. I think none of people who was thinking about I\O time on contest and knew how to read and write numbers fast didn't have problems with it.
In my opinion, it would be more correct to say "Competitive Programming". Programming. So to participate well you need to know your language well: speed of I\O, precision of sqrt and all other features, which can be abused by problem's authors. And I also think that's sometimes authors must give problems which requires accuracy or maybe even additional efforts while using some usual built-in methods, so people know how does their language work and not just write some keywords having no idea why does it work.
I don't know what did you check, my last public submissions contain it. For example: 17076273
Normal means this one and it means on pretty much every Linux or MacOS computer(and probably any other PC that support gcc itself)
There's a difference between the language and compilers, you know.
Your submission was not shown in submission tabs because it's unofficial one anyway, you said you've used in
How can Div2 D be solved?
I solved it this way:
Notice that, no matter what operation you do, the odd and even numbers will always be in increasing order ({1,3,5,7,...}, {2,4,6,8,...}) (in a circular fashion), and the whole array will never have two consecutive even or odd numbers.
So you can keep track of where the 1 and 2 are after all the queries. Then you can deduce the position of the other elements.
Let’s notice the following:
Then all we have to do is print the offset values for each guy, remembering to do it in a fast way, as n can be big enough for iostream to be too slow.
Задача 641D - Маленький Артёмка и случайные величины
Посылка 17499640, использующая стандартный sqrt из cmath, получает WA 8.
Посылка 17499630, использующая вручную написанный m_sqrt бинпоиском, получает OK.
Уважаемые авторы задачи, вы действительно хотели, чтобы участники писали свой sqrt? Очень хотелось бы понять, ЗАЧЕМ в этой задаче такие ограничения, и какие неправильные решения они отсекают.
Стандартный sqrt не работает с отрицательными числами, даже если это, на самом деле, 0 — eps. Возможно, в вашем решении достаточно учесть этот факт.
Вы правы. Спасибо. facepalm
Why are we still not allowed to practice?
You can submit on VK Cup 2016 — Round 2. Note that the problem order may be different.
Что за 11 тест в задаче "C — Маленький Артёмка и Танцы"? Почему используя cin/cout я получаю WA, а с scanf/printf TL ?
Auto comment: topic has been updated by AlexFetisov (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем AlexFetisov (предыдущая версия, новая версия, сравнить).
I am not able to see others code. Is it just me or is it not unlocked yet?
newbie question: after contest, looks now I can only view myself's source code? when I try to click other people's submissions, I can not view the source code?
is there any way to view other people's source code? thanks.
I think soon it will be possible.
Контест в целом хороший, но ошибок бы поменьше, и было бы вообще здорово :)
WTF?! Is E is actually E?! I didn't read it during contest because I thought that it was something like Div.1 E. After contest I read it and just wrote solution in 5 minutes using
std::map<int, std::map<int, int> >.I will always read all problems during contest... :-(
Someone please share your code of Div2 C so that others can find answers to their test case.
Thanks.
My Code
Now we can see others code!
http://pastebin.com/Z7302WFz
for those who are having trouble in testcase 6 try this
correct output:
Почему не получается посмотреть коды других участников ?
Автокомментарий: текст был обновлен пользователем AlexFetisov (предыдущая версия, новая версия, сравнить).
@AlexFetisov: It should be noted that mkisic also solved everything within an hour :)
KILE ANIMAL!
Добавьте, пожалуйста, задачи контеста в Архив.
Problems were really good. but getting TLE (in problem B Div1) because of not using "scanf" was really unfair! I used cin/cout without syncing with stdio and got TLE...
I think something is strange going on in CF compiler or server. On my PC scanf/printf works as fast as cin/cout.
In Div-1 C, when we are solving the quadratic equation to calculate the probabilities of the two dices, can we select either one of the two roots as the required probability, or does it matter which root we select?
It can be easily proven (Well I didn't think about it, I just realized) that this equation either has one answer or one of its answers are not valid (and it is 0 I guess). But in the first equation there are two answers which are the two numbers we want. (Because of symmetry).
Many people failed this problem (including me) because sometimes we encounter sqrt(0 — eps) which is produced by double errors and the return value will be nan instead of 0.
How can we prove that only one of the answers is valid?
I didn't prove and maybe I'm wrong, as I said before I just guessed :-D, also I think if there exists another valid answer, we can continue from that and find anohter answer for the problem which is a valid one.
in problem B div2, when I run this code in my computer gives correct answer "INFINITE", but, when codeforces run this code gives "FINITE" and I receive WA.
this problem happens in the Test Case 2. someone can explain to me?
17484721
Change %Ld to %I64d.
Accepted
There is something that i thought was weird during the last round after solving the A&B problems it locked to try hacking other solutions and when trying to open the submission i couldn't so i tried to open and see the hacks and i could see no hacks was there something special about this round that i missed or was there something i did wrong on my behalf?
А что в топ-30 изменилось? Рейтинг пересчитали, на место хуже стали в контесте.
Hello , In the Problem Little Artem and Grasshopper.
I made 2 cases,
First case — When string's current index is having '>' as direction , then if this index + the distance he has to jump exceeds n-1. Then he will go out of the array.
Second case — When string's current index is '<' as direction , then if this index — the distance he has to jump is less than 0. Then also he will go out of the array.
But this logic is giving me WRONG_ANSWER on test case 29. Can anybody help me ?