Hi!

On Tuesday, July 11, 2017, at 16:35 UTC Codeforces Round #423 will be held. Some of the problems will be from VK Cup 2017 Finals, some are prepared by Codeforces team to complete the problemset.

**Note that there will be two rounds based on VK Cup Finals, so I want to ask finalists not to discuss problems until the end of the second round.**

There will be *six* problems in each division, four of them shared. The problems of this round are proposed, prepared and tested by: vintage_Vlad_Makeev, demon1999, fcspartakm, Perforator, MikeMirzayanov, PavelKunyavskiy, qwerty787788, Belonogov, izban, tourist, vepifanov, AlexFetisov, winger, Errichto, Gassa, naagi, I_Remember_Olya_ashmelev, Endagorion, ifsmirnov, Arterm and me. Huge thanks to all who helped with the preparation!

**There will be prizes from VK social network in this round!** Namely, among participants solved five or more problems in second division, or three or more problems in first division, five are to be selected randomly. They will receive championship souvenirs. There is no country nor language restriction, everyone can win a prize. One don't have to have participated in VK Cup to receive the prize. Exact selection algorithm will be announced before the start of the round. There will be prizes in the second round using Finals' problems as well!

Good luck!

Congratulations to the winners!

Div. 1:

Div. 2:

The analysis is here.

Corresponding problems from VK Cup 2017 - Finals:

- Problem 827B - High Load is problem 823A - High Load, the author is MikeMirzayanov;
- Problem 827C - DNA Evolution is problem 823B - DNA Evolution, the authors are MikeMirzayanov and me;
- Problem 827E - Rusty String is problem 823D - Rusty String, the authors are vintage_Vlad_Makeev and demon1999;
- Problem 827F - Dirty Arkady's Kitchen is problem 823G - Dirty Arkady's Kitchen, the authors are demon1999 and vintage_Vlad_Makeev.

The souvenirs winners are:

Eligible list place | Contest | Rank | Handle |
---|---|---|---|

19 | 827 | 19 | zeliboba |

42 | 827 | 42 | kevinsogo |

114 | 827 | 115 | triploblastic |

125 | 827 | 126 | namai |

138 | 827 | 140 | gepardo |

Congratulations!

Thanks for your efforts

But how do you make sure that no one of the finalists has leaked the problems ?

They trust them and trust is never meant to broken. <3

Is it rated?

no it's not, they wrote the word "rated" as a joke :)

OMG, 300+ upvotes on a single comment. I want to thank my parents for bringing me up, my friends who have always supported me in everything I do and everybody who voted for this comment. Also, a huge "Thank you" goes to Mike Mirzayanov, without whom this would not be possible, for creating this awesome platform.

Does souvenirs includes the cute cats?

His name is "Persik" (Peach)

Duration of the rounds? 3 hours, or more?

2 h

It's 16 reds including KAN.

Thanks.

Hey man, you are prince of statistics and probability , I always notice your efforts in comments

Thanks.

666

Wow! the number of problem setters exceeds the number of problems itself. xD

It must be a challenging round.

The problems of this round are proposed, prepared and tested byNot all of them are problem setters. So we can't be sure that the number of setters exceeds the number of problems.

The start time is too late

It's too late. Always has been. Always will be. Too Late

In China，It‘s midnight。 So .... T_T

It is always less than 30 minutes from midnight somewhere.

Okey, who wants to receive championship souvenirs, put dislike!

Codeforces server seems awfully slow. Does anyone know what is the matter with vjudge1 , vjudge2 and so on. There is a huge number of submission from these ids.

Well, vjudge(.) accounts are used to submit solutions from VirtualJudge and there are not so many submissions to hack codeforces. However I worry that there can be problems with codeforces during the contest and also API is not working which I use participating in the contests(

Good luck everyone :D

I got so used to times specified in MSK timezone (which is also more convenient for me) that I thought this one is in MSK too and completely ruined my schedule, oops

In the English post it is written explicitly that time is in UTC, isn't it? On the contests page the times are noted with a timezone, right?

Yeah I know it's completely my mistake, I was quickly checking it on my phone without paying much attention.

For div 1 contests, will task be same as on official contest, or we will have one easier ?

Thx for preparing the contest... GL all coders :) Let's Rock

.

With all due respect to all problem setters and testers... I don't know why but seeing 'tourist' in the list gives a different feeling whole together..!!! Seems to be an awesome contest on it's way !

delay :)))

10 minute delay? :(

And again delayed...

I think winner of div 2 will be ccz181078 :)

mind explaining how you make that prediction?

https://www.codechef.com/rankings/JULY17

hahahhahhahaha, this is the reason for my prediction :)

OMG! :D

your prediction was correct...

Thanks "L" ;P

delay------10 minute.

I have a feeling that Div2 result will mostly be decided by the speed of solving the first 2 problems.

If added 3 new problems A,B,C it will not be decided.

Oh boy, you have never been so wrong your whole life!

You know what's worse than being in the friendzone for long? Being in the gray zone after a ton of contests. :(

Hoping to change that in this round. Need +40. Good luck to me! Good luck to everyone! :)

Never say Never http://codeforces.com/profile/KingOfWrongAnswer

Oh you got it, @cpaudyal! So happy for you. Keep up the good work.

Where is the scoring distribution?

To determine the winners we will use the following algorithm.

code"The seed is the score of first place in the next div. 1 contest."I can see people in the next contest posponing their submissions by few minutes and intentionally unsuccessfully hacking just to get a more favourable seed.

And? Who won? :D

With seed 5581, 200 people with 3+ problems in div1, 13 people with 5+ problems in div2 (isn't that difference too big?), the winners are places 19, 42, 115, 127, 139 in div1:

zeliboba

kevinsogo

triploblastic

SoiMae

pitfall

I wrote some scripts to make the process of winners determining easier, and they produce results slightly different then Xellos's. Here are my results (not official yet):

The seed is

`5581`

, the length is`213`

. The output of the generator is`19 42 114 125 138`

. The scripts I used are below. Xellos, have you used any scripts? If so, can you see where the difference came from?python codec++ codeThe list places are the same for me. I didn't use scripts, just went through the scoreboards manually, marked off ineligibles and then added 1 to list places for each smaller ineligible place; maybe I added incorrectly for place 131.

I believe that my results are correct, so now they're official.

If anyone has comments about the code, please comment.

what will be my contribution if i ask is it rated? and what the hell of lating?

This contest has more hacks than the U.S. presidential election!

maybe because of the large number of russians here :p

Is there anyone easier way to do E than FFT?

I also use FFT

What is FFT? Could you explain it please, if it's not too long, or give a good reference to it?

https://en.wikipedia.org/wiki/Fast_Fourier_transform

Thank you.

It's an algorithm used to multiply two polynomial in

O(nlogn) (withnis the degree of the polynomial).You can learn more about it here. (This is probably the only resource so far that don't make me instantly want to give up trying to learn this algorithm)

Thank you.

I did 400 Binary Index Trees, but I dont know if that qualifies as easier ;) edit: nvm you meant div 1, I meant div 2

I think he means div 1. E

Easy div.2 A hacks

How can i hack other's code ?

You need to lock this problem firstly(problems page), then you can open other's code (room page, double left click / ctrl + click on their score on problem) , look through and try to hack (button will be at the end of code).

There are no constraints? e.g. rating only lock?

You can lock only task you have already solved(solution has passed pretests) and you cannot send any code on this problem after lock.

Really really thanks!!

4 1 2

1 1 1 2 Ez hacks :) P.S.: Sorry, room 125 ^_^

Answer is 2 right?

yep

why 2 ? i thpught the answer is 0

If a group consist of one person, it is seated at a vacant one-seater table.

If there are none of them, it is seated at a vacant two-seater table.If there are none of them, it is seated at a two-seater table occupied by single person. If there are still none of them, the restaurant denies service to this group.Got it thanks

Hacked is better than system testing failed

WA on pretest 11 on Div2 D. What could be this case?

7 3

My code was giving wrong answer on this test case and I also got WA on pretest 11.

Div2A Hack4 1 2

1 1 1 2

Answer — 2

PS — My solution will also fail. :)

how is it 2? the first one will take an a table, the next 2 a b table and the last 2 the last b table. isn't this right?

I assumed the same but..

If a group consist of one person, it is seated at a vacant one-seater table.

If there are none of them, it is seated at a vacant two-seater table.If there are none of them, it is seated at a two-seater table occupied by single person.oh god, i understand now lol. that restaurant has some stupid policies.

Could it be said that the pretests were very weak?

the pretests were fine. if i had wa i would have wasted too much time trying to debug, not realizing that i understood the statement wrongly.

I think very many solutions falls in this test, me too...

Is the hack for C TLE ???

If so I'm screwed.

Yeah same here, thanks to map<string, vector>

Goddamn it the code was ready I was just about to resubmit it...

Ah well...

Hack for C div2 or A div1?

people were hacking faster than eminem rapping

TC 11 for DIV2 D any idea?

Don't know if it's that, but check for 13 6, answer is 4.

may be it was

8 3

what i think it was

and not like

Nope, I got WA 11 but I output 5 on this

That is why I wrote may be!! but after working on this my pretests were passed

How to solve E?

After a really bad performance on A and B...I know if I continue to do this contest, as usual, I am definitely not going to get a good result, so I opened F. I did F for more than one hour and I didn't pass pretest 19 until the contest ended.

Why even bother with A and B? You can start with F straightaway :D Yes, this strategy might not give you the best result, but at least you will spend the contest solving an interesting problem.

When you cannot debug a simple FFT solution for 1 hour :'(

:)

No FFT, No fun?

xD xD xD

4 1 2 1 1 1 2

Hack test in problem A :D :D Good Luck all :D

What is the hack for Div2C?

How to solve Div 2 D? And is Div2 E just a simple segment tree that remembers for every letter and every position % 10 number of occurences on every prefix?

I solved Div2E nearly the same way you described and used bit instead of segment tree.

I figured out the same solution, didn't get time though. :/

Looks like you can store prefix sums as well. Although I haven't submitted yet.

From one node, the other nodes extend in k directions. like a bfs.

Just like that? So simple? Any ideas how to prove that?

tried the same, but got mle. i suck at implementing seg trees.

For Div2D.

The tree wil be of star shape. So, put k vertices around centre. Keep doing this until you have less than k vertices. Then, put each of the remaining vertices in each of the branch. Maximum distance is

2*floor(n-1/k) in case when n-1%k==0

2*floor(n-1/k)+1 in case when n-1%k==1

2*floor(n-1/k)+2 in case when n-1%k>1

How do you prove (even intuition behind that) that a star tree generates the lowest diameter?

Followin is just an attempt to prove. Correct me if I am wrong.

CASE:

n> 2kWe can prove this by induction.

Let's say we know the best tree consisting of

n-kvertices andkleaf nodes. So, our required tree will be formed by addingkvertices to the best tree consisting ofn-kvertices andkleaf nodes , one at each of thekleaves.CASE:

n< = 2k(This is base case)We can clearly see that in this case it will be star. Any other shape of tree yeilds greater diameter.

The proof is pretty gappy. You don't prove that in the first case, there can't be a better solution.

Also, when using induction in graphs, most times it's more efficient to go backwards, inspect a graph, take away a node/edge, and by knowing the statement was true for the previous graph, it can be shown, that it is for the current graph also.

If you use the induction forward, there will be troubles to proove that you can achieve any graph this way.

There can't be a node with higher degree than k, because if a node had more edges, then the network would have more than k exit nodes.

Let's assume the highest degree is smaller than k. Pick the highest degree node, and choose the two longest "branches" starting from it. At the end of these "branches" there has to be an exit node. If we would have a node instead of this one, with degree of k, then this two longest "branch" would be at most as long as it is now, because all the non-exit nodes, can be distributed into more parts.

Also with this change, other lengths won't be longer, because it can be seen easily, that the longest path in this new network must go through the centre of the "star".

In conclusion, the star network isn't worse than any other, hence it's one of the optimals.

I found D easier than C in the contest.

Hack for C div2 or A div1????

Only 250points difference between C and D? Really?...

This was a CF round for me :D

Also div2 A hack: 5 1 2 1 1 1 1 1

It worked, if somebody didn't count the number of split tables, just used a boolean.

I tried to hack Div2 C for TLE. So I tried hack through generated input, then spammed some large string and same index. I care that sum of the size of the strings are equal to 10^6 and sum of k values are equal to 10^6 but I got invalid input with this error "Validator 'val.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]". What is the possible reason?

If anyone succeded to hack via generated input, can they show their generation code?

You forgot to output newline somewhere

So sorry to bother you again, can anyone find the mistake? Here is the generation code.

You mustn't output " " at the end of the line.

Div1 C memory limit too strict ???

Yup :( I just changed vector<pair<long, string> > to vector<pair<long, long> and string[MAX] and it passed. How to check difference in memory in this case?

I changer my segtree size from maxn*4 to maxn*3 and it passed damn

What was that rogue test case in problem A Div 2 that many people missed?

4 1 2

1 1 1 2

in Div2 B if all the cells are black the solution will be -1 or 0 ?

if n==m than 0 otherwise -1

that's right because the square should contains all black cells I forgot that . thanks a lot

if n==m then print(0) else print(-1)

div-2 A 5 1 3 1 1 1 2 2 i have hacked the code of user badassBitch his code gives 2 as a answer for above TC. but correct answer is 0 for above TC. some body please help me out ?? why

TC n=5, a=1,b=3, t[]=[1 1 1 2 2]

ans is 2 bcoz first 3 group will occupy different tables as given in question than there will be only 1 table left for the 2 sized groups

pretest 7 in E was an antitest for doing fft mod 2^27*3*5+1? Or did i make some stupid mistake?

System test is started...

Waiting for System Testing is like waiting for your HIV testing results...

That feeling, when you couldn't solve task during contest and solved it for 6 minutes after contest

Your text to link here...

Div 2 A

Yep, that's my hacking! My Room

My hack tests:

ANS: 2

ANS: 2

Your first hack test is the same as mine.

Can you explain, why the answer is 2?

UPD: my fault

test 8 in Div2 C :))))

It's damned!! You know

such shitty pretests for div2C

The contest is a massacre for any problem solver XD WOW

Memory Limit Exceeded on test 8 in Div2 C :(

If I understand the statement well, you can have a string of length 10

^{6}(e.g. aaaa...aaa) and then 10^{6}positions for this string : 1, 2, 3, ..., 10^{6}. Maybe in this case you register 10^{6}times a string of size 10^{6}?yes. i was pushing the string to each of such indexes. Instead of pushing, could have just stored the max. length string for each index. (instead of creating a vector of string, sorting it and picking the last one. :P)

Very funny. Write some complicated statement in d2 C/d1 A. Do not add appropriate pretest and watch majority of the solutions fail. Did you guys bring enough popcorn?

Edit. Some people still don't know. The strings coincide, so the total amount of occurences can be huge, you should set each letter only once...

Sorry, are you complaining about the fact that a solution that is obviously too slow gets TLE?

I'm complaining that it was not obviously too slow. It is the fact that you can't discuss as majority of submitted solutions failed.

Copying strings of length 10

^{5}from 10^{6}different positions gives 10^{11}operations. What is not obvious about that?The fact that they can overlap. It was mentioned that they can coincide — I understood that they can have some common parts but not that the positions may overlap.

The statement was not clear — perhaps examples showed that problem but it should not be required to read them to understand the task or at least it should be mentioned that "be careful, statement is not too good, read the examples". Besides it was not clarified what does it mean to be lexicographically minimal.

Bottom line is — the statement was confusing which was proven by very high rate of unsuccessful submissions.

You're just grasping straws. If you made the assumption that strings cannot overlap you cannot blame that on the statement not explicitly mentioning it.

The statement doesn't say that they don't overlap. Thus, they may overlap. I don't see what can be unclear about it.

P.S. The only thing a high rate of failed submission means that (surprise!) a lot of people submitted an incorrect solution. These solutions are blatantly wrong, it's not a corner case or something.

i do, but still TLE... I'm curious.

Probably java.

Yes, and I used my own SortedMap implementation, which made the code about 2x slower than when using the standard TreeMap implementation. Still O(nlogn), pity that it was rejected.

I can confirm java is probably the problem. I translated my Java solution that failed systests into C++ and I got AC. It's annoying that problem-setters often seem to make bounds that are very unfavorable to java users, but understandable considering the main focus is on making sure suboptimal C++ solutions to not pass.

Reference: 28433564 28453400

But there is a linear solution to this problem.

I get that, but based on the bounds I expected am NlogN to pass in time. Maybe that's because I generally compare 10^8 operations ~ 1 second, which might be more accurate for C++ than Java.

I don't get that there's a linear solution to this problem. But, that's why I'm not red and will have to wait for the tutorial...

EDIT: Oh, yes, now I see, use an array instead of a (tree)map, that's linear indeed, thanks.

I don't get how my submission to div1A (28436078) can get a TLE... Can anyone help me understanding this? It seems to me that my program does something like 5·10

^{6}operations in any case...I was wrong. Deleted.

The length of the answer can exceed 10

^{6}. So you have an access violation that changed the loop counter or something like that.but I used array size 2e6+4, still I got tle on test case 8. Any reason for that?

No it's not the problem, I have no access violation.

Actually I got it : I wrote s = v[remember[i]] in a loop of size 10

^{6}, and v[remember[i]] can be a string of length 10^{6}. So if I simply erase this and replace s by v[remember[i]] in the next lines, it should get AC... :'(same doubt

You made the same mistake I did, copying the string each iteration instead of referencing it:

`s = v[remember[i]];`

Yes I just figured it out! Thanks :-)

When you fail at A and C... Because of edge cases... I failed C because i used constant too low (2*10^6)

Div2C/Div1A how could this pass systest? http://codeforces.com/contest/828/submission/28450333

It takes about operations. The worst case is 1000 strings, each of length 1000, and each appearing at 1000 positions that are spaced 1000 apart.

guys i still struggling to get AC :( , if someone can help me

I got WA on test case 5 and my solution works in O(|Needed String|)

Here

Did

O(m*log^{2}(m)) pass in D?Yes

HLD or smaller set to bigger set?

HLD , i started coding small to large with priority queues but that would be NlogN memory so i switched to HLD at the last moment.

Actually small-to-big works as well; limits aren't too tight.

28460132

How to solve E div2 ?

I built segment tree for each length of e, every position in e, every letter. So it's about 220 segment trees. I didn't use custom allocator, so got TL. But solution with custom allocator gets AC.

PS: can somebody explain me better solution?

I also did something similar but using a space around 40*N and BIT trees.

ML is not problem. Every adding operation uses

O(log_{n}) memory, so it'sO((n+q) *log_{n}). My solution used 393 MB < 512 MB.I didn't use a custom allocator either. But I made sure that when I was looking at length

L, my Fenwick trees all had sizen/L, maybe that makes a difference. Here is my solution: 28440263I think because you used arrays you haven't troubles with memory allocation. And I'm not sure, but Fenwick works faster than segment tree

Who wants it to be unrated? XD

For Div 1 A/ Div 2 C, consider the following testcase:

4

bcc 1 3

c 1 5

bcbc 1 6

cc 1 4

The answer should be "bcbccbcbc" but the accepted solutions output is "aabccbcbc". Why so? The question states that there is at least k occurrences of each string!

EDIT: My mistake! Interpreted the question wrong!

Question also states that you need to print lexicographically smallest string of all possible strings(answers). In that case u can assume that at least k means exactly k and put 'a' at all the remaining positions of string.

Why is rating predictor not working ?

Codeforces API down

So why I'm getting TLE? :/ C SOLUTION

Try using fast I/O and use pos.insert(pos.end(), i) to insert in the set

Code

Source

Thanks a lot, it passed :D

Ur first while loop is doing n interations and for loop is doing |s| iterations ,i.e. , 10^6*10^5 operations!

the for loop isn't doing 10^5 operation read it well :)

Sorry my bad..

Can someone tell if the round was actually rated?

Thank you for the contest, the problems were great. However, there is one tiny issue.

28439979

Look at this submit. It passes flawlessly pretests and then gets TLE 16. We can easily notice what happened — author is outputting answer via unsynchronised cout. The real question is — wasnt there any maxtest in pretests in such a valuable problem? KAN

In test 3 the output is 50000 lines. Should be enough to test I/O.

In test 16 the output is 1 line. The problem is at some other place.

I'm sorry then. Strange, though. The submit looks correct

Don't use ordered set

LOL! Gray retards put minuses again, they don't know that Fenwick tree should be used in such kind of problems as it is much faster.

"Gray retards" ! Be polite man!

Look, it worked! What's happening with this site?

And what about div2 C ?

TLE AC just for I/O

The writer of this comment asks, who is the author?

A solution with policy-based DS fits exactly in the time limit in Div 1 C:

http://codeforces.com/contest/827/submission/28452503

It is such a sad fact that i didn't notice that i got WA during contest because i forgot to check the set size.

Time Limit 2 secs

it's Python, baby

Problem C in div2 says "**It is guaranteed that the sum of lengths of strings ti doesn't exceed 10^6**".

I got RE in this submission: 28448052 Here array size was 1001000.

I got AC after increasing array size 2*10^6 in this submission: 28452964

Why?

MikeMirzayanov

Array sze for soln will be a max of 2*10^6.. Consider the case where there is only 1 string of size 10^6 and x is 10^6

Oh, that's frustrating :/

can anyone tell me why i am getting TLE i dont think so that my code is taking more than 2 secs CODE->28448213

Found the problem!

So what do we do now?? KAN please help us!!!!

You are copying the string every time.. I changed your code Now it gives WA on 16, so there must be some other mistake 28454163

actually i got it earlier now i m just trying again and by the way thanks

Can someone explain their solution for Div 2C String Reconstruction ?

Keep an array of indices, (we have an array a of length 2,000,000, if a[i] is marked with an index j, this means that there is an occurrence of string j at position i, if multiple strings occur at the same position, save the index of the longest string which occurs at that position). Then, we loop through all of the positions. For each position, if the position is marked and we are not currently printing a string, then we start printing the string marked by the current position. If a position is marked and we are currently printing a string, then we check to see whether the leftover string we are currently printing is longer than the string marked on the current position. If the string marked on the current position is longer than the leftover string we are currently printing, then we stop printing the leftover string and start printing the string marked on the current position. If a position is not marked and we are not in the middle of printing a string, then we just print 'a', since 'a' is the smallest letter.

here's the implementation of the exact logic...

28470641

Thanks

28448669

`//lol;`

Hey, don't steal my upvotes =)

I have to admit it, I'm proud of kpw29. #annealer

Ehh, I'm not so proud now (but still proud). Test were just very weak... First test that came into my mind: "VKVKVKVKVKVK..." with one random change was enough to make these submissions fail:

28448669 — WA

28448743 — TLE

28447467 — TLE

My Rating=2017 in year 2017 :), so to me seems like a notorious coincidence

Why does this TLE for Div2C

Maybe because using lower_bound gives takes log(n) extra time

But lower_bound would be called 10^6 times at max so that shouldn't be the case

Erase in vector takes linear time?

Yes.But again each element would be erased at most once(no insertions).Why is it timing out?

What is the prize selection algorithm?

http://codeforces.com/blog/entry/53219?#comment-372405

For Div2 C, can anyone tell me, why I am getting WA on test for my code: 28454008

Change max to 2*10*6..

A bit of bit magic helps you to solve E div 2/ C div 1 in

O((n/ 32)^{2}) time.Code: 28454011

Ugh,

n= 1 on F... 28450889 vs 28454566. This is the worst way to get a problem wrong. I want a refund for my brain :-Pcan somebody plz point out the mistake, I tried for hours now, here's the code 28455191

Ah! String Shallow copy denied me a double digit rank.

string a = "This is a blunder. I knew it. But I forgot. Dont mess it up"

string b = a. //This takes not O(1) but O(n) time :(

when will next round?

Challenge in div2 C

Add this constraint

"the string can only be reconstructed using the input strings"

this is how i understood the problem during the contest and i thought that it was very hard problem

me too man

I can't access neither my submissions page nor any other user submissions page since the round ended. Server returns page with "The page is temporarily blocked by administrator." message. Does anyone else experience this issue?

http://codeforces.com/blog/entry/53217?#comment-372273

See this.

Can someone help me with the Div 2 part C 828C - String Reconstruction. I wrote a solution but get black spaces in between the final string for the answer. Can someone tell me what the mistake might be?

Here is my source code:

int main(){

}

The given strings, don't fill the whole string. You have to put 'a' s on every position, which wasn't occupied by a character from the input.

I tried that too.

I initialized the answer character array 's' with all a's.

Still I do get blank spaces.

Can Someone explain there solution of Div2C Please.

Thank You!

Disjoint Set use this data structure and its O(αn) can solve this problem

is this contest rated btw?

Can anyone tell me why my submission is getting a WA on div1A/div2C ?

My Submission

2

aca 2 1 5

aba 1 3

Answer: acabaca

Your answer: acaaaca

Thanks for the help, was able to rectify that. Getting a TLE on TC 8 now. Will have to make the solution more efficient, I think. :)

Yes. You have

O(ANS·k) algorithm (wherekis sum ofk_{i}), but existsO(ANS+k) algorithm that much shorter and easierIgorSmirnov can you help me :/ ?

I got WA on test case 5 while my algorithm works in linear time O(|Size of needed string|) that's good enough

Here

Did you check for the test case provided above in the same comment thread?

yes :/

3

aaa 1 1

abbb 1 3

bb 1 4

Answer: aaabbb

Your answer: aaabba

After if in 42 line you have to write

i=ii;But your solution seems to bee not linear too, because in lines 37 and 43 you copy the string, so I can give you a test when you will have to copy

O(n^{2}) symbols :-)BTW, your solution is very close to AC, you just have to think how not to copy all the string

Ohh I thought that this operation works in O(1) but you made it clear to me :)

but there's another mistake somewhere :''( , I got WA on test case 5 too

Here

But here you should do lst = ii in if, shouldn't you? I can't check it myself, because I'm not in front of my computer now

I think nope :/ because i compare two strings with each others so i used lst = i (the first position before the beginning of the last string) so i am getting its end with lst + size

Yes, but in this if you take a new string to compare with others, but you don't update its start. Just try to add this line (lst = ii) in if and submit

I'm sorry tooo :(( , but i went to WA on test case 6 lool here

Before while:

lst = i — 1

finally AC , Big Thanks IgorSmirnov , you're great debugger by the way :)

WA on test 62 421div2 B what is it ?

421 div2B has only 46 tests

When will the editorial be published?

Where is the tutorial ?

Will we know (after second round ofc.) which task from finals is which?

Sure. I'll update the posts with this information.