After the long delay (disease, conference and many other things) the new Div.3 round is coming!

<copy-pasted-part>

Hello!

Codeforces Round #515 (Div. 3) will start at Oct/12/2018 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>

I also would like to thank arsijo, Decibit, PrianishnikovaRina and lng11 for help with the preparation and testing the round!

**UPD**: I'll be on the community Discord server shortly after the contest to discuss the problems.

**UPD2**: The editorial is published.

**UPD3**:

Congratulations to the winners:

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

1 | nickyrio | 6 | 165 |

2 | smokescreen | 6 | 205 |

3 | lanven | 6 | 239 |

4 | SodaineGreen | 6 | 242 |

5 | wythend | 6 | 330 |

Congratulations to the best hackers:

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

1 | Gabies | 82:-24 |

2 | djm03178 | 33:-3 |

3 | Laggy | 27:-10 |

4 | wanderer163 | 11:-1 |

5 | antguz | 10:-1 |

231 successful hacks and 322 unsuccessful hacks were made in total!

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

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

A | CopeCope | 0:01 |

B | stafdasca | 0:06 |

C | nickyrio | 0:04 |

D | nickyrio | 0:11 |

E | somanaik | 0:15 |

F | Ohyeeeeee55 | 0:50 |

FINALY!!!

Hope this div — 3 won't be like last div — 3

What happened last time?

Last time?!? When?

Codeforces Round #506 (Div. 3)

He means the latest Div. 3 round :)

I guess sohrabkhufnak ment that last Div. 3 has been held so much time ago that nobody remembers it.

I meant that last div -3 contest was tough enough.. :3

When did Vovuh become Schrodinger?

Sometimes the the number of problems changes right before the start of the round :) It might happen, but in this round (I hope) will be exactly 6 problems :)

Now I understand the true purpose of your profile picture

IT'S TIME TO UP YOUR RATING, GUYS

How can I improve my level to solve C&D?

Practice past C and D problems.

Wow!

About 1 month the Div.3 contest came again!

I feel surprised!

The last Codeforces Round before NOIP 2018. RP++.

Rp++

RP<<1

Div 3 only? Not good.

Finally a contest by my favourite problem setter after a long time. I love Div 3. :)

I've been hating div 3 for a long time ;|

finally div 3 , i wish it will be esiear than last one

Unfortunately, clashing with Snackdown :(

Duration of snackdown is of 3 days. You can easily participate in both

Ohh ..I didn't notice that.

if my rank is above 1599 can i participate in div 3

yes , but it will be unreted

thx

so much pain :P

Thanks, bro :)

SpoilerCome on, come back into Saratov, we miss you

Thanks for another rating round for div2 :)

happy new round:)

High rating & Good luck

Wish you all get +100 rating!

Guess Mike hasn't yet been able to find an algorithm to make that happen...

Some wishes can never become reality unfortunately :(

will this round have any problems with c# like I had last time?

Hope we will get some strong pretest problems. Wish you all high rating.

Hoping for no delay...

I guarantee that there will no delay because of problems readiness :) So there will no delay if nothing special happens...

Thanks Vovuh, I always get +ve rating in your contest.

Good luck!!I hope we will learn alot.

Hey Vovuh, i suggest that you should become Master quickly, because your color doesn't match top contributors's colors, which makes me a little uncomfortable.

Ahah, this makes me laugh :D I will become Master as soon as possible, hope I can do it :D

This isn't Div 3

as I work through a relation of recurrence of order K,

`F0=0`

`Fn= 1 for n=1...k-1`

`Fn = Fn-1 + Fn-2 + ....+ Fn-k`

where

`0<K<=3000`

? such that we can calculate the nth term of the sequence efficiently! I have No problem to calculate the nth term (fast exponentation!..), only problem is that it does not find a way to reduce this equation homogeneous in terms of smaller.... I would appreciate it very much!This Div3A was much, much harder than Div2A typically is. It also didn't have any coding, just math.

Maybe it seems equivalent but not harder.

Wth happend to my brain in problem B

Same, but for me it was an error of index in the vector, it took me like 20 min to find it.

in div(1+2) last contest I solved 3 problems but in div3 Idk why I always become dumper than homer (simpsons)

the problems aren't that hard but it's like my brain gets numbed because I'm telling myself these are div3 too easy

how to solve D ?

start from behind till you run out of boxes .

do you have a tricky corner case please? I have no idea why my solution is failing.

How did you think that you will have to start from behind?

It's specified in the problem statement that you can remove boxes from start."Maksim wants to know the maximum number of objects he can pack by the algorithm above. To reach this target, he will throw out the

leftmost object from the set until the remaining set of objects can be packed in boxes he has. Your task is to say the maximum number of objects Maksim can pack in boxes he has."Use greedy, start from behind and keep a temporary sum, as soon as this temporary sum is bigger then k take another box, if you have an available one, if not then you just end.

in case : 3 2 5 2 5 1 wouldn't the distribution be [1 2] [5] so the answer is 3?

Every box should contain Consecutive elements

I keep reading the problem statement and can't see where was that mentioned.

Any way thanks for the clarification mate.

It wasn’t said directly but you can understand it from the statement .

Well, this round was about ranges.

What is formula dp for problem B?

Is it dp?

You can use greedy

Really ? I wasn't able to figure out a greedy solution during the contest. In the back of my mind i was still thinking that a Div3-B can't be a DP problem.

Now after the contest, i saw a few codes, many were done neatly using Memoization. Can you share what Greedy approach you have used ? And which approach would be easier to Debug here ? Greedy or DP ? (I think DP looks neat enough here)

For every position X that is not heated i look for the first heater from the position X + r — 1 backwards to position X — r + 1. The next X is the position of the heater I chose + r.

For coding and debug DP is better. It is short code.

It is just brute force. Let the array be a.

You take index when a[i]==1. Then you go to i+2*r-1 and go backwards till you find another a[i]==1. and then set i=j for this j. repeat this process and put condition for -1.

Ohh. Thanks

Codeforces Round #515 (Div. 1 + Div. 3, combined)

How to solve C?, I was thinking in a segment tree but i wasn't sure.

I solved it using a deq and map

two prefix arrays for books placed on left and right.

Can you elaborate please ? I would love to know a new way to solve the problem ?

You can map the book ids to a set of consecutive integers which are ordered according to the order in which we put the books on the shelf. (Let's call these integers — "second IDs") (Use a C++ std::list or even std::map for this)

Then for third type Query, you can use the mapping just created and binary search for the second ID of the required book in the second ID collection(Either a vector or a SET) and using the smallest second ID and largest second ID in the collection you can get the answer.

Two arrays for books on left and on right. You can see my solution. Don't think you would need to find an easier one:

http://codeforces.com/contest/1066/submission/44217835

I used segment tree for fun. http://codeforces.com/contest/1066/submission/44219102 If you don't understand the code I can explain with more detail

Can you explain what you kept in node and how did you managed query and update?

I created a center position far enough so i csn go left in every query and never have a negative position. Each node has 1 if position is occupied and 0 otherwise. Every left query ocuppies a node left to the last one and similar with right queries. You end up with a segment tree where leafs look like this: 000...01110111000...000 I save another array where a[id] is the position of the book in the segment tree. Now queries are simple Query from 0 to id (id not included) is the sum of all 1s left to id. Which is what you need to delete so id becomes the leftmost one. Query from id+1 to N which is from id to rhe rightmost node of the segment tree is the sum of all 1s right to id. Which is what you need to delete so id becomes the rightmost one. I hope i explained it well. Good luck!

That's some precious and articulated explanation! Thanks! I just learnt segment tree few days back, and I got accepted following your approach. Learned a simple but effective technique, storing the position in the segment tree to another array. Thanks again.

Contest was so poorly managed. See what I encountered when I opened problem B:

Explanation Part: In the first example the heater at the position 2 warms up elements [1;3], the heater at the position 3 warms up elements [2,4] and the heater at the position 5 warms up elements [5;6] so the answer is 3.

6 2 0 1 1 0 0 1

But there wasn't any heater at pos 5.

Problem Scenerio Part: If n=6, r=2 and heaters are at positions 2 and 4, then Vova can warm up the whole house if he switches all the heaters in the house on.

How can heater on pos 4 warm 3 to 6? r is 2 so it should warmed up 3 to 5.

Asking this, the contest team replied it was an typo and to refresh the page. What about the 15-20 minutes I wasted scratching my head off over the explanation? Why wasn't any announcement made? Assuming the typo was fixed much earlier, what about the people who have had opened the tab in the very beggining? Do I get consideration for that time penalty? Even after replying my question, they didn't make any announcement.

I too left the problem B during the contest because of that. I thought it was not my thing.

I will describe it to you. I cannot make any announcements by myself. Mike was too busy with the Southern Quarterfinal preparation, other admins (or who have access to make announcements, I don't know) didn't have the access to this contest. So how I can post an announcement if I have no rights to do it?

First of all, thanks for explaining the reason. I get it. I won't blame the contest team for this. But definitely CF team should come up with a better system. Giving access to make announcements to contest creators won't be bad for a start. You don't expect this kind of bugs from one of the world's leading competitive programming hosts.

I understand your opinion. In fact I had hold this contest alone and answer all the clarification by myself. Sorry if sometimes you has got bad answers or don't understand my replies.

From your part, I suppose you did what you could do best. Thanks for the quality problems, though.

I Liked the contest, really felt like a Div. 3 competition.

I would like to know if there is Hack data in the D question using the traversal method from the back to the front.

No, this solution can be proved (I will describe it in the editorial) and this cannot be hacked.

Thx

sir there is hacking going on you can't tell these .

very nice contest

The editorial is published now!

P.S. I write this comment because of [cut] of the blog at the main page. Someone can miss that the blog is already published because of this [cut].

Could anybody help me why I am getting wrong answer for Problem C?Submission

My code of Problem B. heaters is working perfectly fine .but instead it shows me WA on test case 13 . while after contest I have submitted the same code .it gave me AC. my rating was not increased due to this . please help me and fix it

here is my code