Hello Codeforces!

On Sep/20/2021 17:35 (Moscow time) Educational Codeforces Round 114 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 or 7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | tourist | 6 | 82 |

2 | LayCurse | 6 | 158 |

3 | LJC00118 | 6 | 159 |

4 | mtsd | 6 | 207 |

5 | mhq | 6 | 212 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | IntoTheNight | 20:-4 |

2 | tzc_wk | 12:-5 |

3 | TsukasaYuzaki | 9 |

4 | SSerxhs | 9:-1 |

5 | Makise_Kurisu | 10:-6 |

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | Ormlis | 0:01 |

B | KPATKOBPEMEHHOCTb | 0:01 |

C | gleb.astashkin | 0:05 |

D | tourist | 0:12 |

E | tourist | 0:21 |

F | Potassium | 0:23 |

**UPD:** Editorial is out

Hoping this to be a Successful Contest unlike previous one, Good Luck to all the Participants & May you get Positive Delta, cheers :)

So Mike fixed the problem and found out the cause ?

So many assholes downvoting these days like do you feel important when you downvote ? get a life retards we haven't seen any information about the problem yet

Very bad words for the community

That's what haters deserve it's not for the community i don't see any problem in the question i asked

ok Jhin, voting these days is unfair! but this isn't a reason to say bad words.

I have seen worst it's not a big deal once a guy wrote to the authors **** you and your contest he got upvotes and his comment didn't get deleted and nothing happened anyway these bad words aren't for who's downvoting now they're right but it's for Who downvoted the 1 rev of my comment

Welcome to Codeforces

Join the club bro. Literally everyone has been downvoted before its not a big deal.

it's annoying when it gets repetitive everytime someone ask or say something i got downvoted alot before but not that repeatedly

Sometimes maintaining silence also solves lot of problems.

That's what I always do but sometimes say what you want I don't care about the downvotes after what i said

it's on mondayyy when we have school :'(

Good luck to everyone!

Educational rounds are usually very good, hopefully this one too. Good luck to all!

I thought you would never post again.

Ok liar.

Is it rated?

Yes, it is.

I thought you said you would never post again :p

Well, contribution is a tricky business

I just troll, waiting for some downvotes :).

I see how it is. You get downvoted by asking for upvotes, and upvoted by asking for downvotes.

thanhchauns2 go big or go bald...

Definitely...

СпойлерFor those who don't know

No matter what happens but for sure, he gained a lot of contribution points with this blog.

He will get positive delta (cf predictor) but not enough for being cm numberofbaldpeople++;

Thank you for this competition, it gives me a chance to advance.

Tomorrow is China's Mid-Autumn Festival. happy mid-Autumn Festival!

ckmkb

So, Codeforces is back

you must check out the blog How to grow in CPBigger Better StrongerHidden...

Tomorrow is Mid-Autumn Festival, which is one of the Chinese traditional festlval. I wish all Chinese participants a Happy Mid-Autumn Festival!

Wishing you a very blessed Mid-Autumn Day!

中秋节快乐

顺便一提

我不是中国人。

😅

Just became pupil in the last contest I gave hopefully I can maintain that today :)

DELETED

Excited for this round! Hope I'll increase my rating today :)

It seems like I'm facing my greatest fear in my first contest.

Spoilerdiv3_master < div2_noob

usually comments start after the round ....

i have always got negative delta in edu rounds lol hope to break the streak

updatenegative again lmao:( b was a nightmare c saved my a*s from nosediving into pupilI feel dumb reading D from last 45 minutes and not even understanding how the answers for test cases are being constructed

same here. today i am able to understand problem D.

Don't understand why my code of problem C works less than 0.2s on local machine with 2*10^5 & 2*10^5 data while TLE on testcase 6...

can you tell me how do you test for such large test cases?

there are different methods just go into google you will find stack overflow articles according to each language..

Hello , in B : 2 3 4 . So why max pair is 6 . I just see AABBBCCCC , and max pair is 4 Can you explain it for me ? Thank you so much

AAA --> there are two pairs (0,1) and (1,2) AAAA --> there are three paris (0,1), (1,2), (2,3) for n --> there are n-1 pairs.

2 3 4 --> (2-1) + (3-1) + (4-1) = 6 pairs!

A block of n consecutive letters contains n — 1 pairs of equal characters; so AABBBCCCC contains 1 + 2 + 3 = 6 pairs of equal letters. If a letter coincides with two of the same type, it is counted in both pairs.

Ah i already have the answer , but thanks guys

Maybe you didn't use

`ios_base::sync_with_stdio(false); cin.tie(0);`

I got TLE twice because of that...i got 6 TLE...

Hey!

Is weightage for every question the same in Edu rounds?

Yes

Hope I can return to the candidate master.

Finally reaching to Pupil. Hopefully will reach the Specialist too soon.

i don't understand how 4700 people solved C.

It's easy, but I don't know why I always get TLE...

Yep, I also got a weird TLE verdict, but after placing the "Fast C++ I/O" stuff I got AC.

Thanks very much for this "Fast C++ I/O"... I got AC after adding it. But I'm really disappointed that this becomes the key point of AC or not...

the time complexity is about O(nlog(N) + mlog(n) )

.

Thanks. This is much faster. I never know it impacts so much.

just because i didn't added fast I/O i couldn't solve C :"(

It's as simple as x+y — (sum of strength of all hero's) ,but since the values may over flow on addition, you need to do subtractions first. There will be two cases you just take min of both. Got accepted without fast I/O too.

It was a just a implementation problem, it did not involved any particular algorithm. I and most people got stucked in choosing minimum condition else 7-8k submissions was not a big deal.

{deleted]

How the heck we generate the 'M' sequences in D ? given that we have taken the difference between last element and every element for each item and sort it in increasing order ?

I am sorry to be "that guy" but I think your question isn't very clear. I'd happily help (I solved D) but I can't if I don't understand the question!

i tried to use some priority_queue strategy. Start with a vector which contains all the last element of each array and on each step decrease one from a spot and recalculate the sum. think about (x,y,z,SM) -> (x-1,y,z,SM1),(x,y-1,z,SM2) (x,y,z-1,SM3) (and the priority queue is sorted by the SM) (i dont know if its correct but that was my idea)

I used a BFS ( sort of ) with a priority queue. Initially, i inserted the max sequence in the queue with its cost.

After that, i kept on processing the top of the queue ( max cost ) and inserting its possible children ( i.e. 1 position different from the parent ) into the queue. Ultimately, since we are using a priority queue, we will visit the nodes in decreasing order. If we ever hit an unmarked node, we can return.

However, we need to be careful about TLE and MLEs. In order to avoid those, i trimmed the priority queue ( used a set ) from the lower end, if we exceed a MAX LIMIT ( 1.5 mil in my case )

Oh Geez!!! Is it that simple ? Thnx.

Did a very silly mistake in D. Nice contest btw AC solution: https://codeforces.com/contest/1574/submission/129422495

Use set of Vectors

The only thing problem C educated me about was that even 1e18 is not enough to keep as infinity in your template

In what cases the answer can exceed 1e18?

You've got just 2 warriors of strength 1, the dragon has 10^18 atk and 10^12 def. The answer is 10^18 + 10^12 — 2.

just use const int inf = numeric_limits::max();

It will work fine even with #define int long long

Do I deserve them? Thanks for so many downvotes! It`s make me feel happy.

I`m really bad man. Do you think so?

In C, my O((m+n)logn) solution gave TLE on the 6th test case. Any idea why?

Perhaps you have a logic mistake in your algorithm. I thought I had it too but it turned out that I made a mistake and had to think of a different way to save myself from checking all exponentially many possibilities.

Edit: oh, derp. I misread and thought that the question was about problem D. Sorry!

same but i somehow passed it by using fast I/O and "\n" instead of endl.

cin/cout are slow operators. Better use scanf/printf (cstdio library), or add ios_base::sync_with_stdio(0) In the beginning on your program, which boosts iostream performance (but beware of combining iostream/stdio in one program!) Just google "how to boost iostream", you should find some tips easily.

How to solve D?. I thought of using max heap but was getting the wrong answer in test case 5.

Me too, I was using a max heap too but also get a WA on test 5

I did a very silly mistake

AC Solution https://codeforces.com/contest/1574/submission/129422495

thx and I also did a very silly mistake(

ACed now

View a build as a vertex in a graph (or rooted tree), there is an edge between two builds (vertices) if they only differ in one slot by 1, and the edge's weight is the strength difference of the two builds, then we can perform something like Dijkstra on the source, which is the optimal solution if there are no banned builds (the build consisting of the last item in each slot). we iteratively find a nearest (with lowest strength loss) new vertex (build) like what Dijkstra's algorithm does, and as soon as we find a valid build, print it.

Meaningless F with the easiest gf knowledge

What is "gf"?

I think it is generating function.

something I don't have :(

https://codeforces.com/blog/entry/92536 :)

well… it would be easier if one observe that there are at most O(k^0.5) kinds of length.

Yeah, this is how I've seen this problem solved before. I'm interested in how you would do it with GF, is the complexity better?

Removed.

I'm weak in GF, so you can ask ieeMeowCon for more information.

Let $$$A(x)=\sum\limits_{i=1}a_ix^i$$$ be the OGF of subarrays, $$$a_i$$$ is the number of valid subarrays whose length is $$$i$$$.

Let $$$B(x)$$$ be the OGF of ways to make the whole array and $$$[x^m]B(x)$$$ is the answer.

It's easy to show that $$$B=1+A+A\times A+A\times A\times A+\cdots=\sum\limits_{i=0}A^i=\frac{1}{1-A(x)}$$$, so you can compute the inverse of $$$1-A(x)$$$ in $$$O(n\log n)$$$.

nice problems but i'm wondering why my f is wrong answer on test 13 QAQ

In problem D, I was stuck on this approach and was getting WA on test 11. Here is my approach: We can see that $$$4^{10} > m$$$. Initially we can consider the case where we take all the last elements. We define a variable $$$p=1$$$, denoting total number of ways with current elements. Then we can greedily add elements to our set from each row until $$$p \leq m$$$, each time we add element from such row which has largest latest element (from end). Then we can generate all sets and maximize our answer.

But I can't understand why this approach is wrong. :(

If I understand your solution correctly it is similar to the one I thought at first.

Why do you think adding the element from the row which has the largest latest element produce the next bigger permutation? I believe this is not always the case.

I think I did not make it clear. Let's say we take $$$x_i$$$ (number of elements that are available for us) elements from $$$row_i$$$.Also we take all the elements that are equal to the last element we entered. Then we stop when $$$x_1 * x_2 * ... * x_n > m$$$. Now, my claim is that any other combination which contain some element from some row $$$i$$$ such that it is out of reach of $$$x_i$$$ elements, then it would definitely give smaller answer than the minimal combination that we can form if we do not take elements outside of $$$x_i$$$. But I am not entirely sure about this claim.

[Edit]: Well I found a testcase which prove my claim false.

Test caseMy solution is similar to yours which was getting WA on test 13. Now I know why I was wrong.

Please see the test data below—— 10

1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

1000 ...(992 elements 1) ... 1 1 1 1 1 1 1 2

1000 ...(992 elements) ...993 994 995 996 997 998 999 1000

We can then ban all combinations of the last element in the first nine lines and the last 5

(or any other element greater than 4)elements in the last line to hack your solution5

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 999

1000 1000 1000 1000 1000 1000 1000 1000 1000 998

1000 1000 1000 1000 1000 1000 1000 1000 1000 997

1000 1000 1000 1000 1000 1000 1000 1000 1000 996

you will get Wrong Answer because you have to take the element —— 995 but you don't.

I'm sorry. My English may be poor.Thanks :)

How to solve B?

Find minimal and maximal number of adjacent equal letters, everything is possible in between.

I saw almost everyone solved the problem as you've said. Is there any

theoryrelated to the problem? I want to study the topic in a bit more detail. Thanks in advance.I guess the

theoryyou are searching for isGreedy AlgorithmsandMath.That's because the concept behind "find min and max number of ..." is that we can always arrange the letters

in a greedy way(you can consider how you might arrange (a, b, c) = (10, 2, 2) to get the max/min possible adjacent equal pairs)After figuring out the above, you may also realize that you don't need to simulate the process but rather can solve it by some

Mathproperties.Thank you so much !

WLOG assume a >= b >= c so the max possible same pairs will be in case like aaaabbbbccc => such pairs can be counted as ( a-1 ) + (b-1) + (c-1) = (a+b+c-3) so m<= a + b + c -3 and the min possible pairs will be in case like abacabac in such a case the possible same pairs can be counted as (a-b-c-1) so m >= a-b-c-1 so if m is in between this range we can always have an answer or else no answer

actually the min possible pairs should be abacabac... rather than abcabcabc...

Thanks for the correction

How did we derive the min (a-b-c-1)??

if u see the minimal case 'b' no of a's will be utilised 'c' no of a's will be utilised so we will be left with a-b-c number of a's so the no of pairs that can be formed is (a-b-c-1)

Simulate the problem. Try taking only 1 number of a,b,c. Then check for which value of m we can get "YES"... Then try with 2,3,4 numbers of a and rest if them are 1 b and 1 c.... Now check for different values of m.

Note: If we have

1 1 1andm = 20.. Is it possible to achieve something like this? So we can conclude that there must be some range or largest value of m for which we can't find valid string. Now try to find out the maximum range ( upper value). Similarly we can say we must have some lower value of m for which we can get valid string. So the problem requires you to find the range. If m lies in the range then you should print "YES" otherwise "NO".

terrific terrific terrific terrific terrific terrific terrific sample cases

I can't believe I forgot how to do knapsack with items appearing arbitrarily many times and sum of weights a small number >_>

At least I'll remember it now in the future, very educational round :)

+1

But you can still solve the problem by using FFT or polynomial inv if you haven't oberseved that

How should I improve myself to solve problems like B?

Solve B problems on a2oj ladders

Just keep on practicing the questions of the rating that you are targeting from the problemset try doing at least 30 problems of that rating and also try to give every contest either live or virtually for getting the feel of solving problems in contest. Hope you will soon be able to solve B in contests :)).

i don't have a good solution but when I get stuck on problems like that I generally open paint and try to visualize the information that's provided, and that really helps me out.

edit: practice of similar questions through ladders helps for sure

Could someone explain the first sample of F? The way I'm interpreting the problem, the answer should be 0. Since any valid array a needs to have as many [occurrences of $$$A_1= [2, 1, 2]$$$] in it as [occurrences of any non-empty sub-array of $$$A_1$$$], in particular it seems that our array can't contain the number 2. Since $$$A_1$$$ itself has 1 occurrence of $$$A_1$$$ but two occurrences of [2], which is a nonempty sub array of $$$A_1$$$. And then we are banned from using the number 1 as well since it's contained in $$$A_1$$$ and we can't make $$$A_1$$$. And then similarly since $$$A_2=[1,3]$$$ we are banned from using the number 3 and it's impossible. What's the right way to read this?

First number is the size of an array.

I really liked the problem C (cool implementation of binary search + some key observations). However I did not like the difference in constraints of attack and defense upper limit ( the attack can be as high as 1e18 and defense up till 1e12).

When I first read the problem , I read only the defense constraints (1e12). I reasoned that since was n was also only till 2*10^5 , the answer can never exceed 1e18. So I took 1e18 as INF. I submitted my solution with INF set as 1e18 only to receive a WA . I reread the problem , couldn't figure out a problem until I saw the constraint on attack. Quickly changing some code I submitted again and got AC.

In hindsight I should have been more careful while reading the problem and there was no fault of the authors , however if possible from the next time this can be avoided.

Hi everyone, any pointers on how we can solve B? wasn't able to come up with any approach for it.

Think in the maximum amount of adjacents with the same letter and the minimum amount of adjacents with the same letter. Then check if

`m`

is in that range.Hello , in B : 2 3 4 . So why max pair is 6 . I just see AABBBCCCC , and max pair is 4 Can you explain it for me ? Thank you so much

Of course, A-AB-B-BC-C-C-C. The

`-`

means each adjacent with the same value, so is 6Ohhh, thanks man

Find the minumum and maximum number of pairs you can make with given values of a,b,c and if m is lies between maximum and minimum then print YES otherwise NO.

How to solve E?

Can someone explain what does the following line mean in tourist's submission 129351289? I'm literally this line away from solving D :(

EDIT: seems this line is not very crucial, my original implementation was not fast enough.

Nice problemset, specially loved

problem Cbut I think it was a littleimbalanced.Personal opinion, there was a clear gap between problems

CandD. If I were to set points for this set, I'd set:I think people messed up c ,which making a choice for minimum among lower bound and previous to it, other than that it was pretty straight-forward

Phoenix_021, exactly!

I made the same mistake first time around, did not consider the value left to the lower bound. Cost me ~10 minutes to debug and correct, but it was fun.

Last line of problem C. I need to keep this in my mind. This silly mistake cost me very much I am going to kill myself.

Write lots of weird stuffs on problem D and suddenly realized that I had just "invented" trie again.

Is there any easier approach for problem A than this one? I couldn't come up with idea immediately.

codeI took embarrassingly long too! I had it slightly differently.

Here's howInstead of generating a sequence of i nested parentheses and then another sequence of n-i nested parentheses, I did first, a sequence of i nested parentheses and then i sequences of the string "()" haha.

Yours is better. And, well, you must admit, this is a very simple few lines of code. It's just that problem A was probably not the usual stuff you'd expect and that's why it took so long to think of!

You can use next_permutation function with the base string of all opening and then all closing brackets for example n=3 ((())).

i using cout_cin in contest = TLE 6 https://codeforces.com/contest/1574/submission/129409353 i using printf_scanf after contest = Ac https://codeforces.com/contest/1574/submission/129417724

lol

Just add

at the beginning of the main function. This boosts iostream, but makes using both iostream and stdio dangerous, as the two are now desynchronised (as the name of the invoked method implies).

it's work thanks

C tests are bigger than 1e18? :|

Yes.Otherwise it will be WA on 3.

yes. think about strengths are all 1 and x and y are 10^12 and 10^18. so just make it x + y.

I used MAP , HASH , priority_queue and greedy in Problem D.But I haven't solved it. So I'd like to know whether Problem D has a high point of about 2000? I think it is much more difficult than Problem C.

I want to kill myself . Missed AC on D by a stupid mistake $$$ if(z >= ans)$$$

AC Solution

Wrong Solution

This is the moment when we can start questioning about our existence.

Just do it. — Nike

https://codeforces.com/contest/1574/submission/129407156 nice submission from alt to hack by yourself

https://codeforces.com/contest/1574/submission/129419462 Hey Guys, noobie here.I thought I solved c in (m+n)logn but getting TLE on test case 4. Kindly help

Hi, so I have a question for the community as well, the answer to which influences your case.

I see that the limits for a solution are the same regardless of the language in which the solution is written. Does that mean, that using Python (without extensive Python optimization knowledge) instead of a much faster (in common use) language like C++ can greatly influence scores on CodeForces?

I am asking this, because this is exactly what happens on another competitive programming website on which I am a regular organiser (instead of participant) and thus, we don't allow Python there.

got AC after changing input :(

Try adding this template:

Spoilerand use stdout.write(str(ans)+'\n') instead of print (important if you print more than 100000 times).

But yeah this problem had a tight time limit for python. Had to switch from pypy to regular python 2 to get AC.

nice last time solved B C and couldn't solve A , now i solved A C and couldn't solve B >:(

does any one coded A using swap function!!

codeint t;cin>>t; while(t--) { int n;cin>>n; string s (2*n,'0'); fo(i,0,2*n) { if(i%2==0) { s[i]='('; } else { s[i]=')'; } } cout<<s<<nline; for(int i=1;i<2*n-2;i+=2) { swap(s[i],s[i+1]); cout<<s<<nline; } }

Just replaced cin and cout in problem C with scanf and printf, and it worked. Just wish I had tried that earlier (>﹏<）

If you want to keep using cin and cout add these two lines at the beginning of the main function:

As far as I can remember these lines desynchronise iostream and stdio and perhaps do something more which makes using both input methods dangerous, but as long as you are using only cin and cout and these two lines, you shouldn't run into any time limit problems caused by input/output.

thank you.. ill look into this

The fact that the last round had an unexpected (unknown) error, and this round just after 2 days went flawless is one of the reasons I love cf. Great work.

The Pretest runs for the first 2 problems actually seemed smoother than usual, with almost instantaneous results.

I think it should be a hint in problem c to use fast input output but it was a good contest many thanks for problem setters for clear requirements!

B. Combinatorics Homework

`Input:`

1

1 1 3 2

`Judge output:`

YES`I think the output should be:`

NOBecause you can't make 2 pairs in the context.

[abccc]How can you make 2 pairs? Can you please specify your string that satisfies?A brief explaination would be appreciated. Thank you.

'ccc' is 2 'cc' pairs, they just share the middle 'c'

edit: 'adjacent' was probably technically incorrect...

Yes bro.

exactly

msuch postitionsithat thei-th letter is equal to the(i+1)-th one.I could have put more attention to this line. I think CP isn't for me and i should leave now.

`:-(`

For what it's worth, this contest was still meant for div2 despite whatever connotations 'edu' might entail. I wouldn't sweat some brick-y outcomes.

As for quitting, I'm a fan of people doing things they find intrinsically rewarding rather than pushing themselves due to extrinsic reasons or ego. There are also other cp sites besides codeforces if you want to try atcoder ABC's for instance. Either way, I can only hope you find what works for you.

in the string abccc the chars at pos 3 and 4 make a pair and the chars at 4 and 5 make a pair

Thank you... I am a noob.

When io issues aren't just affecting python users...

I don't know why my program with same time complexity as others which passed don't work. Can anybody please explain why this is happening. This is the link to the code.

Your getmin function takes a vector a directly, so it makes a copy (which takes $$$O(n)$$$) each time you use it, if you change it to take the vector by reference (just adding an

`&a`

) you'll get AC.Here is the corrected code 129426111.

Thank You very much. It was really helpful.

Why did this did not worked for C? https://codeforces.com/contest/1574/submission/129409251 I have seen few submissions which follow the same approach and they got passed. Can anyone plz help?

If you use

`cin/cout`

for input/output,`ios_base::sync_with_stdio(false); cin.tie(0)`

should be your best friend.Here you are 129426352.

Can someone hack my C 129392269

Can anybody tell me why my solution to D is failing?

I iterate over all the sums I can get with those numbers, but in order from maximum to minimum. As soon as I have a solution which is not 'banned' I print it out. I guess it should work.

In priority queue I keep two values (sum, chosen items).

EDIT: I had a little bug but now after fixing got TLE. But why? I think I should find the solution in $$$m$$$ operations.

Solution

You are adding repeated states to the PQ. If a build is already in the queue you can skip it.

Yep, fixed it, silly mistake :(. Thank you by the way.

Nice, btw you can only store the build (in the set of visited), the sum is not necessary since it can be deduced from the build

So you mean to change the pq comparator?

That would indeed force you to change the comparator and I think it wouldn't be worth it because:

You'd have to recompute the sum of the values every time you need it, which increases the time complexity constant, which isn't good, and

You'd lose time on writing a custom comparator which is not exactly the easiest thing to do and can easily go south, so unless you've already done similar stuff, it's risky, and even if you've got experience with that, it's still a waste of time during the round.

The only "pro" of this approach would be to save some memory, which is negligible. Much more so than the time you would otherwise save.

No, I mean that the set you added can be only of

`vector<int>`

. Instead of`pair<int, vector<int>>`

:)Oh, got it. But I feel like my approach is better. Even if we are in CP, I think that vector or any kind of collection should hold the values from the same context.

This would then require a custom comparator, though. Unless you do another funky thing and let the strength be the first (zeroth?) element of the vector.

Can Anyone help me find error in my code i'm getting wrong output format Unexpected end of file — int32 expected in Test 6.

My approach is: I'm starting with the vector having the highest build(i.e, all the last elements of all rows say top layer) in the priority queue then for each top element of the priority_queue I'm pushing all the new vectors with a new element in one of the rows that can be formed from the next lower layer with the build value of the vector at the beginning of vector.I'm pushing popping until i get a vector which is not in the our set of bad vectors.(soory for bad explaination >_<)

CodeUPD: I was storing some same vectors multiple times. Accepted Code.

Problem C has taught me that qsort TLEs and std::sort doesn't

Yes, because the Quicksort algorithm, while having "quick" in its name is not that quick after all.

Firstly, its O(n log(n)) complexity is just the average case, although admittedly by randomizing the pivot, the only thing stopping your case from being "average" is EXTREME bad luck, so this is negligible. But...

Secondly, std::sort is a wicked hybrid algorithm optimized for all kinds of stuff and well... it's faster.

Seems like tests for problem F were super weak, I hacked many reds without even knowing the question

Spoilerhow can you prepare test cases without knowing the question???

p.s. i have never hacked so no idea

Knowing constraints is enough info

My solution to problem D using

triedata structure. First of all construct a trie of the banned combinations. Now we will be iterating over each banned prefix(using adfson the trie) and take the remaining values the maximum possible. Here is my submission. Hope it helps someone. Submission:- https://codeforces.com/contest/1574/submission/129429122"and take the remaining values the maximum possible"

could you please explain this?

Basically ,what I am trying to do is that go to every prefix which is banned. Now let's assume till index

x-1you have taken the banned prefix. Now, for the index x, you will choose the largest possible value which can be taken for that particular index, such that that the prefix upto index x is not banned. Once you have taken that, for the remaining indices, fromx+1 to n,you can just take the maximum value among all possible values for each of the indices (x+1 to n).Nice idea, thanks!

Based on how you explained it here, I think I have the same! Pretty interesting to think of it as a trie. Then again, I only "know" trie in theory and never consciously used it.

Can you please explain your dfs function?

In the dfs function, what I am doing is that I am going to each node of the trie. Now, this node represents a banned prefix. Now for this banned prefix I will choose the maximum value for the next index such that the sequence doesn't become banned(in my code it is done using the x variable inside dfs function). For the remaining indices ,I am just taking the maximum (stored in the suff vector).The

nowvector stores the current prefix(banned obviously). Hope it helps.Thanks.

Almost the same approach but used hashing in place of trie ( as I dont like pointer much ). MY_SOLUTION

I think my solution for problem D is kind of different. I passed pre-tests by using

the pigeonhole principle，brute forceand a trick.At first, I got a

wrongobservation: if $$$\prod_{i=1}^n x_i > m$$$, then we can only consider the top $$$x_i$$$ equipments for the $$$i$$$-th slot, because according greedy and the pigeonhole principle, the answer must be already considered. And $$$\max_{i = 1}^n x_i$$$ can be calculated easily by using binary search. Now, we can enumerate all possible builds and get the "answer".After getting WA on test 13 for a lot of times, I find out a case that the observation did not work. For example:

And I think out a trick: for a banned build $$$b$$$, for the $$$i$$$-th slot, replace the $$$b_i$$$ with $$$b_{i} - 1$$$, and then take $$$b$$$ in to consider.

The trick appear to cover cases that the observation did not work, and I do pass all pre-tests.

(Hope that I will not get FST

129449581 got accepted But 129414197 didn't

There is difference in only one line of program.

When i used (long long) 9e18, it passed. But when i used LONG_MAX i failed.

Can anyone say me what happened? Thanks in advance!

long max is actually the maximum integer that can be represent in type int which is 2147483647. This number is clearly not large enough for your solution.

Yeah! Thanks man!

in codeforces LONG_MAX is 2147483647 LONG_LONG_MAX is 9223372036854775807

Yayy I finally have a chance to become a pupil, also I want to ask if it's normal for someone to reach pupil after 18 contests?

Where is the official editorial...

hi

How to solve D?

You can use a max priority queue ordered by build strength to generate the most powerful builds in decreasing order.

First push the max build on the queue, then loop. On each iteration, pop from the queue, check if the build is banned (with a map of banned builds). If it isn't output and stop. Else generate new builds by decrementing at each index of the popped build (so at most n<=10 new builds are generated) and push these builds on the queue ordered by their strength (if they haven't been pushed already — can be checked with a map of seen builds). Since the all the popped build are different at most m+1 builds are popped and at most m*n builds are pushed which is fast enough.

Dijkstra vibes.

Can anyone please help me with a test case where my solution for

Bis failing? My solution: 129451176 My approach seems almost the same as mentioned in other comments but still it fails.For test case: 1 4 4 3

Your code outputs "NO" while the correct output is "YES"

Thanks! I also got WA on this test case, couldn't figure this case myself though.

nice problems, I love problem D.

I got the min-max range logic for B.

But I can't figure out what is wrong with my first approach. Can some help me debug it?

Spoiler: CodeGetting WA on testcase 2, 80th. Can't see the actual case: a,b,c,m values though.

Try to put your code in a spoiler tag. It's less rude that way.

Got it, Done.

For this input your solution outputs NO, should be YES

Yeah, I see thanks!

The max-min range is the best way to go for this one.

I wasted 4 submissions because of using

`int`

in problem C :(.

That's not a good idea sometimes the time limit won't be enough with long long

Oh! Sorry I didn't knew about it. Thanks for correcting!

Does CodeForces compile into 32-bit executables? I'm asking because long longs are slower only in that case. Another competitive programming site changed compilation to 64-bit and now there is no difference besides memory use.

But additional memory use is not something completely unimportant. Usually it doesn't matter, but problems can easily be made to require better memory use. I've seen a problem (not on CodeForces) which actually required the use of short ints!

Also, having templates with a couple of useful things like

`#define st first`

may be good (I personally don't use that), having multiple dozen lines of code (more than fits on a screen) as a template is most definitely a bad practice, especially at the lower levels. And it's not like templates help much besides obfuscating your code to protect against potential hacks. You can take a look at the submissions of some of the top people on CodeForces and all of the ones I've seen fit on one screen. Some of them are even a very modest couple of lines. And they most definitely don't have bullshit like`#define int long long`

.can anyone help me why am i getting tle in D?129459481

You need to add some sort of "visited" logic to the queue. Otherwise you will end up trying out the same configuration multiple times.

I modified your solution using a set of vector of ints to implement the visited logic- you can see the modified solution here: https://codeforces.com/contest/1574/submission/129462075

thank you so much

It says that this contest will be rated for div 2 participants but my rating hasn't changed after the contest. My rating previously was 1099 and still is the same. Can anyone please tell me why is it so?

same issue

See after the contest there was hacking phase. After that within 2-3 hrs you can see the changes.According to indian time I would say by 3PM

Oh I see. I didn't know that. Thanks a lot.

Have a testing time after hacking. Please wait.

Why isn't the system testing started yet? It's been 3hr since the hacking phase ended.

The system tests were ran from the very beginning. Notice, how submission status was never "Pretests Passed (3)" or something like that, but straight up "Accepted". I was surprised when I saw that!

Oh, sori sori, I actually meant when will they run all the hacks over the submissions? It had been too late now :/

Still, don't start yet.

I think D is not difficult for someone who know how to use heap,maybe it only can get 1300.

My rating is not increased yet, why??

Great things come out of patience.

Have the ratings been published?

not yet

I wonder why it shows me the game is unrated.

Since every contest ends up with questions like "when my rating changes" it would be great if stage "System Tests" will be followed by stage "Rating calculation". It would calm down a lot of people.

then there will be questions about why rating is being calculated so slow

Adding percentage of progress (like in system tests) could partially solve this issue too.

I guess rating changes applying is manual work, automatic calculations should be pretty fast. But I might be wrong. Correct me if someone is more familiar with system

I do not beleive in manual rating calculation for 20k members. No way.

Yeah, that will be automatic. Any idea by when can we expect the rating changes?

I meant only

applying changesis manual, calculation is for sure automaticSo you used some form of hashing and then stored whatever data you needed on a set either way? At that point I'd use std::unordered_set...

That being said I used a

`set<vector<int>>`

(because std::vector by default compares itself lexicographically) and didn't have any problems with time limits."unorder_set" is really much faster, and I've never used "set<vector>" before, thanks for your advice, it's all new to me!

Yes,

`std::unordered_set`

and`std::unordered_map`

are two STL containers one should always keep in mind when dealing with algorithmics. They use hashing to provide constant time access! However, in a very pessimistic scenario one could potentially encounter data which has a lot of collisions and then the access would have linear complexity. But understandably -- that simply doesn't happen.One another note,

`std::vector`

does not have a built-in hashing function, so it's not compatible with the two aforementioned containers straight off the bat. That is why, during the round, I wondered if vectors are compatible with regular sets and that would be if their`operator<`

was built-in. Just like you, I didn't know, but I opened cppreference.com and looked it up.Another bit of advice: your way of hashing (don't worry, it's pretty much the only popular way of hashing) by taking elements and multiplying them by a constant and then taking the remainder modulo another constant is rather slow, because the modulo operation is slow. So I wouldn't be surprised if using hashing is still slower than using the logarithmic

`std::set`

structure. In fact, looking at your newest submission, that is the case, since it still performs around 3 times slower than mine.Better luck with all this new knowledge next round!

awoo at least provide us, editorial.

Editorial much-awaited!!!!

I am new here, How much time taken by codeforces to update rating ?

It's taking a lot of time today usually 2 3 hrs at max

when will we get the editorial of the problems?

Soon

^{TM}Eagerly waiting for editorial and updated rating !!

Someone please shoot me, I can't wait anymore.

2 !!! Ouf.. wait for the next contest

when is editorial published?

Is this contest was rated for div 2 participent.

Because Till now there is no update in ratings.

Are there any chances of publishing the editorial?

me waiting for rating change and editorial

for the B problems we check whether the given m ranges between minimum possible pairs and maximun possible pairs , but i dont get the intution behind it , can anyone explain it to me , and also does this approach work with similar kind of problems ?

For me B was similar to A, it is slight variation of that here we can have let

mxbe themaxamount ofequal adjacentpairs now we can change the orderging todecreasethe no of such pairs by1tomx-1 and so on..., similarly going till certain value after which you cannot decrease that value of mx , which will act as your minimum value.Yesit works with similar kind of problems .thanks , got it

awoo: please post editorials. For rating changes take your time. but please atleast post editorial....

Dont understand why editorials are so slow. -1

why editorials are so slowBz it takes efforts ans time which you must have not ever gone through,

orz

awoofor such beautiful problemsLol there have been editorials published in a few hours after the contest.

orz awoo for such beautiful problemshow about u solve them first before writing genric nonesense in the comment to get contribution or whateverYes, editorials take a lot of time to create, but I think they should be created before the contest is released.

I got +0 delta :")

For C, I understand that we would have to check for the lowerbound and lowerbound-1 as candidates for beating a defense of x, but why stop there? why not check lowerbound-2? or lowerbound-3? I get that they increase the cost with attacking against the dragon, but they do the job of reducing the cost while defending against an attack of y right? without this I'm not able to prove the greedy approach. any help will be appreciated ! Thanks!

So assume we have $$$n$$$ knights with strengths $$$a_1 \leqslant a_2 \leqslant \cdots \leqslant a_n$$$. Now assume that the dragon has defense $$$x$$$ and attack $$$y$$$, and let's say that $$$i$$$ is such, that $$$a_i$$$ is the smallest of the strengths greater or equal to $$$x$$$. Now I will show why we only need to check $$$a_i$$$ and $$$a_{i-1}$$$ (if they exist).

First, we do not have to check any $$$a_j$$$ for $$$j>i$$$ because using greater attack than necessary will not give us any advantage, but may cost us defense points, and thus gold. I think this is fairly straight forward.

Second, we do not have to check any $$$a_j$$$ for $$$j<i-i$$$ because:

Assume we use $$$a_j$$$. Then, we lose $$$d = a_{i-1} - a_j$$$ attack points, and gain $$$d$$$ defense points. However, since $$$a_{i-1} < x$$$, then it is guaranteed, that we must pay an additional $$$d$$$ gold coins to compensate for the attack. Notice now, that however much we had to compensate for the defense if we chose $$$a_{i-1}$$$, we will compensate

at most$$$d$$$ less if we choose $$$a_j$$$. Thus, choosing a knight with strength other than $$$a_i$$$ or $$$a_{i-1}$$$ will never be beneficial.Thanks for this, and after I pondered upon the problem I was able to prove that for i<lower_bound-1 the cost of gold will remain equal to or more what we got when we chose lower_bound-1 mathematically.

This can be proved as, say for a dragon's attack y, and defense x and a array of the knight's power h, we can have (x-h[i]) coins which will be needed to attack the dragon and (y-((∑h) — h[i])) coins to strengthen our defense, which would yield to a total coins of :

x — h[i] + y — ∑h + h[i] = x + y — ∑h which will be constant for all values of i below the lower_bound — 1. now there might come a point where (y-((∑h) — h[i])) becomes negative, in that case it will be replaced with 0, hence it would be worse than lower_bound-1.

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Auto comment: topic has been updated by awoo (previous revision, new revision, compare).