У меня середина сессии, но я все равно пытаюсь готовить Div.3 раунды.
<copy-pasted-part>
Привет! В 18.12.2018 17:35 (Московское время) начнётся Codeforces Round 527 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</copy-pasted-part>
UPD: Также спасибо Роману Roms Глазову, Farkhod Farhod Khakimiyon и Alex hohomu Poon за помощь в тестировании раунда!
UPD2:
Поздравляем победителей:
| Rank | Competitor | Problems Solved | Penalty |
|---|---|---|---|
| 1 | Doma_Umaru | 6 | 331 |
| 2 | BigDelta | 5 | 141 |
| 3 | AbduM | 5 | 262 |
| 4 | PauloMiranda98 | 5 | 266 |
| 5 | Fill_in | 5 | 276 |
Поздравляем лучших взломщиков:
| Rank | Competitor | Hack Count |
|---|---|---|
| 1 | MarcosK | 84 |
| 2 | hmducanh | 67:-4 |
| 3 | jsuyash1514 | 58 |
| 4 | Warawreh | 29 |
| 5 | darkness_peach | 25:-2 |
Всего было сделано 796 успешных взломов и 2063 неудачных взломов!
И, наконец, люди, отправившие первое успешное решение по задачам:
| Problem | Competitor | Penalty |
|---|---|---|
| A | lee_chaerin | 0:01 |
| B | ajarindong | 0:02 |
| C | BigDelta | 0:15 |
| D1 | Sad_reacts_only | 0:26 |
| D2 | bigbigbigcat111 | 0:40 |
| E | Patunia | 0:24 |
| F | Patunia | 0:12 |
UPD3: Разбор опубликован.
anothert trashforces made by trash russians
The legendary grandmaster Intellectual said! Oh wait...
Jokes aside, it can be very usefull for those who are slightly weak at maths or have no experience of solving algorithmic problems but want to practice in coding. And imho even for some 1600+ last problems are not such a trash.
meanie
Last line increased my expectations for the round.
div1 + div2 = div3
I guess you inspired them :)
yep
Lol really good joke. But, surely, I did not expect such a difficulty. I'm very sorry for such a hard problemset
I don't have the right to complain more, because I'm out of the competition, but, for me, really enjoyed it. Thank you!
Good luck in your exams! vovuh
Thanks Man! I just wanted another div3
it is raining contests
3 contests in 5 days
Good Luck!
And guys, that's how
<copy-pasted-part>becomes a legend.Cool! Long time no see the Div.3. I hope I will have fun in it.
I really like this Div.3 because I am a new hand absolutely! Thanks to the beloved author and say good luck to everyone who take part in this match!
Я посмеялся =))
What does trusted participant mean. Plus how to hack solutions of others once if we submit the solution
you_paison, there's a link on "Remember that" in the piece of the text about trusted participants. There you can find the definition and the motivation of this term.
5+2 = 7 Seems a lucky round! #527
UPD: NO, it was'nt :(
That reminded me of 1058C - Vasya and Golden Ticket.
hope that i can be blue :D
C is a pretty weird problem for me :( i tried to solve it with two different algorithms but all failed even though i knew how to solve it
Long way to go before blue, you will have to master all the elements.
Nah there's nothing special about blue, we are still clueless
Probably, participants from the first division will not be at all interested by this problems
Probably they even can't solve them.
Даа, сложный контест получился. Разница между задачами С и B слишком большая, а между D и C все больше. Все равно спасибо Vovuh за хороший контест.
Is C checking the possible 4 strings?
Yes, that's what I did.
Checking 2 strings is enough. We have two longest (n-1 length) strings.
One of them would be prefix and another will be suffix. Therefore, we can just guess one to be prefix and add a single char — last letter of another longest string — to the last of what we guessed. And if it isn't the case, we can do it again with another guess.
This is valid because it is guaranteed that there is an answer.
What is test 17 in C ?? I could not pass it. I firstly found strings of length n-1 in the input data and then considered if one of them could be a prefix of original string . Once I find that which one is prefix of length n-1 we can get the answer string but I can't understand where am I wrong MY SUBMISSION
i solved it in the same way but getting wrong answer on test 17 .. i don't know what is the issue , i tried many different approaches all of them failed on test 17... let us assume i found the right string then i will iterate over all the prefixes and suffixes and store them in a vector in the form of pair of string and character and finally printing by just iterating over the input data and checking the other part of the pair and in case prefix == suffix i am handling that case too.
edit: i was using find function to match the prefixes and suffixes which may fail for the case where it have different suffix(or prefix) but it matches with prefix as it is there so instead create another vector to store all of them and match them one by one this helped me :) hope this may help to others who failed on test 17...
I had the same mistake. Once you check for a string, you have to double check it before printing it as an answer. Check my submissions for more:
WA on TC 17 — https://codeforces.net/contest/1092/submission/47208703
AC — https://codeforces.net/contest/1092/submission/47213730
sad part is it has nothing to do with the logic just a blunder !!! check mine exactly same mistake :((((((((((((((
Can you provide a example test case I am not able to understand what you are implying.
i have solved it like that but then also my solution has been hacked ...don't know why ??
wasn't div3 supposed to be easier then div2?
Is this a joke? The difficulty level rises up like bitcoin! Come on
Understood that reference. Let me make it more clearer
Difficulty level of the reference roughly matches difficulty level of the problem set.
how to solve D1 and D2 ?
D2 can be done using stacks.
how ?
Here have a look at my solution
Solution
So while putting elements in the stack if it is equal to the previous element then you can raise it to any ht required so remove both from the stack but the ht cannot be reduced so just keep a check variable for that.
Now if the final size is 1 or less it is possible else not.
convert each a[i] to a[i]%2 and then use almost logic of D2 for D1. D2 D1
Good solution but hacked.
Sed_Lyf
what was test case 6 for problem 3?
https://codeforces.net/contest/1092/submission/47223304
I think the hidden string is something like aaab, because considering aaa as sufix and aab as prefix will fail.
i attached my code . Please refer to it once
Sorry, I didn't know what's the issue.
i think problem c and d hard for div3 ?
What is test 17 in C ?? I could not pass it. I firstly found strings of length n-1 in the input data and then considered if one of them could be a prefix of original string . Once I find that which one is prefix of length n-1 we can get the answer string but I can't understand where am I wrong MY SUBMISSION
47221338
Why did this fail?
Problem E is IOI 2013 — Day 1 — Dreaming
Also, how to solve D1?
In D1, from some state you can always add verticals on any column for as much as you'd like, since anyway you can return to the state before with all columns being increased by some constant C (which makes no difference).
Therefor, you can always keep at a state where the difference between the maximal and minimal column is less than 2, this implies you can take all columns modulo 2.
I used stack for D1. Because we can vertically add a block, the number actually doesn't matter — only its parity does. I just checked parity every time I get an input and if i-th element has same parity with i-1 th element, both can be raised to arbitrarily number, so I just ignored them.
At last, if we have one or zero element left, we can complete the wall. Else, we can't.
This was my idea, but I'm not really sure if this is correct or not. Plz teach me a lesson if you found something wrong :)
I passed pretests by keeping a queue of all possible consecutive indices whose values have the same parity because they can be made to reach all possible heights. Removing a pair might add a new pair in the queue if then consecutive indices have same parity. If at the end, we have exhausted all possible indices except possibly any 1, then answer is yes, else no.
:(
Не посинел, потому что не успел наложить кирпичей
I think this contest is div1+div2 combined !
I think problem E can be solved in O(n), though I submitted an O(n*n) solution.
Yes, you can solve it in O(n). Check out Dreaming from IOI '13.
I solved it in O(N). https://codeforces.net/blog/entry/63911?#comment-477736
How to solve F ?
Hint: Calculate values for each of the nodes using DP. Firstly calculate the value for just the subtree for each node using subtree values of the children. Then, calculate the complete value (for subtree + other nodes) using parent node complete value.
Me after open the scoreboard for today Div 3 round:
How to solve F?
I was trying to find the two nodes which lie at the diameter of the tree, I assumed that either of them will be the answer, but it was not to be. Can someone provide with a small test case where this assumption fails?
Testcase: If diameter has the largest weight and rest are preety small maybe. Hint: use DP.
Problem D is a pile of bullshit.
Considering the low constraints, I don't think C was tough, it was good enough for Div3. I can say this until my code is not hacked. :P
Felt same here. Initially I thought C was too tough for div3, requiring trie and some other skill. But I think 100 is fair constraint... Still I'm not sure before systest and hacks end :P
Is there any penalty for unsuccessful hack?
no. div3 and educational round hacking has no effect on rating
Anybody have idea for D1 pretest 9?
You can check this testcase:
For D1 :
When seeing problem C — F :
D1 wasn't easy at all it's harder than most of div(2) C :/
Maybe he tried to troll div 1-2 participants who tried to solve from the last problems.
actually all div3 contests sucks they always fail to make a balanced problem set and I will never participate in a div3 round again
Whoa, challenging round for cyan here :) However, I really enjoyed. Although generally people here felt this was harder than how div.3 should be, I think it gave me more "doable" challenges than div2 rounds did. (Generally I couldn't even submit for problem D on a div2 round ...)
Thanks for vovuh and whoever worked hard to prepare a round, and to the community for giving wonderful oppertunity to enjoy problem-solving.
Hope no systest failures or hacks kill my rating xD
in problem C, test 17 gave me WA and when i changed the order of processing the input, it got AC. i don't know why. please someone help...
code1: https://codeforces.net/contest/1092/submission/47224002
code2: just by changing the order https://codeforces.net/contest/1092/submission/47227536 please someone check it...
I have the same problem with test 14. I just changed order of appending strings with length 1 and length (n-1). Pretty sure that test for problem C isn't covers all possible answers.
your code will probably get hacked
Me to, i wrote cout<<"P" (or "S") and got wa on 17, but when I switched up and put answer in string, I got accepted.
yes me too
Вопрос по взломам: они влияют на результаты матча или просто for fun? Какие бонусы/пенальти за успешный/неуспешный взлом? Если влияют, то справедливая ли это система? У меня, к примеру, нет возможности продолжать участие после окончания соревнования по причине нехватки времени, а кто-то может и 12 часов сидеть взламывать. Спасибо.
Because I'm so stupid, I can not do C problem
What is the test 12 in C ? https://codeforces.net/contest/1092/submission/47223481
https://codeforces.net/profile/sxzdsb this guy has inserted if(n==66) print(some random no) into his code. please admin look into this
Though above the Div3 level, the problems were really good(I read A, B, C, F).
Can F be solved by doing multiple DFS?? Basically, after finding the answer for 1 index as root through 2 DFS, I tried to do another DFS and pass some parameters to check for it's children, but couldn't implement it in time. Am I thinking the right way?
yes if you use dp with 2 times dfs.
Yes. After finding the answer for an arbitrary vertice you can calculate the answer for any children of this node in constant time. Basicaly, when you move from from a vertice u to a vertice v you have to decrease the sum of values of all subtree of v (because the distance has decrease by one) and increase by the sum of all others nodes that doesn't in subtree of v (because the distance to this vertices has incressed by one).
I think it should be subtree of v instead of subtree of u in ur explaination.
Thanks, i fixed it :D
Yes, exactly the same idea (I used 3 dfs's). I implemented in time, was unable to debug a wrong indexing in dfs in time :(. It got accepted few mins after the contest got over... My submission: https://codeforces.net/contest/1092/submission/47228524
Thanks! :)
Was this really for Div3 noobs?
Nope
Penatlty for unsuccessful hack?
nope!
"And for 1600-1899 the problems will be too easy."
I missed a really good contest because of this line :(
That moment when you submit a bunch of bullshit code in C and you get accepted.
https://codeforces.net/contest/1092/submission/47222677
Someone please hack me , end my suffering :p
I give it a chance of 70% to be hackable.
UPD : i got accepted lol.
5 atmx a at tmxk mxk xk k atm for this test case your code gives segmentation fault..still unsuccessful hack
Use custom invocation , the segmentation fault was probably caused by the compiler you are using.
Hi, Can someone please help me out with the solution for problem C? I got wrong ans on test case 17. After contest i swapped the order of processing the longest string and submitted and got AC.
I think verdict is wrong. I had same problem and checked TC 17, it's oyyyyyyy.. (with 99 y). I checked on notepad and it's correct in both order (yyyyyyo or oyyyyyy)
I think you are wrong. I checked your solution on the following case:
5
a
aa
aaa
aaaa
b
ba
baa
baaa
And it printed
PPPPSSSSwhile only one suitable string is "baaaa". So...Checked again and I might be looking some suffixes in reverse way :P
Are you trolling me? Or what are you trying to say? I checked all your wrong submissions for this problem in custom invocation on this test and they're returned the wrong answer (in my and checker opinion).
I'm not trolling you, was saying what was my mistake. Here an example: for aab, ab is suffix but when I was checking, sometimes I was looking it as "ba" (in custom inputs)
Oh, then I'm sorry, I didn't understand you correctly.
I had a similar situation as yours. If you are only checking for prefixes and assigning the remaining strings suffixes then it becomes important as to what you choose as prefix. Out of two largest length strings, it may seem both can satisfy prefixes but only one can satisfy suffixes. So as you change your order of processing, you may get AC on a wrong TC as you are changing your prefix. But you need to check suffixes also.
Any Ideas for an O(N) solution in E.
https://www.quora.com/What-is-the-solution-for-Dreaming-on-IOI-2013 The answer on quora is pretty good.
My solution
thanks apparently i had the same code implemented during the round but had a little bug :p
I tried to make strong tests — he said
he also said that he copy-pasted.
https://codeforces.net/contest/1092/submission/47229976 The solution for D2, Can this be hacked. Just got hacked in my original D2 solution and found my mistake, I was just missing one simple condition. So I wanted to know can this be hacked now. Thanks
VERY HARD DIV3!
Saw a lot C's solutions are getting hacked. What are the hacks for C?
I did one using this:
4
a
c
ac
ab
aba
bac
I got WA at test case 17 but getting PSSPPS for this. Is that correct?
yes it is correct!
How to solve C Question? I'm guessing the full string using prefixes and suffixes of length n-1 and then if any string is a prefix of fullString it is assigned P and other one of same length is assigned P! I'm always failing on test 14 Please help!
My Submission
in short:
From the input you can get 4 candidate strings from which the suffixes and prefixes could come from. These 4 string are )for instance) combinations of 2 shortest and 2 longest strings from the input (shortest + longest or longest + shortest),
Just check among these 4 a valid one and you solved the classification problem.
Or you could just form 2 strings. Take the largest strings among the input strings, suppose s1 and s2. Two strings to be checked are:
s1[0] + s2
and
s2 + s1[s1.length()-1]
Example: 5 ba a abab a aba baba ab aba
In this merge abab and baba to form: "ababa"(from a + baba) and "babab"(from baba + b) and check these 2.
This works because the answer always exists.
Yeah, actually this (your) is the solution I implemented, cause you just need to check 2 strings so I assumed it would run faster. Maybe my first explanation is a bit more intuitive,
I have done the same in my submission!
I can't figure what's wrong!
Can any of you helpout?
Cheaters on problem D2 Duongcvp , duyleson76
47217201, 47216097
UPD: vovuh pelase look into it.
Thanks! I informed Mike about it, we will do something.
The rate at which my rank is decreasing, after 8 hours I will be rank 1.
Sorry, of course, but why is C such a slop? Maximum unpleasant. Do you like to give such tasks? ...
I dont think all the possible answers are provided in each testcase for checking. For example, in test case 19: 5 ba a baba a aba abab ab aba
Either ababa or babab can be the possible string. Thus, the possible answers are SPSSPPPS and PSPPSSSP respectively. But when my code output PSPPSSSP, the verdict was WA. Please look into this.
My submission: https://codeforces.net/contest/1092/submission/47238081
ba can’t be a prefix
All Prefixes should start with the same letter. In your output they don't.
Thank you @Hasan and @ShowStopper728 for replying. My case itself was wrong. Understood my dumb mistake.
can someone explain why i fail test case 9 on D1? thanks.
submission 47221085
can someone explain why i fail test case 12 on C ?thanks. submission https://codeforces.net/contest/1092/submission/47223481
Apparently according to the judge, it says "The number of 'P's and 'S's should be one and one for length 1". Maybe your output marks both strings of length 1 as P or S. One should be P and one should be S.
When you check the Ps it seems you are assigning prefixes too early and leaving invalid suffixes
Man I solved problem C using DP , I was so proud because no one else did it that way (that I know of) and then I got hacked :( bummer, but of course I got hacked I didn't take into account at the last step of the DP to check that the remaining suffixes were valid , :( I really feel so hopeless about this contests I just get crushed over and over again, well at least I solved it using a different approach.
I used DP too. I hacked myself with the same test I used to hack your code :P
Yeah I should've totally took into account that checking of suffixes :(
very weak pretests ever!! two of my solutions were hacked. This isn't fair actually. -_-
Fun fact: I hacked at least 40 submissions with a test that hacks my own submission for problem C :P
What hack did you use?
I think test case #17 for C is wrong.
You should have a look at this comment ..https://codeforces.net/blog/entry/63911?#comment-477530
I still don't get it.
The div3 is very good, E & F is about tree, let's know how to get diameter of the tree and how to construct the shortest diameter. and F is also nice, is similar with fermat point problem. https://www.lintcode.com/problem/fermat-point-of-graphs/
Thanks vovuh
and thanks to MikeMirzayanov also.
System test did not happen? Or if it is going to happen, then when?
fastest system test already done.
Where is the rating changes
I don't think that problem C is that hard solely because of constraints on n <= 100. Just find the strings of length n — 1 from the input. Consider one to be prefix and other one to be suffix. Find all other suffix and prefix strings from these strings and check wheather theses strings matches with the input , if not then the other possiblity must be the answer
i even think that F is easier than C
When is the rating going to change??
For problem C — Prefixes and Suffixes, my submission 47235377 got a MLE by using the built-in C++ sort function.
On the other hand, when replacing sort with stable_sort, the solution is accepted with only 200 KB of memory consumed 47237954.
Does anyone have a clue why this is the case?
Thanks in advance.
Your compare function has undefined behaviour. Change
return a.Id < b.Id;toreturn a.S.size() == b.S.size() && a.Id < b.Id;and you will get AC :)Indeed, it gave an undefined behaviour. Thank you for guiding!
isn't its a rated contest ???
why its took so much time to changing rating ?
am i the only one who hate > 1 question mark ?
I have one solution of C.Find two strings of length (n-1), assuming they are prefix and suffix, or suffix and prefix. Then let the other strings match the two strings. Because each length has only two strings, one is the prefix and the other must be the suffix. Because the problem must have a solution, if the first case is wrong, the other must be correct.
Why in test 23 of problem C, checker of system report "Runtime error" 47214009, when in my IDE or Custom Invocation, my code is alright with that test. (Test 23 is special case, so i can creat it myself). This is my code, include test 23 in input: https://ideone.com/PB83La
vovuh Can you check the checker of problem C again ? Thank you!
Test 23 has the following pattern:
a
aa
aaa
...
aaaaa...aaaaa
a
aa
aaa
...
aaaaa...aaaaa
Your pattern of test from ideone not matches this one. Anyway, I copy-pasted 23th test from polygon and checked your solution in custom invocation and it gives WA.
I had read my checker in about 20 times. It is correct.
mistake is in your code.
check this in your sort comparator :-
return (a.X.length()>=b.X.length());
remove the equality sign and you will get AC, like this :-
return (a.X.length()>b.X.length());
for more details refer strict weak ordering
Amazing ! Thank you so much, i never know about that.
What means terms "improper prefixes" in Problem C? I guessed it means words which are not prefix of the given string.
Prefixes which have a length less than the length of the string
Thank you! Is it a math jargon? It confused me a lot.
Hi fellows, Why I still can not see my rating change of this round now?
Please update my rating for this contest, user name: dileepjallipalli29
It'll change all user's rating at the same time. But not yet.
It's been one day, no food, no water, no sleep. Still waiting for the rating to be updated
I am getting a Runtime error on test 4 for C. Can someone help? 47229206. I am guessing the word since we know both the suffix and prefix of length n — 1 , and then assign 'P's and 'S's accordingly.
maybe variable word is empty.
you can check it with asserts:
try submit this code.
Are the ratings for this contest has been updated?. Because I can't see any changes in my ratings. I took part in this contest and solved 2 questions. Please update the ratings!!
Editorial?
deleted
deleted
y the hell is it taking this much time for changing ratings ?
Fastest system testing ever plus slowest rating update ever in my codeforces career.
Can anyone explain problem E?
For each Tree, find its center (find the diameter first, and take the node in the middle of the path, that's the center). Let Cx be the center of one of the trees with greatest diameter. Now add an edge between Cx and every other center found, now you have created another tree in which the diameter's length is minimmum. Finding all centers can be done in O(N), and finding the diameter of the final tree can be done in O(N) as well, so the overall complexity remains O(N).
thanks a lot!
E — невероятно-красивая (хоть и баян).
The problem C is not so hard as it seems in my opinion, I solved it in the folowing way : take the two sequences of length
n - 1, one is suppose to be the prefix and another the suffix of the original string and the original string is eithera[0] + borb[0] + a. Just try both possibilities and take the good one.When taking
a[0] + byou should check as well if the letters in a from position[1, size]are equal with the letters in b from[0, size - 1], same goes forb[0] + a.Hope this helps somebody, for more details take a look at my submission.
Here I have written my approach to solve problem F: [Editorial] Another Solution to Problem F(1092F) from Codeforces Round #527 (Div. 3)
Oops, what wrong with the winners? It seems to be Doma_Umaru only got rank 5 instead of 1 (I found on his/her profile), and absolutely_bu01th4nh got rank 1?
The ones that don't have rating are excluded.
Wow, new fact!
em rank một mà bọn nó đéo cho em rank 1 lên trang chủ anh nhị ơi
vì cái tên của em nó như bu01
em tên bùi tiến thành thế đéo nào thằng lồn nào nó tạo nick nhái em tên buồi
AbduM лучший
your previous round was one of the best rounds i've seen since i join codeforces
hope to see such a great contest again