Привет, Codeforces!
VK Cup 2021 - Отборочный раунд (Engine) уже совсем скоро, не пропустите начало: 17.07.2021 17:35 (Московское время). Это соревнование предназначено для тех, кто решил хотя бы 7 задач из 8 в квалификационном раунде VK Cup 2021. Раунд будет рейтинговым для всех.
Но даже если вы не регистрировались на VK Cup 2021, добро пожаловать на объединенный Div. 1 + Div. 2 раунд Codeforces Round 733 (Div. 1 + Div. 2, основан на VK Cup 2021 - Отбор (Engine)), который начнётся в то же время. Он также будет рейтинговым и открытым для обоих дивизионов.
Все задачи были придуманы и подготовлены мной. Большое спасибо всем, без кого этот раунд не смог бы состояться: PavelKunyavskiy, KAN, lperovskaya, ksun48, Sert, Aleks5d, MikeMirzayanov.
Участникам будет предложено 8 задач и 3 часа на их решение. Рекомендуем прочитать условия всех задач. Удачи!
Среди участников закрытого отборочного раунда, 64 лучших участника получат фирменные футболки VK Cup, а топ 32 пройдут в финал и будут бороться за солидные призы:
- 1-е место — 300 000 рублей;
- 2-е — 200 000;
- 3-е — 100 000;
- 4-е — 50 000;
- и 5-е — 30 000.
UPD: Распределение баллов: 500 — 750 — 1000 — 1500 — 2000 — 2750 — 3750 — 4750
UPD2: Поздравляем победителей!
VK Cup 2021 — Отборочный раунд (Engine):
Codeforces Round #733:
Выложен разбор задач A-E на английском языке.
UPD3: В разборе появились решения задач F-H на английском языке. Русскоязычная версия разбора появится позднее.
One of the shortest announcements. Tourist orz
Oh Yes
Wow! A tourist contest.
What is (Engine)?
That's the name of the competitive programming track of VK Cup.
Imagine getting +286 on a reply. Sorry can't relate T_T
I made it +287
Amazing. Unbelievable. God powers!
Now it's 409!
2000+ upvotes easily
Done :)
For the first time i will be participating in tourist's round.
Really excited.
Yess, round authored by biggest name in competitive world. Excitement at its peak.
i also very exited just after seeing author is tourist
and hope to become expert in this round..
You could have wrote this without tagging him. Why it's so difficult to understand that it may annoy them
Edit: He edited his comment
no, it definitely dont annoy them ,by these comment they can see how much people appreciate their talent.i dont know how you came up with this idea.
https://codeforces.net/blog/entry/82329#comment-692934 https://codeforces.net/blog/entry/81527#comment-682038 https://codeforces.net/blog/entry/81377#comment-680706 https://codeforces.net/blog/entry/79620#comment-655959
Looking forward to participating! Good luck to everyone who is participating.
Originally I am not planned to participate this contest because I have a date then. But when I see the author, I just postponed the date and register for this contest. Wish I can turn purple.
tourist is always first, dates come second
Nah, second is Benq, check the top
That's not a contradiction.
Hii, Errichto what's up! I am your huge fan.
Lmao, others fans got serious.
Why not both?
Me too, I would have a sweet date with my girlfriend tonight. But when I saw it is tourist round after, I give up the date have no hesitation!
I would have a sweet date with my girlfriend tonight. I asked her to participate in this contest with me :)
and now she is your ex ,she called me after conversation with you LMAO.
whatever imaginary scenario floats your boat
I can confirm that we didn't break up :)
wait a minute you guys having a girlfriend
Dude, thats hilarious !! Best of luck !!
Unfortunately, I will have a negative delta. I stuck too much time on problem D, although it passed in the end. I solve problem E 10 minutes after the contest, but it's too late.
This contest is good, but not good as I expected, the real problem D and E are just implementation and corner cases analysis, the solution is not beautiful.I don't like that.
Imagine now your girl is mad at you cuz you cancelled your date and on the other hand you get negative delta. Life suck sometimes :(
Yes, I feel very bad now.
Lets look at bright side. You got contribution points. :)
Can contribution nullify the point that Girl is mad?
Well, when you cancel a date, you surely know its_Atrap
D really has any corner case? I don't see any corner case in my solution :(
Yeah one actually.
I didn't consider any corner cases either and got AC, probably some logics don't encounter the corner case.
Just wonderful to see the author's name. Really excited to participate in tourist contest.
And the award for the shortest announcement goes to...
Let's hope same for problem statement.
Me? I've never written an announcement.
tourist orz!!
After a long time!
A contest written by tourist!
I'm enjoying the contest already!
Experting in a tourist contest would be so honorable ;)
Take my upvote
tourist recommended to read all the problems. We should ....
As a tester, I won't be participating in the round.
OH NOO! is this a sign again?
sign of?
Maybe a hint to participants to be aware of what's gonna happen...xD
In other words, "As a tester, I want contribution points".
I signed up for this contest seconds before seeing this. SECONDS FROM DISASTER
This would be my first contest whose problems are completely authored by tourist. Hope to perform great this time :). Just a little question, why the name is Elimination(Engine) ?
Engine is the name of the competitive programming track for the VK Cup
OTZ
is this going to be much harder than normal div 2 contest ?
Aye, this is a Div.1 + Div.2, so it obviously will be harder.
Why is there a second contest (VK Cup 2021 — Elimination (Engine) ) at the same time ?
EDIT : My bad, overlooked the mirror part.
one is the actual contest, and the other is the mirror of it i think
My first tourist contest, I hope to make him proud.
Yes you can make him by getting Rank = 3748 .
If this is the condition. Then I want to make 1-gon proud. (. ❛ ᴗ ❛.)
Let me help you with upvoting.
The quality of problems would most probably be exceptional to say the least. Hope to have a great round. :)
Nothing! Just coming every hour to see the upvote count. (◔‿◔)
Should I be excited or worried about tourist round?
yes
Extremely glad to participate in this round, my first ever contest by tourist
Why are you guys tagging him again and again.That would be disturbing for him for sure
How you guys manage contest and dinner in 3 hrs p?
by screwing up on A and quitting right away
Lmao haha
Hello , the round will be rated right? plus the problems will be sorted from easiest to the hardest right? Thanks in advance!
First of all answer my this question, Who was using your account for past 8 months? Judging from your questions, the person could not be you. But if it's the case then, The cute answer to your questions is YES.
nah bro , i asked coz he suggested reading every problem , i thought that he might not havebsorted the problems fmas we are used to. about raiting changing i don't usually take part in contests except from div2 , educational ones and div3.
problem a will probably be a 3000
I was expecting tourist to win this round and surpass 3800 for the first time in CF history.
Now, seeing the King himself hosting the round. Can't wait. <3
Time to upsolve global round 5.
(which is also prepared by tourist)
I always thought I was the only one who did that trick >.<
jiangly literally solved every contests ever hosted by tourist within last week. I can already see him in top 10.
well
Say no more.
As tourist said upsolving anything is meaningless, because you will never get the same problem in the future contests...
There are many various blog posts, explaining that humans are bad at coming up with random number sequences. One website even implements a demonstration in the form of a game. All of this has some practical implications on passwords strength, etc.
It's possible that tourist believes that his new problems are really unpredictable, so upsolving the older problems is meaningless. But he is a human too, and humans are bad at randomness...
ehhh, you dint get the jokeT-T
https://www.youtube.com/watch?v=cB5jSWxYmrs
More like, being a new guy around here, I haven't seen this joke before. And TheDramaQueen's comment didn't look like a joke to me in the context of this discussion. Thanks for the link!
So jokes aside, is it generally useful to check the older problems authored by the same problem setter before the contest? I guess, in the worst case this at least doesn't do any harm.
false
tourist what do you eat? orz
He always eats the 1* first position in Div. 1
tourist round! Can't wait for the great problems :)
The round will be perfectly balanced. As all things should be.
G Korotkevich
If you are a true tourist fan you would remember this.
is it going to be a tough round for div 2 participants since it is a combined div 1+2 round? But since there are 8 problems this means first 5 problems would be like normal div 2 rounds.
Are the scores of the problems published?
https://codeforces.net/contest/1315
if anyone wants to take reference this is last vk cup.
And this is the shortest announcement I have ever seen #tourist swag
Who all are fired up just after seeing the author of the contest?
Let's nail it guys.
Imagine Benq winning and gaining the first position in this round.:-)
There goes another opportunity of getting a chance of defeating tourist in a round :(
More than 1441 upvotes wow !
tourist round, really excited!!!
tourist round, amazing!!!
tourist round, amazing!
Specialist i'm coming!!!
Pupil I'm coming!
Newbie, I'm coming
says tourist ! Super excited to see what new is coming :D
Looking forward to participating! Good luck to everyone who is participating. I hope I can be pupil after this round :<
Very Excited for this Round :)
My bad! I M SORRY
Do you find it a tedtalk stage?
Tbh... It's better to share something you have on your mind with the CF community, cause they are always understanding and help you out. So thought of sharing it so that it might help those having the same mindset as I did. If not TEDTalk, it definitely is CFTalk stage!
It's better to share your thoughts when a topic arises related to that in some comment.Otherwise if people keep posting their thoughts not related to contest announcement, then it doesn't look good
Maybe, But instead of just sharing memes and funny posts on the round... I thought this might be a bit of change in the flow. Just CF things
tourist : Finally prepares a contest.
Everyone : tagging tourist
tourist : That's why i don't do it
Excuse me, How do you write text in red?
Like This!
nothing
I_love_Yuuki_Asuna
You can use html tags in here like <span>,<p>,<b> etc.
TANK YOU!
...
<p><span style="color:blue">Blue!</span></p>Blue!
A tourist contest! I think the contest will be difficult. /kk/kk/kk
I will have no rating.（（（
oh guys I solved some problem in the last round which write by tourist and it was easy do not be nervous!!!
Just because his previous round/s was/were easy, how does that make this round easy? 3hrs contest are usually hard than standard 2hrs contests.
Congrats tourist on making it to top ten contibutors Your competitor is here Monogon
Tourist can easily be on top contributors by just writing its_Atrap
I hope this round is going to be amazing.
Hoping to become specialist in this round. (edit: did it!)
After seeing no. of registration
Thankyou tourist for this round. Hope I take most from it.
Coming out of rated contests retirement for this round, I'm going down but I don't care
You liar! Seem that solving problems consistently keeps you in a good shape, right?
apparently
Scoring? I know that you're not a huge fan of dynamic scoring, so don't keep us waiting.
why am i feeling nervous even though I participated in 247 rounds and my rating is at it's worst
Little sign of nervousness will always be there no matter how much experienced you are
it's been a while since i felt that nervous probably tourist effect
is this round rated?
He is demanding 2500 upvotes for score distribution
Mission accomplished! tourist on the contribution board!
Best round I have ever seen for adhoc.
I'm so stupid when I solved C I thought this is it and I probably won't solve D so I made a sandwich and ate it and wasted 15 minutes that would be 50 points difference
how was your sandwich?
Falafel so delicious XD
The taste of the sandwich is your wasted score :D
How to solve E without lots of casework? I've got 5 cases (each case immediately exits):
I think f(t) can be only 0 and 1. This simplifies the problem. What was pretest 2 of E. Anybody has some idea?
Can be n — 1 in case of all characters same, but yes 0 or 1 is always possible otherwise.
Yes, 0, 1 and n-1. These are the only possibilities.
I got exactly the same cases. Thank god I'm not the only one, felt wrong implementing that many cases. :(
After this E I feel like I should practice constructive problems more...
This isn't even constructive. I got 2 of those cases by just running a brute against my soln
I got the exact same cases.
This is my pseudocode
aab(minimise sequence while avoiding an aa)ac, returna(all the b)(all the remaining a)to avoid havingabelsewhereab(all the remaining a)(smallest c)(all the remaining b)(remaining alphabets in order)to avoid havingabelsewherearefers to the smallest alphabet,brefers to the second smallest alphabet,crefers to all other alphabets.I missed the last case. Thanks.
Didn't finish but I think 3-5 are the same after you figure out the first couple characters (aab vs ab), then you can just brute force for the next character that fits and isn't a prefix.
I only thought of first 3 cases but tell but little differently. I combined your case 3,4 and 5. Since except the first case, in all other cases f(t) will never exceed 1. Then I found the 1st char whose freq is less than cel(n,2) ans started the string with that char and tried to filled other positions in optimal way.
This was my idea but couldn't pass pretest, tell me if I made some logical error.
Yep, same. I'd be surprised if you can do it with less cases, as these all require different solutions (except maybe "all char are same", as then literally anything works).
D felt too hard for me, I have no idea how to even start. I feel like practicing has been a huge waste of time considering my last couple of performances :(
Don't feel sad. It happens.
I just did some dfs with vertices with zero in-degrees for D.
I felt it's easy the number of wishes is how many distinct numbers used so just keep those and distribute unused numbers without someone gifting himself
What if $$$n-1$$$ people gift presents to each other in a circular fashion, and one last guy remains all alone (can't gift to himself)? The solution needs to ensure that this doesn't happen. I spent a lot of time to implement something monstrous, but now I'm worried about system tests.
I handled this case but i don't think it will happen we'll see
This can never happen actually because in the array we are given values such that arr[i]!=i. So if the first n-1 people give gifts to each other in a cyclic manner and we are left with "n" for the nth guy, knowing arr[n]!=n, we can just swap any other person giving gift to arr[n] with the nth person.
My submission : 122808827
Looks like lots of heuristics. For example, if all of a[i] are different, there is no need to change anything. If there several a[i] == a[j] == a[k] then we have to choose two of i, j, k and reroute them to someone who has noone wanting to give them presents. If there are several people pointing to the same guy, then there is certainly someone who has noone that points to them. If there are several people pointing at a[i] and one of them is j and if k points to j and if k has noone pointing at him then we most certainly must reroute j to point to k =)
So we need to decouple cases when we have lots of people pointing at the same person by rerouting them to the ones who has noone that points at them.
I solved it using Dinic's algorithm for maximum bipartite matching. Then if some vertices got matched with themselves, I corrected them manually in linear time. It was almost a straightforward implementation, so here is my code 122817211
How to solve F?
I want t-shirt too :'(
lol imagine being 64th
However congrats, you won me :D
Can you do F using broken profile DP? I tried doing that and I think it works but the implementation seemed bad so it might not be intended.
Can $$$O(n^22^n)$$$ pass problem F?I get TLE on test 10 :(
I am a stupid who can only use brute force,FWT and pragma to solve bitmask dp
Update:It seems that if I optimize the initialization part(before FWT)from $$$O(n^22^n)$$$ to $$$O(n2^n)$$$ it could pass in 6.5s,thanks~
My solution is $$$O(n2^{n})$$$. I don't think $$$O(n^{2}2^{n})$$$ can pass.
I passed pretests with $$$O(n^{2} \cdot 2^{n})$$$ (after lots of constant optimization, and took 6.5s). :| Guess that is not intended.
I passed pretests in 6.9s with $$$O(n^2 2^n)$$$ ( 122855739). The main optimisation is to skip 2/3 of the or-convolutions, as you don't need to transform the same array back and forth between handling every column.
Locally my code takes 3s in the worst case ($$$n = 21$$$, time used doesn't depend on input), but somehow it is over 2x slower on codeforces. I'm very afraid that random changes in the timing over many tests will TLE my code >:(
I have $$$O(n^2 2^n)$$$, the only limiting operation is "multiply+mod vector * vector".
I passed it in 3.5s :) 122866086
Is F solution DP in complexity n^2 * 2^n * 8 (8 bcs of mask of diagonals and current column)?
It is $$$O(2^n \cdot n)$$$
Is knowledge of prefix function required in E ? Also what is the solution for E
No. You can look at my comment above.
I found one guy in my room skip these cases discussion, maybe it has anothor solution which is more beautiful. :)
There was one observation that the value of function can be at most 1 if all are not same. No knowledge of prefix functions was required
No You just need to know what is the definition of prefix function(that is given already in statement) Atleast for the solution which solve all cases separately
lol E got 500 more submissions in the last 30 mins, I left the contest thinking it was too hard for me, stupid me :(
Solution of E got leaked around 30 minutes before the contest
what? where?
I'm guessing in some cheater chat :(
I've heared from my friends that code with AG guy is spreading answers on telegram.
sauce ?
I know my implementation skills are bad, but this felt more implementation forces than normal. Maybe there are good solutions for D and E and I'm just missing them.
My E was pretty nasty too. For D I used Hopcroft Karp maximum matching, which might have been overkill, but the advantage for me was that I could rely on templated code and had to add minimal lines myself, decreasing the probability of a mistake.
D was not too implementation-heavy for me, Here is my solution. I hope it passes system tests too.
I think F was broken profile bitmasking dp on row or columns. We could set diagonal mask initially and build the answer for rows or columns.
How to solve D? Is it somehow related to graph theory?
You can do it without using Graph Theory.
how to solve d?
Wait for the editorial. I'd explain it but I don't want to embarrass myself in case my submission fails:).
I used Dinic's (max flow) to find the max number of possible assignments. Then did some post processing to fill in the unassigned people. There's probably a better way though.
Could you please explain this a little more? How did you model this as max-flow problem? (I did it without using graphs)
The flow network is an edge with capacity 1 from the source (node 0) to n nodes numbered from 1 to n. Then we create another n nodes numbered n+1 to 2n and for each i in 1 to n we add an edge with capacity 1 from node i to node a[i]+n. Then for each node numbered n+1 to 2n we an edge with capacity 1 to the sink (node 2n+1). The max flow on this network gives max number of ways you can assign people to their secret Santa and their assignments. Then you are left with some people who are unmatched and you have to do some post process to assigned.
I considered the functional graph created by edges of the form $$$i \rightarrow a[i]$$$. The maximum number of fulfilled wishes is the number of nodes with positive indegree.
This graph has a bunch of cycles with trees hanging off them, and I flattened each tree into the cycle in DFS exit order, to get the functional graph for $$$b$$$.
I passed it by random_shuffle the positions i that a[i] isn't appears for the first time until the answer is valid.
It can be proved that the expected complexity is O(n).
Problem statements were short and clear. Enjoyed the contest:)
I think there are a hell lot of corner cases for E, :(
Zero hacks?
Well, were you expecting weak pretests from tourist?
I was expecting a non-zero number of hacks...
The chances of that happening is same as the chances that he actually missed some corner case :)
But it only has to be a corner case for one solution. There are many creative ways to make a weird, tiny mistake.
What was the pretest 2 for problem E?
for E it should be only 5 types of answer:
1) f(s) = 0 (there is a unique symbol) daaaabbbbccccxyz
2) f(s) = 1:
iii) abaaaaaaaaaaaaaaacbbbbbccccdddd...
EDT: f(s) = n — 1: zzzzzzzzzzzzz
What else???
UPD: nothing else, just forgot to add '\n' after one of the options :(
You missed f(s) = n-1.
sorry, yes, edited. But it should be something else
Yes these are the only cases
so, what's wrong with pretest 2?)
Did you miss inputs like
aabababa?it's 2.i
what? i do exactly what you've explained and get AC. did you implement your idea wrong?
I think substring abbbba of abbbbaaa..... makes wrong answer
no, my solutions returns aabbbb. By 2.i I meant everything which could starts from aa
ohhh got it, I was dumb
Stupidest mistake award goes to me, got all the cases correct except the first one :(
my random string generator can't reach it smh my head
I too had to struggle, but my random generator actually caught strings like these, when I restricted the character set to 2 and 3
Anyone struggling on E should try the following test 8 abbbaaa abbbaaaa abbbaaaaa abbbaaaaaa abbbaaaaacc abbbaaaaaacc abbbaaaaaaacc abbbaaaaaaaacc
[Deleted]
You guys have random string generators?
Random string of length N is just generating random integer from 1 to A N times where A is the alphabet size.
I wrote one during the contest (hardly 4 lines) to generate random strings.
In case you need, there's this test generator which might help.
I got 5 WAs to figure out all 5 cases. add 1 case for each WA.
I did code for "abaaaaaacbc", "baaaaaaa", "baaaaaaaaaaabb" but sadly, still don't know where the corner case is.
Edit: missed abbbaaaaaaaaaaa ;(
Yeah, I was also really confused passing several thousand rounds against a brute with $$$n \leq 10$$$ and getting WA2, so I tried reducing the number of distinct characters to reduce the number of distinct strings and get next permutation to run faster. Thankfully found this pretty quickly with $$$n \leq 15$$$ and $$$\text{distinct chars} \leq 3$$$
DELETED
If only I could solve D earlier... I really want to cry.
Hey, at least it's not your 3rd negative rating change in a row :///
Inspiring Rating graph, good sir
Me when in the contest :>
when will be editorial posted . if it is already posted than i dont know where to check .ps i am a newbie. its my first time doing cp.
wait for some time.
get over your contest depression first :)
why cant we submit now(without marks ofcourse)
Because system tests haven't finished yet
I want to check my sol. For E. I couldn't submit by just 2 mins.
Unfortunately you have to wait till the system test finishes
its still not available for submission
Haven't you learnt patience?Wait for a few minutes, it will happen
But why E? (when you can simply don't
I hope the finals will not be as boring as this.
I think even for a div-2 contestant there should have been harder C and Ds
You haven't even written this contest
Does it say I can't have opinions on problems?Will you disagree on the part D could have been harder at least?
no, I don't think so, because an amount of tasks is bigger, than in usual dif2 contest
When can we see other people's submissions
Great contest, as a Div 2 participant the difficulty curve felt really nice.
I'll probably get negative delta because I spent too long on D and as a result ran out of time to solve E, but I had a fun time.
Unpopular Opinion: it wasn't a good contest , as B,C,D,E were pure ad-hoc s.
I don't think that is an unpopular opinion.
I would rather say just implementation problems with zero ideas.
rofl
I wouldn't call CDE adhoc at all, they seem implementation+some casework to me
It's pretty funny that people just put "ad-hoc" on wherever they want these days and then upvote each others lol.
It seems that G and H are the only problems in this round. D, E are just boring case analysis problems and F are also too messy to code, so I skipped F and used my remaining time to solve G but nothing good ideas came out with me QQ.
Honestly, we all knew that tourist wouldn't win this contest :d
So happy, I finally solved 2 problems in the contest.
Feel like mike should give me bonus points :) for such an awesome achievement.
This might not mean a lot to you guys but I really put in a lot of effort in the prev 20-25 days and now I feel more motivated than ever to prepare for the next contest. Thanks CF for such a wonderful feeling.
I think this contest is terrible to mediocre participants like me.
Every problem before F is too obvious and implementation oriented (perhaps F is harder because $$$n^22^n$$$ should not pass). I spent at least two hours and thirty minutes on coding, and could not even finish F due to my poor implementation skill.
Just curious, how could you spend 2.5 hours on F when you finished E at 1 hour and 45 min mark? Did you multitask?
I think he(she) means A-F problems not just F. and I'm totally agree with him(her).
They mean. Agree with them. I think it's easier to write
I got stuck on problem C (Pursuit). I tried to simulate the process and find sum using prefix sum for every different stages and compare that sum to opponent until it becomes equal or greater. Could someone find the error in my code ?
My code link
Try this input:
Your code outputs
1instead of0. You should remember that Ilya's overall result is also computed from the highest $$$k - \lfloor k/4 \rfloor$$$ scores.Can you please tell me where am i getting wrong in problem C? 122851201
Try this:
The correct output is
2. With only one extra stage, your score can only be at most $$$100+50+50=200$$$ but Ilya's score is at least $$$100+100+1=201$$$.Thank you, now I am using prefix sum for both players. For Illaya I have to push front in the prefix array of Illaya score which is giving me TLE error. Could this problem solve using Prefix sum ?Thank you My code link VTifand Carti_Tester alwerty
The line
b.insert(b.begin(),0)is probably too slow in vectors. Have you tried using a deque?Changing the total number of cases can also change B score. For example:
b = 50, 100, 100, 100 -> score = 300
b = 50, 100, 100, 100, 0 -> score = 350
You forgot to increase Ilya's score with the increase in number of rounds.
For example, if n=12, you only check for the top 9 scores for both but for n=13, you have to check for top 10 scores.
Why is not my solution for B in queue? It is still showing 'pretest passed'.
Edit : fixed
Because you are not patient
D can be solved by randomly shuffle leftover people to people with replicated wishes, because the probability of getting a valid solution is greater than $$$\frac{1}{e}$$$.
What's the formula to calculate it?
It's not worse than the probability of a permutation being a derangement.
Could you describe your algorithm and proof strictly? For example, do you take any leftover people and fix them before shuffling? If so, if you have one leftover, with probability 1/2 you will choose wrong guy who can be matched with himself only.
I handle the case when there is only one leftover separately.
Hmm. I guess this is because the number of derangements is zero. Then its clear.
then:
Codeforces Global Round 15 Jul/25/2021 22:35UTC+8 02:30 Before start 8 days Before registration 5 days
dangerous
CF is ardent on destroying people's ratings.
I don't like this round.
A, B is simple math, and C is just implementation.
D, E requires observation but not knowledge about algorithms. Especially, E has a lot of annoying corner cases.
This round is neither educational nor enjoyable, at least for those who can't solve F, G, H. I could learn almost nothing from A~E.
I don't how problem D is supposed to be solved but it was my first time implementing something with the "linked list logic", if there is such a thing. So for a beginner that problem was cool. Didn't solve E but I also didn't like ABC that much.
D can be easily solved this way as well : https://codeforces.net/blog/entry/92951?#comment-817698
Problems A and B are Div 2 problems A and B, thus they have to be simple) IMHO, observation-based problems are much better than algorithm-based ones. Additionally, such problems as E are created to test your technical skills, so you just have to learn how to solve them. I've seen a couple of problems, which required hardcoding about 50 cases (coding and decoding a labyrinth or interactive chess for example) and that was an overkill, but this problem definitely isn't. At least, you can stress your solution and find all the corner cases really fast.
Why solution not open yet??
For D, my O(nlogn) solution gave TLE on test_case36. But isn't it good enough to pass in general?
Your code's complexity is not $$$O(n \log n)$$$ because you are copying vectors that might have length up to $$$n$$$, $$$n$$$ times:
thanks
98% tested but solution not even in queue, any idea?
https://codeforces.net/contest/1530/submission/122840063 Can someone explain what exactly happened here? The solution had passed on pretests but the system tests seemed to not even run it?
Edit : It's fixed now.
Same here
MikeMirzayanov please look into this.
My first time winning div.1, cool!
congratulations!
why downvotes to my message?
The contest is finished, yet my solution of problem B is not judged. It is still showing 'pretest passed'.
MikeMirzayanov Can you please look into this?
i have same problem(
Acc to CF predictor, I am finally becoming specialist.
It feels extra special coz this upgrade came on a tourist contest :)
Congratulations!
Even after 100% system testing is done, my submission still showing Pretest Passed. But it should show either an accepted or the wrong answer. Why is it happening?
same :(
To me ur soln is showing accepted
Why we can't see other people's solutions? UPD : now it's fixed.
Is there a chance that actual VK cup results will be merged with the rated round?
I wasn't able to solve A and B in any of other contests but in this one I solved them and I am Happy thanks tourist for amazing problem set!
The problem is not with you but with the questions A-C.
okay!
Why I am unable to see the code of other people given that testing is done?
The system testing is finished, but I'm still not able to submit solutions to these problems for practice. When will I be able to?
Anyone please tell how to solve D ?
Place all the unique elements on their place and all remaining elements such that if there exist a number such that if b[i]!=i then use that element otherwise place i there. Then check if there exist any index i such tha b[i] == i then swap it with another j such that a[i] == a[j]. It is easy to see that there will be at most 1 such index after applying above algorithm.
My Randomised greedy solution got accepted and I'm not sure if it should. I got an intuition that if I shuffle the array after some tries (very less), I will be able to find solution with straight-forward greedy. Can anyone proof this (or atleast tell me why my solution works) ?
Are there any kind of plagiarism checks done because almost half of submissions of all the questions including E are same.
F
I looked into the standings and did not find tourist. Now suddenly noticed in the sidebar that this post was from tourist.
can someone help me with my problem C
if number of stages can be divided by 4 you should add 100 to s1 and subtract it by the lowest stage he had let's say you have 3 numbers 20 30 40 then sum is 90 if you add 100 then you have 20 30 40 100 but you take n-n/4 so you have now 30 40 100 sum is now 170 not 190
In problem E we have to minimize the longest prefix suffix and find the lexicographically smallest one among possible configurations.
But in TEST case 2 it's giving wrong Ans, and the expected output is NOT the lexicographically smallest
TEST CASE 2 wrong answer 64th words differ - expected: 'tutttttttttttttttttvuuuuuuuuvvvv', found: 'tutttttttttttttttttuuuuuuuuvvvvv' Can anyone explain what's wrong? Am I missing something? 122865709
Your soln has "tu" twice which makes max value 2 for some prefix.
GOT it ThankYou. I was reading suffix of string from right to left (in reverse) MY BAD.
Problem C
Can anyone help to tell the error in my code
Failing on second test case(273rd TC).
https://codeforces.net/contest/1530/submission/122867622
int k = mid — mid / 4; bsum = b[min(n — 1, k)];
It doesn't work for every circumstance. Since we assume that we add only 0 to b, therefore we eliminate 0 first rather than element of b. For example, let n = 7, mid = 8. Then bsum must be the b[5], but it is b[6] maybe?
Could you give an input that shows this issue? I think I don't understand your explanation.
1
7
8 8 32 42 51 56 67
25 31 38 51 53 75 92
Can be a possible example that a given code doesn't work.
Edit. I found my explanation is a little bit wrong. But this counterexample still works I guess and bsum is still miscalculated.
Hmm, maybe writing
bsum = b[min(n-1, k-1)]will work?Ah. I think so.
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
I miss MikeMirzayanov saying that
Thank you for this round and particularly for strong examples: I got bunch of WA1, and thus no extra penalty! First time I became master! (after color revolution in 2015). (My screencast, 53th place official contest. Nothing interesting after E)
Your palindrome probably won't last long :-) "Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!"
Really interesting contest but I still can't be pupil :< Hope next contest I could be...
And this is what happens when tourist is the author of the contest: 0 Successful Hacks!!!
I get wrong answer on testcase 2 for problem C ? can you help me ? my code : https://codeforces.net/contest/1530/submission/122892715
fixed
Thank you
For problem B. Putting Plates Why this one is incorrect for 4 4? Please someone explain it. ~~~~~ 1010 0000 1001 0000 ~~~~~
in your submissions it's 1010 0000 1001 1000 the one you wrote is correct as HP21 said
F-H editorial when?
3 days have passed, could you please where can i found the editorials for the problems f to h, or rather, they have not been made public.? thank you.
когда следующий?