<copy-pasted-part>

Hello!

Codeforces Round #535 (Div. 3) will start at Jan/23/2019 17:35 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

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

Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) is **10 minutes**.

Remember that only the *trusted participants of the third division* will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participants of the third division*, you must:

- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

**UPD**: I also would like to thank testers ismagilov.code, Nebuchadnezzar, Arpa, filippos, eddy1021 for the great help in round preparation!

**UDP2**: I don't sure about Iamoni so I included top-6 instead of top-5 in the table. And I'm also don't sure that **some** hackers aren't cheat so forgive me if my information is wrong.

**UPD3**: Editorial is published!

Congratulations to the winners:

1 | b31quocbao | 7 | 358 |

2 | GZY_AK_IOI | 7 | 455 |

3(?) | Iamoni | 6 | 101 |

4(3?) | pushkar12 | 6 | 216 |

5(4?) | _DarkDawn_ | 6 | 226 |

6(5?) | Amooo | 6 | 229 |

Congratulations to the best hackers:

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

1 | _bacali | 181:-49 |

2 | Chiakisa | 55:-8 |

3 | CNH_NHI | 10:-1 |

4 | CutieRabbit | 9 |

5 | CNH_NSIS | 8 |

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

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

A | spacewanker | 0:01 |

B | mpstxdy | 0:03 |

C | Iamoni | 0:06 |

D | arpit040199 | 0:06 |

E1 | Iamoni | 0:11 |

E2 | TsingTaoDaTieWang | 0:16 |

F | Zhao-L | 0:20 |

I hope its not like..

DIV2<DIV3<DIV1

Maybe a Div3 = Div1 + Div2 ....

More like Div3=Div2-Div1...

Let's Increase it's value a little Div3 = (Div2 — Div1) * 1.5; ;)

i hope it won't have any useless and pointless math involved...

also may i ask will it rate my rating?

The contest will be rated for you as long as you're under 1600 (now you're 1599). If you took part in today's contest and it will raise your rating — the next Div. 3 won't be rated for you. Half of your comments are complains about maths :D I don't agree with your statement that maths has nothing to do with programming. It has a lot, especially with competitive one. All of the algorithms (e.g. graph theory) come from mathematics. Try to deal with it if you want to have fun from Codeforces.

what are you talking about i am expert

I wrote my comment before the contest results appeared and you was 1599. Now you're an expert, right. Congratulations!

thanks i feel really great now

Round by Vovuh !! Always exciting to participate!

Wish a lot of AC <3

Div3 contest is like a gift for contestants below 1600.

Announcement of Codeforces Round #299 (Div. 2)?

Fixed now, I think :)

Perfect announcement doesn't exi...

[Off Topic] I am trying to practice on my hacking skills for the next contests. Is there any good blog post about how to approach hacking effectively? Some sort of guidelines/best practices on how to hack solutions.

I searched but couldn't find any

Step 1 : study for exam

Step 2 : participate in Cf round

Step 3 : loose 100 rating points because your mind was tired from studying

Step 4 : fail the exam because your mind became even more tired after trying to solve problems

problems are easy in Div3, today I'll be in TOP 20

Is div3 friendly to new people?

Yes, it's without a doubt the best contest new people can choose. But it doesn't mean it will be easy. If you have no or little experience in competitive programming, doing 2 or 3 problems will be a quite good result. Good luck.

Is vovuh nephew of Mike Mirzayanov? Why does he take every single Div3 Round?

Does it mean that participants with 1600 higher rating taking part in Div.3 would not be rated ?

Exactly. We can take part just for fun.

Oh that's amazing! Thanks a lot!

Another div 3 round, which is equal to div 2. In any case, thanks for the prepared problems. Good luck, have a fun. Take care of your feet

You also take care <3

Yet again disappointed by weak pretests >:(

Sorry, I tried to make strong tests in almost all problems and just forgot about you! The only tests among your solutions are in the problem B with answers 69 and 42 :(

Bro just do it like a normal CF Round... please drop that 12-hour open hack feature.

All of your solutions are hacked.Because "if(n==69)return 0;".

Why are you putting if(n==69) return 0; Your all solution are hacked @problem_destroyer420

swap(C, D)

C && D giving TLE in java wow in-spite being O(N) =_=

Changing the string to char array gives AC WOW! okay

-`String`

objects are immutable, which means`ans+='B'`

requires creating a brand new`String`

object and copy all characters, then append 'B' to it.how to solve E2

i think this solution is right though i couldn't find an apropriate implementation that fit in time and memory limit for it...

first you have to prove that the answer is when you choose the segments that doesnt intersect whith the maximum element.now you can fix the element that shoud be the maximum and apply all the segments that doesn't intersect with this element and get the minimum,this can be done using segment tree

I did that in E1 , assumed that each element is a maximum and chose the segments that don't affect that number

However I don't know how to do it in E2 time limit

how can it be done using segment tree ?

you have to use minimum segment tree.

but for the precise implementation,i couldn't get the accept for the problem,i fix the time limit problem by just a little spitting on my code,but that one agian couldn't fit in memory

My implementation with segment tree : 48837273

yes,you used the sweep line trick that i didn't and because of that i couldn't get the accepted

Segment Tree is to slow to fit tle

We do not need a segment tree here, check it out for my solution: https://codeforces.com/contest/1108/submission/48881765

HintLet min is the index of minimum in the array b, and in a we try to minimize a[i] as much as possible. So where to choose the maximum index: max ?

First thing we observe is that we should not decrease the max index in the array a. Proof : if we choose the range that contains both max and min then it makes sense not to choose it, else if we choose the range that contains only max, not min then it is wiser not to choose them.

So if we choose a set(possibly empty) of given ranges that cover the min, we shold choose the max from the left of the array a: either from the prefix [1..l] or the suffix [r+1...n] since the set of ranges we choose all have at least one point in common, which means they form a big, continuous range [l..r].

Consider that the maximum choose from the suffix. Assume that ranges are sorted according to the end bound.

So for each min = 1..n, we choose the set of ranges in the way that expand to the end of the array. Suppose the set we are considering has X ranges and cover to the r-th element of a, then we take the maximum of our current answer and:

maxright[r+1] — (a[min] — X).

Same kindof process for choosing max from the prefix.

Remember to check the corner case of empty set.

Testcase 26 Problem F?

4 4

1 3 1

1 4 100

1 2 100

2 3 1

In my opinion answer should be 0

Even i did not manage to find how to solve

You can see my submission. You can understand easily from the code itself. What I have done is processed the edges after sorting by weight and did a simple DSU.

I was trying to see the components in a single iteration. Thanks for the reply :)

https://codeforces.com/contest/1108/submission/48833560 i got WA on test 26 any help or test case

Try this

6 7

1 2 9

2 3 9

1 3 9

3 4 1

4 6 2

4 5 2

5 6 9

answer would be 1 i think

you are getting 0

Need help on C. I don't know what I did wrong.

https://codeforces.com/contest/1108/submission/48833951

BTW any recommendation for E1,E2 and F???

//swap(D,C). and maybe even swap (D,B). I lost 50 mins on C and just read D and like "Uh what???"

Same feelings, bro

:(You know how can I solve C afterward?

Brute force the solution got AC bro lol

Simply try "RGBRGB..." "RBG" "BRG" "BGR" "GRB" "GBR" and find the minimum among these choices.

That's what I did after I got WA haha

Honestly speaking, as a C, it sucks though. I mean, brute force get AC but "proper thinking" solution got WA????

I think if the problem setter change the distance and amount of number to 5, it will be better

So it's my first time to see a problem which has two types in Codeforces.

(And I haven't solved it/them.:D It should be an easy problem though..)

I don't know about you guys but 12-hour phase of open hacks is certanily the only thing I don't like about this Div.3 contest, why don't you leave that feature for Educational Rounds only ??? You can downvote me, I don't care about that, but I have to say it... is painful.

But this is really helpful to improve your skills.

I think that Codeforces is a site to help you improve your skills, ratings is not the only thing right?

Ok, but regular CF rounds allow you to hack as well, my opinion is that it would be better to leave the 12-hour phase of open hacks for Educational Rounds only and let this div. 3 rounds more like the regular div. 2 / div. 1 rounds. Again is just my opinion. Happy codings to all :P

Can somebody tell me what's wrong with this code on problem E2?

My submission

https://codeforces.com/contest/1108/submission/48801874 i find new thing one of the guy is submitting right solution expect for case n == 69 and he is hacking with another account . please report this user and please dont allow this to happen in future the user is @problem_destroyer420

I did try to solve the problem E1 using DP. but I did not solve the number of segment T^T...

Am I the only one who felt today's Div3 first 3 problems are more difficult than yesterdays Div2 first 3 problems?

I would say that the diffucult is about the same.

How to solve E2?

For every index of the array assume that it is not affected by any of the M updates. Apply all the other updates which don't affect that index and calculate the answer i.e. max — min.

how to do that in E2 time limit

Apply all the queries to the given array initially. Now you can do a sweepline on the updates based on which index they appear and which index they disappear. Submission

Apptica what u mean by sweep line , how u used it . can u provide me its tutorial

You can use sweep line technique. Iterate i from 1 to n, for each i subtract all segments [i, j], then calculate. After calculating, add all segment [j, i] so that next i won't use old segments.

Check all indices in increasing order. For each index, check all the segments and find if the index is the start of the segment. If it is, then subtract 1 from all elements in the segment, and re-calculate min and max and update the answer. Check all the segments again and see if the index is the end of the segment. If it is, then add 1 to all elements in the segment.

Can you explain in some detail why it works? Is it because you are trying to depress the value of the ith element as much as possible, and the highest element e such that e-a[i] gives the max answer can either be a part of that segment or not, if it is not a part you gain one, if it is you dont lose anything since both get devalued by 1? Please correct me if I am thinking of something wrong

Basic principle is to make each element as small as possible. So for each element, you're going to subtract 1 from all segments including that element.

If you check indices in increasing order, the only segments you need to check are the ones you enter or leave. This guarantees that when check an index, all segments including that element has already subtracted while others are not.

Yes, exactly.

Yeah, I solved E1 with that observation. But that gets TL for E2.

no you didn't, stop lying!

contest was so easy :D

Anyone tell me what happened with my solution. I just change string color = "GRB" code (WA on test 4) to color ="BGR" code and got AC?

next_permutation needs your passed array to be in sorted order, RGB is not sorted, but BGR is

That's not true next_permutation prints all the remaining permutation till RGB but as GRB comes after BGR in permutation so it skips it, so if you are thinking that next_permutation won't work if your string/array isn't sorted then you are wrong!

Happy coding!!

what's the dp solution for probD?

State:

`dp(index, prev_letter)`

Transition:

Please check my solution for more clearity.

can anyone tell why my code https://codeforces.com/contest/1108/submission/48851718 for problem https://codeforces.com/contest/1108/problem/E1 shows wrong answer on online ide while it give correct answer in sublime text??

Your int x in line 63 is uninitialized in those min/max functions.

OK Thanks

What is the intended sol in E2? Segment tree with lazy prop didn't pass for me. (tle #15)

UPD — AC. Missed to apply sweep line on updates.

Someone can explain me why my position in standings changes after refreshing the page? Which of these is the official one?

Hello guys :)

cheaters: same code

https://codeforces.com/contest/1108/submission/48814895

-> https://codeforces.com/contest/1108/submission/48841216

One code was sent after the end of contest.

Is notice helpful? because two of my friends are always cheating. Would anyone ban them or something?

sorry for bad English.

one for example

http://codeforces.com/contest/1097/submission/47921374

and

http://codeforces.com/contest/1097/submission/47922209

Can anybody tell me what is wrong with my E?

I tried greedy + segtree.

Like if you want to have ai as the maximum after applying the subset of intervals applying intervals that contained ai would not help and applying intervals that do not contain ai would not damage, so I just iterated over i and do the updates :P

Your idea is right. I think there're some mistakes in you code.

Can you please help me find what is wrong ?

I'll send you a private letter.

Can anyone explain problem F a little , I mean the sample test case 1.

Initially, two kinds of MST are possible. Both uses edges (3,7), (4,8), (1,2), (1,4), (2,3), (3,5). One possible MST uses edge (1,6) while the other uses edge (3,6).

If you increase the weight of edge (1,6), then the only MST possible now is the one that uses (3,6). Same for increasing the weight of edge (3,6) where only the MST using edge (1,6) remains.

If you're not familiar with MST, you'd better search for it first.

Thanks, now I understood the question :)

in B, can answer to test case

4 9973 1 9973 1

be 9973 9973 ?

nowhere it is mentioned x!=y. this solution satisfies all conditions in question.

Yes, it can be.

Thanks Vovuh for this nice contest. Questions were well constructed and difficulty was also gradual :)

*Questions were

Thanks for POINTING THAT OUT :(

Hi guys, i work in c++ gnu g++14. I have a problem with task B. All my solutions when tested by me output correct answers but when i submit them, program always output "0 0". Any idea why is this happening ?

You should only use one I/O library (C or C++) after using

`ios_base::sync_with_stdio(false);`

. i.e. using only`cin`

or using only`scanf`

.Thank you, i"ll read more about it on internet.

copying alert : The submissions of the a/c LightningFrenemy213 and arpan_dg are identical.

How to solve E1 ?

For every index in the array, apply every query that doesn't include that index, to the original array and calculate the difference (max-min).

smart ty :D

How ? Any reason for this approach

What you're doing with this approach is just checking the final states of the array when that particular index is not included in any query that you've applied. There will always be a case when the difference between max — that index element and min — calculated after applying the queries, will be maximum.

This is one approach, there might be other approaches to solving this problem.

why this solution got accepted. https://codeforces.com/contest/1108/submission/48843911

Thats a greddy approach..I did same thing

Why my rating don't update?

cuz there is 12 hours open hacks

O(nmlogn) algorithm of E2 48867037I use some method to decrease the constant, and it exits when time is up.

I can't blieve D is much easier than C,But it's TRUTH :P

nice problems :D

Someone please update Ratings.

Weak systests, my solutions passed

This round was quicker than the previous Educational round !!

User Iamoni coded with friends.

Problem A(48801772)

Problem C(48805698)

Problem E1(48808903)

Problem E2(48822818)

Different templates, different coding styles.

Vovuh MikeMirzayanov

Good catch there. Also the submission times are highly suspicious. Hopefully they will look into it.

can anybody help why my O(n^3) solution for B is wrong https://codeforces.com/contest/1108/submission/48890311

How did you get this approach?_

I tried to make all the pair of x and y from the given array and then checking for every pair whether it satisfy the given constraint for x and y , if yes then print x and y ( I still don't know what is wrong in my approach).

try tests,where x — is 1 and y — composite num

It is working , you can test yourself , I have given link to my submission

Vovuh, will you publish the editorial?

In a few minutes, bro, please wait a bit :)

In a few minutes,

108 minutes ago XD

It is published now XD But it isn't work XD I don't know why XD

How to solve E by segment tree? (PS: When will the Tutorial be published?

A key observation is that there is always an optimal solution that selecting all segments covering a specific index (let us call it

x). To look forx, we can use a sweep line to handle with the segments and use a segment tree to update the answer.You can see my code for more information.

(UPD) It seems that someone has answered the same approach before :(

thx

Problem E1 https://codeforces.com/contest/1108/submission/48893961

Editorial Page is not working for me! does someone else has this issue too?

48837239 — what is the issue with this?

Why are you not sure about [user:lamoni]?

Take a look on this

ok thanks.