Hi!

On Jun/18/2020 17:45 (Moscow time) we will host Codeforces Global Round 8.

It is the second round of a 2020 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round:

- 30 best participants get a t-shirt.
- 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2020:

- In each round top-100 participants get points according to the table.
- The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
- The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2020 supported the global rounds initiative!

Problems for this round are set by me. Thanks a lot to the coordinator 300iq and testers thenymphsofdelphi, Lewin, Golovanov399, Osama_Alkhodairy, gamegame, dorijanlendvaj, HenriqueBrito, kocko, ruban, Origenes, Ilya-bar, rahulkhairwar. Their feedback was a huge help and affected the problemset greatly.

The round will have eight problems and will last 150 minutes.

**Scoring distribution: 500 — 1000 — 1500 — 1750 — 2500 — 3000 — 3500 — 3000+1500**

Good luck, and see you on the scoreboard!

**UPD**: the round has concluded, congratulations to the winners:

Check current Codeforces Global series standings here (courtesy of aropan).

You can find the editorial here.

Stay tuned for prizes announcement!

Surprising that even legendary grand masters have coordinators.

Yes

Wow, I don't understand how people like posts :) P.S. Perhaps the situation has changed, but now it looks like this:

Wow, I don't understand how people ignore this.

Be careful — now he knows who downvoted him.

recursion?

recursion?

return 0;

What is the exact job of the coordinator?

To coordinate.

Deleted

It is obvious, with everybody except tester and setters.

He reviews the problems and provides feedback on basis of that. They are highly experienced coders who have impeccable taste of problems.

The submission verdict is actually given by them manually.

Aiming for T-shirt!

late announcement :p

Combined Round after a long time !

Deliveries in corona times T_TThat's why it is called random distribution.It feels like the main reason why people do CP is to get free T-shirts...

No, sometimes girlfriends too.

wait what?

don't tell us your dream of today

You mean lose a girlfriend?

That means that you had one in the first place...

Can we expect more than 20k participants in this round.

Endagorion... It sounds like a good round

Bad memes*

Will we see a MiracleFaFa vs tourist?

There will be fireworks from both the ends.

tourist will back to his throne

Um_nik will beat both

More precisely this will be coding war tourist vs Um_nik vs MiracleFaFa ! :)

ecnerwala take it all!

I'm rooting for Benq.

lol looks like a cricket match is gonna happen

No, in this round, @dtc03012 vs @MiFaFaOvO

Hoping to watch a tourist show once again.

Actually its ecnerwala show !

still no sign of MiFaFaOvo :)

He did VP this morning(in China)

Links of previous global rounds:

Codeforces Global Round 1

Codeforces Global Round 2

Codeforces Global Round 3

Codeforces Global Round 4

Codeforces Global Round 5

Codeforces Global Round 6

Codeforces Global Round 7

Hope this helps!

you can use this https://surya1231.github.io/Codeforces-contest/

helpful. Thanks

Thanks..

thanks mate!!

All Global, Div3 and Educational Codeforces Rounds

NICE Round

Hey everyone, those who are turely annoyed with her and want to choose a cool institution please set your institution as of mine. Its a request

I'm annoyed with her, but I don't agree with your opinion too. I don't want to be in any Anti-Fanclub, okay? And also,

don't use your second account to post bad comments.You registered 6 weeks ago and didn't participate in any contests, but your contribution is below -70.Is it like I hate Rachel club ?? Only this time _chandler_ is a part of it instead of Ross xD.

A newbie like me should participate in this? though it is rated for all and the level of questions will be hard

Don't be afraid because you are a newbie. You have to participate in many rounds, and then you would be able to increase both your rating and skills.

Thank you sir for your kind words I'll try my best

Good luck!

Hello guys.I have no idea about calculating contribution.I commented in the last div3 contest announcement then my contribution began to low.Before this i thought contribution is calculated only for blog.Please anyone explain about calculating contribution..Thanks in advance.

Hey bro ,I don't know much about contribution bur make sure that your comment make a positive impact to the community and don't post negative comments. I think it will increase your contribution points. Hope it helps. PS: I earned +2 yesterday

rule but i think skills is more important than your contributions..

Combined Round! Hope it will be fun.

tourist and MiracleFaFa both have registered for this round! It will be exciting to see.

Game of thrones... XD

Indeed! GOT without any bloodshed! :p

Don't forget about Um_nik. He will also join the party.

I wish there was a live telecast! :p

Don't worry. Standing will be live :3

:p thanks for this info! :3

An unexpected finale: on a pedestal ascended ecnerwala

7 among top 8 are registered for this contest and left one is coordinator of this round.

With how many problems?

Sorry, didn't notice it was written in the announcment

No offense to anyone

None Taken

current highest ranked post

In 5 contests they would have 1M Youtube subscribers.

A codeforces round from Endagorion after a long time. Eagerly waiting...XD

I hope to see myself as a pupil in today's contest. Good luck for everyone.

scientists or doctors ?

Is the rating calculated differently for these rounds? For example if I get rank 500 in a global round and in a div2 round, would my delta be higher for global round since div1 participants are also considered in official standings? Or will it be the same

of course, sir!

This comment section is shit.

Agreed, the memes turned from actually funny into shit that takes up space.

MikeMirzayanov should actually ban photo comments to prevent this.

Not all images are memes.

What do you expect it to be before the contest started?

Welcome to memeforces!

welcome to

chandlershit postsYour graph reminds me of Mariana Trench.

Oh boi. You're so rude

wow that's so toxic, don't throw shade on him because he's "bad" at CP (as of now)

That is not something Chandler would say

Apologies to Ag12, adityarev, codemastercpp, Jojo_Mojo.

I, unintentionally, crossed the line.

You got many upvotes (including mine). Because you are Errichto.

Great performance Errichto, I'm glad to see ur level hasn't dropped down even after dedicating so much time to YT.

For the top-100 participants, how is the points calculated? I mean the sequence {$$$1000, 706,575,497,443,403,371 ...$$$} apparently makes no sense. Or does it?

It actually does!! Being a competitive try to find what are the cons of making this sequence in decreasing AP :)

$$$\left \lfloor{\frac{1000}{\sqrt{rank}}-rank+1}\right \rfloor$$$

This function seems pretty interesting, it is ranged between 1000-1 for rank 1-100, also the decay seems fair. Is it the only standard function used for such scoring or there exists more ?

Thanks

If you want fair decay..Why not use...

$$$ points = \lceil{-\frac{ 111 * rank }{ 11 } + \frac{ 11111 }{ 11 }} \rceil$$$

Is it always an integer ? I can't see a clear cut proof.

Ceil function is there.

Because the difference between 1st and 2nd place should be much larger than the difference between the 99th and 100th place.

Yeah, that makes much more sense.

waiting for this contest after global round 7!

and hoping to get t-shirt!!! good luck to all others!!

Waiting for this contest before global round 9!

*_*

Hey, I am somewhat new in Codeforces. I want to ask that ofc my standing will be lower comparable to other Div. 2 rounds, so will it affect my ratings in a negative or positive way?

your rating is based on how you do compared to other participants not your rank. You can read more about it here link.

`Codeforces and Polygon may be temporarily unavailable 2 hours starting from July 18, 05:00 (UTC) due to infrastructure updates.`

I think it should be June 18 ? MikeMirzayanov

Deleted

can someone post previous contest Links by Endagorion.

https://codeforces.com/contests/writer/Endagorion

i hope

"pretest passed"and"accepted"will not follow the rule of social distancingActually this was really fun. Surprised that you got downvotes.

no problem, but for coders coding is real fun

The tourist Is Coming

Is there any chance that the contest will be canceled?

No bro, there's not a 1% chance that the contest gets cancelled.

Hope so.

Please check previous comments before commenting something, don't post same repetitive comments and memes in the same blog.

Remember, it's Codeforces, so don't make it memeforces or spamforces :(

Wow! The score distribution for the last problem is almost equal to the score distribution for the first 4 problems!

Good luck everyone!!

Scoring distribution: 500 — 1000 — 1500 — 1750 — 2500 — 3000 — 3500 — 3000+1500. Actually, I am not clear about "3000+1500" part.

May be at that problem there will be a sub-problem also. Like B1, B2 type.

I don't think so, otherwise problem count must have been 9. There might be possibility of subtask1 & subtask2 with partial marking.

B1, B2 count as 1 problem.

MiFaFaOvOvstourist... who will win today ??and I am tourist supporter <3

CODING.

delayed 10 m !

very thanks

More 10 minitues!!

Last five minutes delays are the worst thing ever.

what about cancer?

You sit there like pumped up with adrenaline. And then you have to start all over.

That's why it's delayed 10m

Oh boy the queue will troll us again huh?

hope for that's won't be happened .

Let's hope that this delay is not a sign of long queues

hopefully queueforces 2.0 doesn't happen

10 min delay?

Seriously why does Codeforces like to delay contests in the last minutes? It's really ruining the momentum and the "zone" :(

So that we can have a short contest of commenting about the delay.

They don't like to delay, there must be some problem. A delay is much better than an unrated round.

It's called ritual.

postponed for 10 mins?

Round delayed for 10 minutes.

The delay is like the apocalypse trompettes before a round.

I got electricity cut and contest is delayed. Hope electricity returns in 10 minutes....

They were notified of your power outage and delayed it for you.

https://codeforces.com/blog/entry/76348?#comment-609368 Looks like this is the case with you in every contest, XD

Hope queue don't play with us.

No queueforces please :(

I hope the round doesn't get cancelled. Fingers crossed XD

If it gets delayed by 10 more mins, I'm gonna have my dinner.

Should have gone for it:(

Wouldn't it be amazing to know what exactly happens when codeforces is working on it's infrastructure? Anyone? Just curious :)

I hope this round will go without any problem and no more delay

Comment section nowadays

Apparently this post is included :(Too Difficult.

The second one is kinda tricky

yea, I'm getting rekt at pretest 3. C was easy tho. Sometimes I don't understand question ordering.

What the hell is this 2nd problem?

Same thing :/ but I figured it out 10 minutes before the end :)

That gap between D and E. Oooooooof.

Solved 4 Problems and left the contest.

Speed-forces for non-red coders. >_<

What a mess I've done? Hope others did well

Nice problems, but it is so demotivating when you just sit 2 hours straight not even coding something...

really.... i think my solution of E is correct... but wrong answer..

For example u have:

Let’s write it in bits:

turn on gravity for let bits fall down and stack at each other, now u have:

Now u just need to sum squares of this numbers

Python code:

Damn, that's crazy visualization. Great work!

When i figured this out, i was like: WHAT? THATS GENIUS

This is the best explanation to a problem I have ever seen.

I made a video explaining problem D because I really liked the problem — https://www.youtube.com/watch?v=oHgcHjk2fIM

There are many people with these videos, so let me know if it's worth doing more, thanks!

(Well, I liked problem E too, but I didn't solve it)

By any chance, were the rooms decided based on rating? Mine only had me as >= CM and 2 blues rest all cyan or below.

Why limit in E is 4/7, not 4/6? ;.;

If 4/6 this is Problem A/B :P

How?

How do u do it in 4/6?

Iterate from 1 to n. If the current node is not deleted then delete the adjacent nodes of the current node and keep the current node. It will be true because we are always deleting maximum of 2 nodes but keeping 1 node

Let's color the graph in 3 colors such that vertices of the same color don't have edges between them. You can do this from right to left. Then delete 2 smallest sets.

These problems are good. Great round! Took me a long while to find the idea for C. I tried so many things lol. Can anyone share ideas for D?

For D you can just count number of bits that are 1 for every position and then construct from them biggest numbers.

What was the catch in Problem B?Can anybody explain?

2 * 2 * 2 * 2 * 2.... generates longer subsequences than 1*1*1.. *n for a smaller cost, so greedy check 2*2*2*2 and then 3*3*3... (keep on incrementing so 4*4*4... and 5*5*5... etc) until you're ready (you can mix different numbers suchas 2 * 2 *... *3 *3 *3

How to solve E?

Judging from ecnerwala's solution, it is just greedy. And that's where I first realized that

"landing spots on the mountain numbered from 1 to n from the top to the foot of the mountain":facepalm:It's a construction problem with large constraints, of course it's greedy. That doesn't help with finding the correct solution.

KSM problem C

What is meant by KSM?

First time participated in a "global contest", Wow it was amazing, thanks to the organizers

How to solve D? Whats so easy about D?

My approach which is wrong was to store numbers in min_heap, extract 2 and operate on them, store the greater one back in heap. This worked on so many handwritten cases but not pretest 4 :(

Just count the frequencies of bits, then keep on generating numbers using them till they are not finished greedily!

Oh my god now this looks obviously correct, why I didn't see this :O

I also feel the same way.I was roaming here and there with approaches like set and heaps but after seeing this I feel like how can I miss it:(

Short version — For each operation, you are just swapping the bits in the two numbers. In the end, sum of the count of bits in each position will be the same. Hence just do a column sort (assuming you have a 2D array of numbers represented in binary form)

yeah now I realised this from goyalnikhil064 comment. It seems very easy now! :(

count the number of bit, For Loop(n) , Loop(bit) if count of bit is more than zero, you add the bit value in tmp, and ans += tmp*tmp

try this 2 3 5 ans is 58

Please tell any hack case.

You just need to learn concept of gravity to solve Problem D

How to solve E? someone help please

I solved D in 8 minutes and B in two hours, I was trying to increase subsequences using suffix earlier on, but prefix gave a better answer. Really upset! But a really nice round overall!

Lol, didn't expect C to be a pattern based problem. Just print the coordinates and thats it.

was b something about powers of 2 and 3?

We have 10 factors so I did it by making them as close to each other as possible.

https://www.imageupload.net/image/rQ6xS

Don't know how to upload images. Sorry about that. ^^ This is what I got for case 1 in problem C.

Its wrong because 4 gray box have 3 gray neighbours each

yah its wrong just realized.. how to solve it? help me.

Actually during contest I was making for $$$n=2$$$ and it was not working placing them side by side. So I tried putting them diagonally and it worked. After some time I realised it worked. Refer this I exactly did like this : link

How to solve C

Find a correct answer for the case

`n = 1`

. For the rest, build the staircase.Is it... blade in minecraft??

This literally reminds me of minecraft lol

Just look at this

It was basically a problem of constructive algorithm. The major sticking point was to decide which n should have all neighbors grey. I chose them as (1,1), (2,2), (3,3) and so on till (n,n). Now chose all 4 neighbors for them. Some of them might repeat. Also chose 0.0 and (n+1,n+1) because neighbors of first and last point will not have even neighbors

If you take pleasure in blowing 1.5 hours building fancy patterns, you can do it like below (for n = 4).

(After the contest, I saw the other solutions and then smacked myself)

If n is odd.

Thanks

Was that any problem ordering C->D->B. B was really hard.

I'm noob so asking, Is B supposed to be easier than C?

deleted

which test is that supposed to be? 2*10^5 * 2^40 fits easily...

Is there such a test?

((2^21)^2)*2*10^5 would fit in long long.

I mistakenly read the constraints as (2^30).My bad

Very very interesting problems, thanks!

Worst contest i have ever seen!..

every time there's this one guy saying: "Worst contest"

I think he is justified because gap between D and E difficulty wise was large

well yes and I too would've liked to get an easier problem E, but at least it was reflected in the scoring distribution — we knew beforehand that E would be hard!

looks like someone under-performed

How to solve B?

let number of first character of "codeforces" n(1), second character n(2) ans so on. Then, just check for the combination of these n(i) with greedy method for which it reaches k at the lowest cost.

Meaning, suppose for k = 4, firstly, the string is "codeforces" which is k = 1 and every n(i) is 1. then, check if it reaches k with 2 first characters, which is "ccodeforces". (combination is 2*1*1*1*1*1*1*1*1*1 = 2) If not, check again with 2 second characters, which is "ccoodeforces". (combination is 2*2*1*1*1*1*1*1*1*1 = 4) which reaches k and is the answer.

Thanks. I don't understand what happens when k is odd, say k = 3. Are you saying that we check for all from 1*1*1*1*1*1*1*1*1*1 to something*something..?

Yes, you can just increment the smallest value of the 10 (if multiple are smallest chose any of them) until they multiply together to be larger than the target.

In theory you can optimise by finding the largest x where x^10 is less than the target and starting from there, but it's not needed.

How to solve F? I think the maximum of $$$R(n)$$$ is $$$\lfloor \frac{n}{2} \rfloor - 1$$$, am I right?

AFAIK, this is incorrect. Try for larger n, like 20.

Do you think believing is worth more than proving? Don't do this in a speed-solving contests...

I kind of see your point, and that wasn't the intent. Apart from E, do you think other problems suffered from this?

Thanks for your comment. I was not particularly suffered from other problems than E because of the believe-vs-proof issue, but the overall experience wasn't good.

I think B, D, and F have a similar kind of issue to some extent. For B and D the proof is rather easy (?) but the "targeted" contestants for them could have felt upset as I have for E.

F is more approachable by experiments (and indeed I did), which is good. But I submitted without proving no better solution exists. Who proved it would have spent non-negligible amount of time, which could lead to a terrible performance for this round.

The ideas for E and F themselves were pretty nice! (at least for Mathematical Olympiads)

Thanks a lot for your feedback! I have a pet peeve for open-ended problems where the initial direction is not immediately clear. Still, too many of such problems is too frustrating, and they tend to get too "mathy". I'll try my best to balance things better next time.

I proved E,F before coding. I don't like hard-proving problem too in rated contests but I think it was not so hard (than coming up with a correct solution) this time.

I think the proof for D is fairly easy and i was able to do it in a fair amount of time,and since i am the "targeted" contestant for it than i think i am the right person to speak for it.Same goes for B, B involves simple high school mathematics to prove.Sorry for my poor English.

Even B and D many solved without proving.

I found the solution for E, but I can't implement in time —

solution for E : === infinite loop === node i = minimum of nodes There is no edge comming to node i.

## (i's leaf) <= 2,

## (i's leaf's leaf) <= 4

open i and i's leaf / close i's leaf's leaf // opened node / (opened + closed node) >= 3/7 : you always satisfies erase-ratio.

## erase the i, i's leaf, i's leaf's leaf in the graph

Am I solved right?

No, there are complications. For example, suppose you have i, i's leaf and i's leaf's leaf. Then say j is another parentless node, and say j's leaf's leaf is one of i's leaf.

I solve problem C with smallest k value... and after end of contest.. k doesn't need to be smallest. T^T

Mind explaining your solution?

Arthur, please do not manage the ski resort anymore.

What so special about 4/7?

i did some cases and it seems that if you greedy for low cases 4/7 should work because you break alternating connections (so if you find a path of length N break 2, 4, 6, etc) but it fails for larger cases like 28 for some reason or another (i drew 28 vertices and kept on mixing and matching but couldn't find the intuition to solve)

If you remove the ends of all the paths of 2 greedily(starting from top to bottom). Then, if x spots are removed, there will y>=x/2 spots that were before these spots in the paths and z>=x/4 which were before the y spots. (x+y+z >= 7/4x => x <=4/7 n)

No one:

Literally no one:

Me: Scribbling problem C in-contest using online minesweeper

As expected from the founder of TLX

In E, does anyone have a counter for this?

$$$S$$$ = {$$$1,2,3,..N$$$}.

while $$$S$$$ isn't empty

Take smallest numbered node $$$v$$$ from $$$S$$$ with indegree 0, add nodes at distance 2 to the answer.

Delete $$$v$$$ and nodes at distance 1, 2 from $$$v$$$ from set $$$S$$$ and update indegrees.

Rather than choosing {6 7 5 10 12 13}, your solution will choose {6 7 8 9 5 10 12 13}.

Wow, thank you very much, during the contest I absolutely did not understand why E does not work :)

Thanks :D

Editorial for C :)

I did the same but from bottom up

There will be odd neighbors in the corner?

Actually no, for corner squares, there will be exactly 2 gray neighbours (1 in vertical and 1 in horizontal).

Another solution (not mine): 84197299

Nice approach. I did same :)

.

i have no idea how to do E because the only problems i know how to do are greedy LOL

It seems E was greedy :)

seriously? bruhh im kinda sad rip pretest 7

Least binary searchy interactive problem I've ever seen. Really enjoyed that one.

C and E were really nice too, and I don't have any complaints about the other problems. Great work on the contest overall.

RIP my rating.

My solution for C:

TutorialSolutionovercomplicated

Tell me if you suggest a better approach.

That's another cool approach!

fucking piece of shit.

How to solve D?

you have to notice that when we do some operations, sum of array stay the same. So we just count how many bits we have in numbers and solve this problem greedily(sorry for bad english)

that doest seems like a correct explanation the more concrete way is to prove why shifting of a bit to any other will never cause any negative overall effect it is actually easy to prove that!!

Yeah, I proved it during the contest, but I'm a bit lazy, so I didn't want to write evidence here:)

that was too easy for a yellow i guess!! XDD

Here are several ideas that might help you to solve it:

Hint 1If the sum of two numbers is constant, the sum of their squares is greater when the difference between the numbers is greater.

Hint 2For any individual bit position, the described operation allows to "sort" the zeroes and ones among all numbers.

Hint 2.5The sum of two numbers before and after applying the operation remains constant.

I did it this way: Firstly, note that the total number of 1s at every position summed up for all numbers in binary representations is going to be constant. Use these 1s to create as large numbers as possible. For every position, count all the on bits and now greedily make the numbers.

Spoilerfirst, convert to binary

1 — 0 0 1

3 — 0 1 1

5 — 1 0 1

Now, let all 1 bits fall down.

now try to create the biggest numbers from it you can.

answer = (7 * 7) + (1 * 1) + (1 * 1)

Code link

Thanks

Would someone solving same problems on Global Round get better rating change than solving it in a Div2 Round (assuming same problems and same submission time in both)?

Oh, after having so many fast editorials, it feels bad right now to not have the editorial yet :(

Problem F: used some time to find $$$R(n)$$$ in OEIS, but failed

Problem F was driving me nuts, but I have a method that I thought would work. Does this seem like I'm even on the right track?

Divide n into groups of size k. Then, in each iteration, you can turn on k lights: replace any that were eliminated by the opponent, plus 1 or more in the remaining groups. If you keep doing this with groups of size k, you eventually can fill all but (k-1) in every group (and the opponent can eliminate one full group). So, you could turn on (n/k-1)*(k-1) lights this way (and would want to find the k that maximized that).

But, trying to figure out how to adapt that to cases where (n%k)!=0 was giving me difficulty, and I'm not sure that this method is optimal, even then.

I know I should probably wait for the editorial, but I'd love to know if this was close to the right idea...

I used a similar idea.

I divided the lamps in groups of size k with 1 lamp between them. The last group could be smaller. K is found by bruteforce.

Then on each move I turn on all the lamps that should be turned on if there are >k such lamps. The opponent would turn off some of the lamps on their turn, then repeat.

Example: N = 11, group size = 2

Note that $$$k=\sqrt n$$$ maximizes $$$(n/k-1)*(k-1)$$$. This is also optimal when $$$k\nmid n$$$, where you can just let the last group have size < k.

can somebody explain what's wrong in my approach for problem B?

my approach :- initialise an array

cnthaving value 1 for each of the 10 places. do prime factorization of k, then multiply the prime factors oncntelements one by one.for example, if we were asked to make a string for "hello" & k is 360, my

cntarray will look like this [10,2,2,3,3] and answer will be hhhhhhhhhheelllllooNotice that the product of each character's frequency should be >= k.

So for each character choose such frequency's such that they are equal or some of them have differences with others.

Like this, $$$x, x, x,....x$$$ or $$$x, x, x,....x + 1, x + 1, x + 1$$$

Well, I had trouble with it too, but anyways:

First observation, if you multiply the frequencies of the letters, you get the number of subsequences. Here we are considering duplication of letters in adjacent positions. Ex: ccc ooo dddddd eeeeeee fff o r ccccc eeeee ssssss. So the number of subsequences over here = 3*3*6*7*3*1*1*5*5*6 = 170100.

Now to start with, keep the frequency of each letter = 1 ie. the array f = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]. Also have an iterator i, which increments modulo n. So all you have to do now, is as you iterate, increment f[i] and see if the number of subsequences are more than the required number k. Refer to my code:- Submission

Basically think of groups of letters: you want some number of "c", then some number of "o", etc.

The number of combinations possible (i.e. the number of substrings possible) is the number of "c"s times the number of "o"s, etc.

You can start out with one copy of each letter: "codeforces". Then, just keep increasing until the number of combinations is at least as large as the number you need: ccodeforces would allow 2 combinations. ccoodeforces would allow 4 ccooddeforces would allow 8 and so on. Eventually, you can get to 2^10 combinations possible: ccooddeeffoorrcceess at which point you need to go back and start using 3 of each letter, and so on: cccooddeeffoorrcceess cccoooddeeffoorrcceess etc.

The key is to realize that you maximize combinations by "spreading out" the repeats: i.e. it is better to do ccoodeforces (4 substrings) than cccodeforces (3 substrings)

I did this by keeping an array of length 10 that stored how many repetitions of each character would be needed, and just kept incrementing through, keeping the total number of combinations until it hit or exceeded the target number.

once again, didn't read question carefully.

I thought i have to make a string that contains

exactlykcodeforcessubsequences. and thus did prime factorisation.feel stupid now...

it happens. I also misread the problem as exactly k. Luckily I realized that if it were exactly k, then the size of the output is at least k chars for prime k (which is ridiculous for the limits)

According to some mathematical theorem:

if a*b*c=constant then to have a+b+c to be minimum the values of a,b,c must be very close to each other. So doing prime factorisation won't work, instead you find a number whose power is almost equal to k, copy this value 10 times, now modify values by adding 1 one by one, to get minimum answer ;-)

It's an easy proof. Consider the difference to be $$$2k$$$, $$$k>0$$$. Then $$$(x+k)*(x-k) < x^2$$$. If it is $$$2k + 1$$$, them $$$(x + k)*(x - k-1) < (x-1) *x$$$. Therefore the difference between any 2 values should be less than $$$2$$$

Its actually Arithmetic Mean >= Geometric Mean i.e.

`p1 + p2 + p3 + .... + pn >= n x nth root of (p1 x p2 x p3 ... x pn)`

. If we make all of them equal to p, only then LHS = RHS otherwise LHS > RHS.hello bad example because you have to LL in a row.

For "codeforces" word you can just add one char on each positio and number of subseq will be product of number of chars

Do it while your number < K

Nice Minecraft sword reference on C. And D is a very nice problem.

ff

It appears I tied the 30th place with chokudai. How does this work, do we both get a shirt?

Each one gets half of it.

You battle to the death. Let the hunger games begin!