<copy-pasted-part>

Hello!

Codeforces Round #501 (Div. 3) will start at Jul/31/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 awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

</copy-pasted-part>

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.

**UPD1**: Editorial is published.

**UPD2**:

Congratulations to the winners:

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

1 | Wavyn | 7 | 245 |

2 | delete4 | 6 | 168 |

3 | BernardoSulzbach | 6 | 212 |

4 | dongshunyao | 6 | 214 |

5 | jiaangk_ | 6 | 217 |

Congratulations to the best hackers:

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

1 | halyavin | 354:-66 |

2 | test616.cpp | 66:-7 |

3 | OlaAdel | 18 |

4 | antguz | 21:-7 |

5 | wanderer163 | 20:-5 |

604 successful hacks and 446 unsuccessful hacks were made in total!

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

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

A | 314rate | 0:01 |

B | 314rate | 0:06 |

C | garipov.roma | 0:07 |

D | shanghaiKingCsl | 0:12 |

E1 | Ka55un0 | 0:30 |

E2 | Ka55un0 | 0:30 |

F | shanghaiKingCsl | 0:48 |

Thanks.

https://www.youtube.com/watch?v=bwAkbAeCXmo&t=10s https://www.youtube.com/watch?v=-RnAxOPjJqo&t=13s https://www.youtube.com/watch?v=gu8DiEBqnVM&t=6s https://www.youtube.com/watch?v=bxchtZSKWJg&t=550s https://www.youtube.com/watch?v=p2UEGMIO3oM&t=464s

First Div-3 contest in 5th century. :P :D

To some extent, from now on, another era of Codeforces starts! :)

*6th

Programmers count from zero XD

31 July is my birthday. Thank you codeforces for this gift on my birthday :)

s

Please reduce the duration of hacking phase.

maybe 6 hrs.

3 hrs.

Don't play ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

"which which"

Please correct it!

Wooops, thank you, fixed!

that moment when you are join virtual get high score then join real contest and get very bad score , why this life is so cruel ?

:( :(

forget to remove something ? , lol

Is this div3 or as usual “div3” is just a hidden div2?

http://admem.ru/content/images/1391120256.jpg

...........................................................................................

So, further Div.3 rounds / Educational rounds' hacking phase will

notcount self-hacks as well? :DHmm, they do count for now, like we manually delete users from the top-5 table who hack themselves too much. Though, I believe, it's easy to fix the tool to exclude these hacks, I'll check what I can do with it.

They count for the standing page but it seems a pretty fair solution to not count them in top-5, all in all.

Edit: Oh, forget about it) I coded this tool in a most disgusting way possible, too much effort needed to fix it now. Maybe when I finally decide to refactor all of it, I'll take that issue in a consideration.

Alright, I thought it was implemented into the system. Well, would be a nice idea for Mike to consider?

Well, not every hack of yourself is a way to cheese the standings. It still might be possible that user knows where his solution fails despite passing all the tests and wants to add the test to the final testset.

Please Decrease hacking time, Hold the Contest intime, Tests have strong arm(s), Check servers for downtime, Hope you enjoyed this rhyme.

contest back2back hip hip array!

What's the penalty for wrong submission?

Read the announcement, please.

Have you changed that?I saw "wrong answer" and asked for TLE,MLE or runtime!!

Are you kidding me? That's a very bad joke.

No man it was a good joke. The problem is you could not understand it properly.

My bad :(

stop this nonsense man...

10 min

it should be ..

copyed-semi_edited-posted

UPD.

No more rounds on the weekends?

"register for the contest" link in email leads to Codeforces Round #498 (Div. 3), don't copypaste this part next time :)

Wow, the funniest thing that this link is copy-pasted not by me :D I don't know but I think Mike sends email manually or using some script/this is automatic process

hacking yourself on purpose to get on the hacking leaders table... that's pretty dirty...

You are an expert. You can not say yourself "Almost Legendary Grandmaster" .

I know. It's a joke...

I don't know how about other participants but i definitely hate when contest held by vovuh or awoo, especially when it comes to div3 or (this is hot one) Educational. From the first sight it seems to be much more easier then regular contests, but when you open the first problem, it's hard as hell just to understand what the hell is going on. Maybe i'm to stupid to complain but I think div3 mainly maintained for GREY or GREEN guys, not for RED. Please make the rounds more doible for us not for them.

http://codeforces.com/contest/484/submission/8757420

TBH, I have an opposite opinion. I'm not sure why, but I feel that vovuh usually does fairly easy problem (for me anyways). I'm kinda looking forward to his contest now

I don't think this problem for div3 contest

Do you have any other examples? Anyway, I don't think it is fair to judge me for such infrequent (I think) mistakes (remember that I am human too and I could be wrong), but you do it and it really makes me sad. But I am also sad by the fact that I can't prepare all my rounds without any mistakes.

Stop this nonsense Vovuh. You have lost all the respect that i had for you.

vovuh, prepare your contests and don't get upset by such comments. :)

It's okay dude. You did a great job. Just keep up the good work. Please all and you'll please none :)

If Div.3 was only cakewalk problems then what is the purpose of it!! How newbie and pupil users will get the advantage of div.3 rounds if vovuh didn't put a little bit harder problems than usual from a time to time:) Anyway if you want to improve your level then you have to solve problems with different difficulties, solving div.3 A won't even make you pupil, I think even a red user won't improve his level if he didn't change the difficulty level of the problems that he solves.And for sure everything happens gradually.

Do you have an example of a problem that would be good as Div3A?

It seems to me you are expecting this site to teach you competitive programming from scratch ("scratch" being not knowing how to code, or how to code competitively). Codeforces is not for that. It's for any level, but you have to master trivial problems to even have a level in the first place (I'm not trying to offend you, I'm just saying you need to try studying before competing). Not even Div3A (and definitively not Div2A) is a "trivial educational problem" such as "sum a and b, a,b <=1000", which you imply would make a good Div3A.

And please, don't shake it out on excellent problem setters such as vovuh or awoo because you don't like their style or had a bad day.

Can someone explain codeforces' system of gaining rating points please (in talks, for example)

So, just checking — if I participate in this, it won't affect my 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.Great work with questions.

What is the third number test case for problem C??

What's in test 4 , on problem F ?

Dont copy whole announcement, copy just link from previous announcement.

how does hacking in div 3 affect the leader board for the hacker?

Just asked from vovuh. It will give nothing to you.

How to solve F?

You can solve it with dynamic programming approach.

Let's DP(i, j, k) be the number of ways to form a regular bracket, we are at i-th position, degree of a regular bracket is j and we are at k-th position of string s.

Answer is DP(2 * n, 0, s.length()).

Passing state:

Consider the i-th position we want to put a '(', if s[k] == '(' then dp(i, j, k) -> dp(i + 1, j + 1, k + 1)

Otherwise we want to find such position l nearest with i and the part from k-l to k-1 is same as 0 to l-1 (we can precalculate it in O(n^3)). Then dp(i, j, k) -> dp(i + 1, j + 1, l)

Same as ')'.

For detail, you can see my solution: http://codeforces.com/contest/1015/submission/41048988

Sorry for bad English.

Edit: a problem using a similar technique having the "maximum prefix that is a suffix of the current string we are building" as a dimension for the dp is http://spoj.com/problems/PSTRING/

We will try to count sequences by the first occurrence of s in the sequence.

Pre-compute nxt[i][c='('/')'] which is the maximum prefix of s that is the suffix of (prefix of s of length i + c).

dp1[i][j][k] = we built i letters, the "bracket depth" is j, and the maximum prefix of s that is a suffix of the current string we are building is k

dp2[i][j] = we built i letters and the "bracket depth" is j

Note that we start with dp1[0][0][0]=1, and instead of transitioning to dp1[i][j][s.size()], transition to dp2[i][j]. The answer will be dp2[n][0].

Is there any suloition using inclusion/exclusion?

How come my N*M*500 Solution passed the pretest on problems E2 ?

Have you have taken min distance of each point from the boundaries and naively checked for a mismatch?In this case,the max no of operations are less than 2e8.

http://codeforces.com/contest/1015/submission/41061197 here's my code

I can't hack , when I click to hack, it is loading and loading..

Try to close facebook and try again :)

Did it , but same problem :'(

It happens a lot to me too. Just refresh the page several times and the hack window will eventually appear.

I had same problem. I avoided it by using firefox rather than chrome. Trust me, it'll work.

Try enabling "flash". :| :| :|

Are there more tests added at the end of open hacking phase? vovuh

my solution for problem E1 is passing testcase1 on my System.But on codeforces it is giving wrong answer.

here is my solution link:

http://codeforces.com/contest/1015/submission/41059028

Print format should be %lld.

He didn't need

`long long`

in the first place. Nevertheless, format string for`long long`

is`%I64d`

as per Codeforces recommendation.Oh right, forgot about that. Does using

`%lld`

make trouble in CF btw?Not anymore, see comment below.

In fact, this is no matter, which format you will use when you print 64-bit integers. Codeforces accepts both

`I64d`

and`lld`

for at least two years.Ah, ok. Probably have seen it while solving problems from old contests.

Issue resolved.

can someone plz tell me why this is wrong in E2. https://ide.geeksforgeeks.org/avFzCSv3v6

Problem D:

In problem statement, it is written that we have to perform k moves to "other" house. Given that, preliminary test case 31 should have answer as "NO", while jury's answer is "YES ...". I am not sure what is the correct place for such doubts but it would be helpful if this is looked into.

Test case 31 is 10 50 450. You can repeatedly move between 1 and 10 (of which the distance is 9) 50 times and reach 450. Not sure what made you think that the answer should be NO.

At the end, The person is on house no 1; so he hasn't moved to "other" house in k moves, but came back to the same house

Nowhere in the description says that you must end up somewhere else than the initial house. You just need to move to somewhere else than where you

currentlyare. It even says it twice:`You can't stay where you are (i.e., in each move the new house differs from the current house).`

and`It is possible to visit the same house multiple times** (but you can't visit the same house in sequence).`

i.e. if you are at

`k`

th house at time`t`

, you must be at another house that is not`k`

, at time`t+1`

.Its written in 2nd line :

`You have to perform k moves to other house`

It implies that after k moves, the person has moved to a different house than the original one.

No, it implies that each

moveshould make you be at a different house than where youcurrentlyare, not where youinitiallywere.https://codeforces.com/contest/1015/submission/41062725

Why does this give WA in testcase 9?

You wrote in your code:

code`if(prefixb[i]>=m) ans=-1`

means that if sum of elements of array is equal to`m`

then the answer will be`-1`

, but the answer should be`n`

.But prefixb[] is the prefix sum of the compressed sizes. If the sum of these compressed lengths till i exceeds m, there's no way to store the songs. So shouldn't the answer be -1?

If the sum of the sizes of all compressed songs

equalsto m, it fits into the flash drive. It just needs to notexceedm.I read this as something along the lines of "Even if Ivan compresses all songs it can be impossible to copy all songs" :(

so out here, if prefixb[n-1] == m, the answer is n, and if it's greater than m, it's -1, right?

Accepted.

Thanks!

Plz help. Why in system my solution get WA on the 9th test, but on my PC it gives correct answer? http://codeforces.com/contest/1015/submission/41053093

Try to add this code:

~~~~~

~~~~~

Hmm, accepted. Too late.

Why my initialization does not work in system?

seems like there are some problems with the first row

Strange ... Thanks for help!

How to solve E2 efficiently?

Let call S1[i][j] be the furthest contiguous "1" that can be reach from block (i,j) upwards,S2[i][j] is the same but downwards, S3[i][j] is the same but leftmost,and S4[i][j] is the same but rightmost.

Its easy to see that with each (i,j) we need to greedily choose the longest star that we can create, and the longest one should be min(S1[i][j],S2[i][j],S3[i][j],S4[i][j]) — 1, note that if the min(..) — 1 = 0 then we can't create the star.

After that you're good to go, but in order to check the impossible case efficiently like in O(N*M) time, you need to break the problems down a little bit, say you have N Pairs of [L,R] segments, find which block that is not covered by any original N [L,R] Segments. Then if you solve this problems then you'll be able to check the case in O(N*M)

My code: 41053798

I did same thing, except there no need to check impossible case separately.

Basically you want to build another matrix, I call it b such that b = input.

Naive implementation of this is O(nm*min(n,m)), we simply brute force every position, then place maximum sizes star by trying every star size.

But we can make this O(nm), by placing stars in O(1).

How? We use prefix sums across columns, and then rows. And to find star size in O(1) we use dp idea describes above.

Something like pre[left]++; pre[right+1]--;

And then sweep across and do pre[i] += pre[i-1] will allow you to do O(1) range updates, and then a single sweep to update them all at once in O(n).

So for every row and column its O(nm). Look at my code for more details.

My solution is O(N^2LogN). I might have overcomplicated some parts of it, would love to know if there can be improvements.

Let the array a[][] be the input matrix, such that a[i][j] = 1 if there is a star on location, 0 otherwise.

For starters, it is easy to see that for each point (x, y), such that the point (x, y) has a star on it, we should make the longest star possible on that node. We need to accomplish this step efficiently.

We first create 2 arrays PrefixRight[][] and PrefixDown[][]. PrefixRight stores the row prefix sum over all (i, j) and PrefixDown stores the column prefix sum. We can do this with the following code —

Now, we have to find the maximum height of the star at some location (i, j). Interestingly, we can binary search over the height and check in O(1) time if it is possible using the prefix arrays we created above. Our condition evaluates to true if some contingencies are met, specifically that the number of stars between our point to a point that is vertically/horizontally at a distance h should be equal to h. These points are (x + h, y), (x — h, y), (x, y + h) and (x, y — h).

The following function check returns true if this condition is met.

After binary search-ing for the greatest height star we can make at a point, we have to find a way to store this result. We now create two arrays, DPRight[][] and DPDown[][]. We update our vertical results in DPDown and horizontal results in DPRight.

We also store this (x, y, h) result in a vector ans.

We can see that this is the prefix sum technique that allows updates in O(1) time. After doing this for all suitable points, we just need to take the row prefix sum for DPRight and column prefix sum for DPDown.

Now we just go over all points (x, y) and check if either DPRight[x][y] or DPDown[x][y] is true. If not, then our answer is no. Otherwise, our answer is yes, and we can just print the contents of our ans vector.

Code here: https://ideone.com/cPp2so

Would love to know a better solution.

There is a problem that some of the E2 solution get the O(n^3),but we can't hack them. Because that a 1000 * 1000 square can't be saved as a test because it is higher than 256 KB:(

Use a generator.

Oh Thanks.

To me, Both E1 and E2 were 'easier' than D :( Somehow I messed up D after solving A, B, C. Read problem E1 and E2 after the contest ended only to realize they were easier for me. Lesson learned: Always read all the problems.

When does system test start ?

In question E2 if it would have asked to find the minimum possible stars too and if many multiple answers exist print any. Then how can we solve it any idea anyone?

I got two AC with the same code to E1,E2. I am regret not to do these two problem first

Messed up completely : B : Was printing C_(i+1) instead of C_(i) C : Taking input as a_1, a_2,....,a_n instead a_i b_i D : frustration after messing B and C

what has happened to the judger? it seemed that the test has stopped.

the tester sucks

Currently, Codeforces Marathon Round 2 is judging mostly. It requires a lot of judges because of 1000 tests and 15 seconds TL. Sorry about it, but Codeforces Round #501 (Div. 3) is next!

Rip system tests :P

Did anyone else lose like 3 problems :/

I got 3 Ac . but there are a lot of system testing fails !

Hello,

It says "_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),_", but, next paragraph says "_Regardless of whether you are a trusted participant..._" — so, which one is actaul?The following guys have participated just one contest and get rated, is it legal: http://codeforces.com/contests/with/Ka55un0

http://codeforces.com/contests/with/shanghaiKingCsl

And why rating changes just for official differs from standings

Basically, it's just that

`Trusted participants != Rated participants`

.Then the first paragraph is nonsense, right? What will be with non-trusted participants?

Even if one is not a trusted participant of third division, they can still be rated. Non-trusted participants whose rating is less than 1600 will not be shown in the official standings table, but will be rated nevertheless.

What does give/not give him and others not being shown in this table if he anyway affects others rating change? Do real cheaters care about it? The only thing they care is to get high rating change and feel himself as the most claver guy and decrease others rating. "Rating chage" shows them

The point of the trusted participants is to exclude such multi accounts from the official standings table. Even though they still affect the ratings, yeah, but at least we are able to not see the top of the standings section full of multi accounts anymore.

My Rank in Standing 799 But My Rank in Change Rating 902 I Think Something Wrong

This is bcz of non-trusted participants :(. See above discussion for more info:)

I just want to know who is ZhouEnlai?

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

Apparently he has been competing on CF in his grave. I wonder who snuck a computer in there for him.

Compete for the rise of China

Hello, in problem F, why does this solution not work :

read n

read sring

get delta of string : delta"(("=2 ; delta")"=-1 like if you have "(" add 1 and if you have ")"

substract 1

get the minimum over all deltas :

than just fix where you want to fit it in

like [ poz, poz+sz-1 ]

I am giving you the code

link http://codeforces.com/contest/1015/submission/41118240 thanks in advance

Can someone tell me how to view GYM coming contests?

Conguratulations to halyavin of being the best hacker again!