Привет, Codeforces!
Мы рады сообщить, что 4 июня в 19:30 MSK состоится раунд Codeforces #306, авторами которого являюсь я (Адилет Жаксыбай), и Тимур Сытдыков (Timur_Sitdikov). Раунд будет рейтинговым для участников второго дивизиона, участники первого дивизиона могут, как обычно, поучаствовать в нем вне конкурса.
Хочется выразить благодарность всем тем, кто помог нам с подготовкой раунда: Максиму Ахмедову (Zlobober), который помог нам с подготовкой задач, Бекжану Касенову (BekzhanKassenov) и Сергею Лазареву (SergeyLazarev), протестировавшим контест, и Марии Беловой (Delinur), которая перевела условия на английский язык. Отдельное спасибо Михаилу Мирзаянову (MikeMirzayanov) за создание платформ Codeforces и Polygon.
Кстати, насколько нам известно, Timur_Sitdikov — первый участник с Узбекистана, принявший участие в подготовке Codeforces раунда. Мы надеемся, что все пройдет хорошо :)
Всем удачи!
UPD Разбалловка будет динамической.
UPD2 Разбор можно найти здесь.
UPD3 Поздравляем победителей:
Раунд закончен, спасибо всем, кто принял участие!
This will be my first Kazakh author contest :D I wish find interesting problems and many hacks ;)
This will be my first Kazakh author content :D I wish find interesting problems and many hacks ;) hahahahahaha pls aka.Sohieb downvote pls me upvote
contest*
contest* a,b,c;
It took me a while to notice what you mean xDDD +1
thenk yu vry muccc i lov yu
excuse me! maybe is not good place to ask but I don't understand: http://codeforces.com/problemset/problem/545/C
look at test case 7 why answer is 5? tree x=1 to left, tree x=41 to left, tree x=55 to left, tree x=59 to right, tree x=68 to left, and last tree with x=105 to right so we can cut down 6 tree and correct answer is 5 what's wrong?
tree x=68 cannot fall to the left because [59:66] is occupied with tree x=59!
UPD: plz ask such this questions in your own blog! ;)
OK Thanks
after 59 is 68, and I didn't get that
Could you please go to the appropriate tutorial page to discuss? http://codeforces.com/blog/entry/17982
Your previous round was easy ( Never mind. I love easy round :D ). Hopefully this round will be easy too ;) Wish you two good luck and prepare more rounds for us :)
I instead, hope I learn something new from this round, participating and finishing a round without progression is not much of a good idea.
or simply it's unrated for you...
It's weird that recently ratings don't update as soon as past and editorials (except PrinceOfPersia) come late! what are doing there??
UPD: 2 hours passed and we are stared at monitor waiting for raitings and nothing happened!
May be they are too busy to find the cheaters and eliminate them. It's an important task.
What methods they use to find cheaters ?
I don't know how they exactly find cheaters. But I guess, they may have some software which can find the partial matching percentage of pair of codes. Then they check the suspected codes manually to be more precise. But those are my thoughts.
even if they eliminate some cheaters, many cheaters are left (like bell-sama in previous contest)!
Why downvote him? He is right.
Wish a standard problem set with strong data set :P
Izi problem, izi life
Hard problem, hard life
It's maybe second Kazak contest?
It's maybe second Kazak contest?
It isn't Kazak contest, it's Kazakh contest
Also this contest is the third one)
Also, it is not only Kazakh contest :)
Asia Mix contest
Scoring?????????
This time they even not write that "scoring system will be announced later" ;)
Hope will be in div1 after this contest.
We all do :3 :P
Yes -_-
I know, I will be there :/
But just for 1 round :(
I do not have to hope. I know I will be :D
Fake contestant spotted.
Sherlock holmes spotted!!
You're not wrong. My deduction skills are not bad actually, but I can't take credit in this case ;)
Why so sure? Are you from div 1 and opening a new ID to attend as a div 2 participant? :P
Do you have any doubt?
I'm just poking him :P
As usual many fake div2 participants. So unfair.
Yeah, frustrating for noobs like me!
To me is no change , after all it happens everywhere .And it can excite me !!!
Life is unfair man ! you just gotta climb up to div 1 and i don't think you'll see any fake participants!
Why do they need to participate from fake profiles ? That is the question.
it's just exciting xD
Why It's exiting?? beeing the first when you know and frustrating other??
Example
Why would you attach a link to this very page? -_-
Keep trying and don't care about that!
Loved your previous contest! I hope I can do better in this one. :)
Problem D is nice, I like it.
Unable to submit :( Codeforces temporarily unavailable, it says :(
First experience with dynamic scoring, it was different and I liked it.
So many hacks with
ABAABandBABBA!I'm also wrong.
Yeah...with that particular test case I got 12 successful hackings :P
My solution also got hacked . I resubmitted it lets see if it passes system testing .
I figured the hack 5mins before contest ended. Coded it right in time, but not fast enough to submit
Who is stdioH? He or She regestered 12 hours ago
Thanks to authors for problem E, it was really nice!
Could you please give an idea of solution?
If last symbol is 1, then impossible.
If sequence ends with 1, 0, then result is always 0. So we will try to make
at the end.
If sequnce consists only from zeros, and number of zeros is greater than 2, whe can place second and third from the end zeros to the brackets:
If sequence suffix is 1, 0, 0, 0, ..., 0, where number of zeros at the end is greater than 2, we can place brackets in a such way:
, and now sequence ends with 
, so result is 0.
If sequence suffix is 1, 0, 0, than there are two cases:
1) If there is no other zeros in the sequence, answer is NO.
2) If there is at least one zero, which differs from zeros at the end, we can place brackets in a such way in a suffix which starts at the last of such zeros:
.
UPD: It was a mistake in last case, but now it seems ok.
it's not that complicated you can just do this
if(lastone == 1) NO calculate ans like this ((1 -> (2 -> (3 -> ...... n — 1))))))) -> n) if its 0 then nice else you can't do it! the proof is that i got my E accepted
Doesn't look like a div2E like solution at all :p but good thinking, I guess.
It seems that my solution does such thing in all cases, lol.
You can gamble in div2 when you're in Div1. Div1 guys have all the fun.
Damn, its so easy solution. Thx man :)
Tried to solve it, but failed on pretest 7, idk where I've got it wrong.
Am I right so if the sequence doesn't end on 0 its impossible to get 0 with this sequence?
yes, you are right But that's all I thought up:D
i also got wrong ans on pretest 7. following are all the conclusions i could make: (assuming array name is a[] and size is n) 1. if(a[n-1]==1) ans will be NO 2. for inputs like: 1(1)*00 ans will be NO 3. for all other inputs ans will be yes
For YES, output pattern is like this: 1. if a[0]==0 and a[n-1]==0: 0->(...)->0 2. for patterns like 1(1)*0(0|1)*0, output will be: [any arrangement for 1(1)*]->(0->[any arrangement for (0|1)*])->0
I don't know what other cases I am missing. Any type of help is most welcome.
Nice problems!
There were often not available to submit or to see someones code in the last 10 minutes.
Как решать D и E?
Я в Е подумал, написал такое решение: если без скобок все ок, то ок, выводим ответ. Иначе ищем выражение вида (false)->(true/false)->0, где false и true — выражения без скобок. Затестил на n ≤ 10, все ок, отправил, зашло.
Наверное, в D есть много разных решений. У меня такое:
Если n = 1, то выводим то, что в семплах. Если n делится на 2, то выводим
NO(это можно доказать).Иначе сделаем четыре полных графа A, B, C, D с n вершинами каждый (у вершин будет степень n - 1). Добавим ещё вершины x и y. Теперь из A и B соединим (n - 1) / 2 вершин от каждого с x. Те вершины A и B, у которых осталась степень n - 1, соединим попарно. То же самое сделаем с C, D и y. Наконец, последним ребром соединим x и y.
Одно из возможных решений по D
Why is it that always the contests with dynamic scoring are some kind of weird ? :D
how to solve E??
try figuring out what's gonna happen if: last number is 1 last number is 0 first number is 0 first number is 1
after some thinking, you'll get the idea :)
Problem A is very nice. Short problem statement and a lot of hacks. Really enjoyed it! :D
Is 0 a valid input on problem C?
yes
It is non negative without leading zeros. I think it should be valid input.
i will get a wa on problem A
i could'nt submit my code in the last 5 min :(
I cannot hack other either. I guess there were too many submissions at that time so that the server couldn't afford.
I did 2 mins before the end !
I could not even pass the pretests of problem A. I believe I understood the problem wrong the whole time. Can anybody tell me what did the problem actually mean?
Such misunderstandings ruined my contests too many times during past. Apart from this, I do a lot of silly mistakes like, not noticing constraints properly, forgetting long long, giving less size to arrays or vectors (even did this today at problem B :D ) and many others.
I am just getting accustomed to be a freaking block-head-dull-brained person all the time.
Happy! ^_^
I found that my solution of A is completely wrong after locking the problem! -_- howeever, the problem says to check whether the given string contains both AB and BA as a substring. and AB and BA should not be overlapped (like ABA )
I have seen the pretest #4. It was
ABABABYep I thought that NO
ABshould overlap with anyBAand vice-versa.Lots of construction algorithms! Nice round!
How can I solve problem D?
for even k does solution exist ?? if anybody could tell it will be helpful
Nope, for even K answer will always be NO
I read a homework question and answer pdf of MIT, and it was mentioned that there does not exist any solution for even degree of all vertices, during the contest.
Currently could not find that link, will post as soon as I find it again.
Are there any solution exists for even N in Problem D?
I also could not find any ;(.
It can be proved that there are no solutions possible for even N.
nope. if every vertex in a simple connected graph has even degree, it can be proven that the graph has an Euilerian circuit. so all of the edges of the graph are at least in a cycle. so there are no bridges in this graph.
I proved it without the help of Euilerian circuit.
Assume the graph has n vertices. Then n*k must be even. If we have a bridge break the graph into two parts(one has a vertices and the other has (n-a) vertices), then a*k-1 and (n-a)*k-1 must be even too. So the only possibility is that n is even, a and k is odd.
Thanks. I just solved it. I was so close. Tricky problem :)
Another way to think about it is like this: Look at the right side of the bridge, without considering the bridge. The degrees of that subgraph, if it existed, would be k-1,k,k,k,k,k,k,k... Since k is even, the sum of those degrees is odd. In every graph, the sum of degrees must be even, so we win :). Edit: Practically the same as boleyn.su, didnt update fast 'nuff.
I also thought that way. But I took too much time to find this.
Can't find it on paper, but also couldn't prove that its impossible, so just give up and moved to E.
Assume that such a solution exists. Consider its "left" part from the bridge and including the bridge vertex. k vertices in this subgraph have degree n and one (the bridge vertex) has degree n - 1. So, the total number of edges in this subgraph must be
But since n is even, the numerator is not divisible by 2.
Thanks :)
i locked one of my solution to hack others :D and bam... my solution got hacked :'(
With new feature of highlight code did impossible to hack for me, it was very slow, sometimes did not show the code :S. ¿ Anybody had the same problem? I use Firefox.
I love the new feature :D, just I have that observation.
Problem A is so amazing, until in System testing :D
Editorial ? :D
!!!!! my A got WA !!!!! what's wrong with test 8 ? The answer is obviously YES why do they expect NO?!?!?!?!?!
As I see, Test#8: ABX repeaten many-many times. It contains AB but doesn't contains BA
Is there any "BA" in testcase 8? If not, then it's NO.
I think there is: ABX A B X AB
the first two ones and the 5th and 7th one make : ABBA
They must be beside each other.
So you can't take the fifth and the seventh one.
(They are looking for substring, not subsequence)
I'm afraid you misunderstood problem
It says to find substrings "AB" and "BA" that not overlape. There isn't substring BA in test#8
Thank you :|
pnnb1997 — How did your submission 11416298 with worst case complexity O(n^2) for question A passed System Tests? :O . Also i can see that there is a test like "ABXABXABX....ABX" just to make sure that O(n^2) with pruning like yours gets time limit exceeded .
It didn't pass system tests and it's O(n)
which submission r u seeing? Maybe i made some mistake in posting the submission link which still seems fine to me. I can see in green letters "Accepted" verdict there!
You're right.I was totally wrong
on problem A
ABABAB => YES ?!
Are you serious? you have only overlaps!!
A B A B A B
so why is the answer to test 8 NO?
is that a sub-string ?
Fuuuuuu...!!!! I hadn't read the problem statement well :((
I think you misunderstand the problem, the two substrings that you find should not be overlap.
For example, you can find such answer:
AB*BA*They don't overlap.
What time does regexp require? 11433753 Is there any way to make regexp works faster in Python?
It was supposed to be O(n*s*_a_) where n is the length of the string, s is the number of states of the NDFA and a is the average number of state transfer edges. However, it seems that Python implemented it another way.
Your regexp has very big time complexity. Try to make it more efficient. Later you can see my submission with regexp in 31 ms (that's because of compiler's optimization).
The problem is backtracking, I modified your solution to prevent it. You can check it out here:
http://codeforces.com/contest/550/submission/11443577
Can somebody please explain dynamic scoring to me ? Thanks
Look here: http://codeforces.com/blog/entry/4172?locale=en
Thank You :)
how to solve b and c?
For B, you need to try all possibilities which are 2^N. For C, what you need to know is that a number is divisible by 8 if the number formed from its last 3 digits is divisible by 8 which means that if there is a number with K>3 digits divisible by 8, then there is also a 3-digit number divisible by 8. So you need to try all possibilities for 3-digits numbers, 2-digits numbers and 1-digit numbers.
im going to give you a hint on problem c to not spoil it.
c-> you just need to know that a number n is divisible by 8 if and only if its 3 rightmost digits together are divisible by 8 For example for the divisibility of 3213123123213888 you just have to check the divisibility of 888 which is divisible.
Запорол правильное решение D, так как не выводил YES и сделал тупейшую конструкцию for(int i = 0; i < (k — 1) / 2; i += 2), где надо было i++ или (k — 1)
А какой у вас опыт затащенных контестов?
Why the stoi function not working in GNU G++ 11 4.9.2 :( Due to this I'm unable to submit at last minute. And when I uses stringstream my solution accepted.
Codeforces doesn't use a 'real' g++, but rather MinGW (a Windows port which has several bugs, including missing stoi and to_string functions).
yeah, MinGW bugs, which annoyed me when I want to use stoi and to_string()....How to fix these bugs, I tried but still not work
My worst contest YET!!!!
my A, B got WA!!!!!!!!!!!!!!!!!!!!!!!!!
but glad C, D are AC!
How it is worst? You have been able to solve D first time I think, I engrossed so much in Hacking, I read problem D little late and could not generate regular graph in time.
problem D was our homework some months ago!!
The exact problem D? Can you provide some link of some kind of resource? That would be helpful indeed. :)
Hey guys, editorial was posted here
I think it has a typo. It is showing dp[i][ai mod, 2015 - 06 - 04 8] = 1 instead of dp[i][ai mod 8] in the 550C.
Update the ratings man, so I can go to sleep.
Does anyone solved A using regular expression, I tried to solve A in this way instead of simple one. Forgot that regular expression takes exponential running time.
Does codeforces not support "to_string" function ? I get compilation error even with C++11 . http://codeforces.com/contest/550/submission/11434694
Compilation error is
program.cpp: In function 'int main()':
program.cpp:40:25: error: 'to_string' is not a member of 'std'
string temp=std::to_string(i); ^Yes. I think there should be a warning similar to the one for '%lld'.
Read the second answer here http://stackoverflow.com/questions/12975341/to-string-is-not-a-member-of-std-says-so-g It will work with C++11 on CF. I used it in some other problem yesterday.
my solution gives a weird runtime error for C — problem with error code -1073741510 both in my compiler and on CF but my compiler runs the code and gives this error as warning . http://codeforces.com/contest/550/submission/11430760 can anyone give any insights?
Holy mother of unreadable code...
Dude, i dont know anything about the runtime but as a friendly advice, i think you should code a little bit cleaner so atleast you can understand your own code. i closed it the moment i opened it.
sorry for being a little too straight.
Do you write code in Notepad?
Yes.gradually trying to move to codeblocks
O_O
O_o
o_O
o_o
0_O O_0 o_0 0_o 0_0 O_o o_O O_O o_o
In div2 A, I wa on the ABAB so sad.. D & E 's constructive algorithms is very ingenious! Have fun in this round！
^thanks shervin will take that into account in future :)
I love this contest because of very short problems without very long story.
Plz Give Rating.Wait a long time.
It is 2:45 AM, BST. Still waiting for rating. Tomorrow morning I have an internal practice contest. So, I should sleep now. :-)
Still awake for Rating and feel bored.
Hope I will become #Candidate_Master today. Nice problem set. Enjoyed very much :-)
Yeh!!! I made it. Now I am #candidate_Master. Hope I will become Master within 2 months. :-)
Congrats :)
My submission for problem C gave wrong answer on test case #22 but the same code gives different answer on ideone.com and my home compiler which is correct. Please tell me what is the issue. My Submission for contest : http://codeforces.com/contest/550/submission/11436093 Same code with test case 22 on ideone : http://ideone.com/Y82K0r
Most probably precision issues due to pow method, try resubmitting after writing your own exponentiation method using fast exponentiation in O(logn)
Don't get inspired by codechef. Please update the ratings ASAP.
Problems A, B, C very easy.
maybe you forget that this is div2 round o_o
Problem E was also easy. I couldn't solve it during the contest due to my own silly mistakes. Solved it after the contest
Two and a half hours after contest and rating...........
.
1700!
I Love This rate
A, C and E solutions with regexes: 11433416, 11435544, 11438339. Update: obsolescence's solution E — 11442038
For D, I constructed the graph like described here:
For k=99, it produces 965448 edges, so it is still within the constraints. Being correct, nevetheless, my submission 11429811 timed out. Guess it is just a problem of optimizing output.
I solved problem similarly. Use
ios_base::sync_with_stdio(0). Output is very big.My submission: 11424571
It is still too slow for his solution, proof:
http://codeforces.com/contest/550/submission/11444006
Iostream is slower by an order of magnitude in certain cases and there is no way around it.
#define endl "\n"and you will get accepted =) 11444087Still takes 150% more times the time though.
This is why I never use cin and cout, they are too slow! Here, I rewrote your solution using printf statements and it passed in 340 ms!
http://codeforces.com/contest/550/submission/11443935
Thank you, JohStraat, very interesting. I learned my lesson!
Congratulations to the winners!
Div.2 winners:
mff
I_love_Ngoc_cmn_Thuy
goodhope
kiana810
xwind
The correct rating::
1st place (mff)
2st place (I_Love_Nodir.Daminov)
3st place (tun)
4st place (I_love_Ngoc_cmn_Thuy)
5st place (goodhope)
Congratulations to these actors for a successful result in Codeforces Round # 306 (Div. 2)
Just added winners to the post. Congratulations!
Thank you all guys, who participated in contest! It was fun for us :)
I am getting an error on problem D "wrong output format Unexpected end of file — int32 expected" what does this mean , can anyone help (http://codeforces.com/contest/550/submission/11450063)
D: my experience is low , if I can master more about graph , I believe I will enjoy more,
Sorry to take part in it late. I feel this is one of the top competitions I took part in. Requires no complex knowledge of algorithms and still the problems were tough. Thoroughly enjoyed the problems. Specially surprised to find red coders getting problem A wrong.