Hi all!

This weekend, at Nov/18/2018 19:05 (Moscow time) we will hold Codeforces Round 522. It is based on problems of Technocup 2019 Elimination Round 3 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2019 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The round was prepared by Alexander Golovanov399 Golovanov, Evgeny WHITE2302 Belyh, Alexandra demon1999 Drozdova, Arsenii kraborak Kirillov, Ivan ifsmirnov Smirnov, Artem komendart Komendantian, Roman Roms Glazov, Daria Dashk0 Kolodzey and me.

Huge thanks to Grigoty vintage_Vlad_Makeev Reznikov, Ildar 300iq Gainullin, Ilia irkstepanov Stepanov, Andrey AndreySergunin Sergunin for testing.

Have fun!

The round is over, we apologize for the issues with platform accessibility. The round is declared unrated.

Congratulations to the winners!

Technocup 2019 - Elimination Round 3

Codeforces Round #522 (Div. 1, based on Technocup 2019 Elimination Round 3)

Codeforces Round #522 (Div. 2, based on Technocup 2019 Elimination Round 3)

Thank you all for joining!

The editorial is published.

Clashing with CodeChef Cookoff. :( Too bad none of them can be rescheduled.

Feeling sorry for codechef :P

I moved to codechef after codeforces crashed. Bad day for codeforces

Feeling glad I choose cook off this time :P

And now I wish I had given the cookoff instead. Bad luck :(

It doesn't seem open for everyone currently. Div.1 and Div.2 versions says "Registration is private" too.

(Fixed now)

Please update c language compiler, it doesn't work for some questions

Let's solve some problems tomorrow. :) Good luck to all of you, guys!

who cares

marsii inapoi pe pbinfo fraere!

Bagami-as pula in gura ta de handicapat ordinar.

pfu sa ma pis pe tine cu bucati de pula mars inapoi pe pbinfo jegule care esti ai dat si tu de internet si hop pe codeforces

Please reschedule clashing with cook-off!!

Not possible :(

How many hour it will take?

It is scheduled for 2 hours.

Does anyone know where can i search for a specified category and see different problems on that category starting from easy to hard ?https://a2oj.com/

You can see different categories where problems of each category ordered by difficulty and the website the problem belongs to.

You can also take a look on the ladder page for general problems also ordered by difficulty.

You can add tag to search section at "Problemset" and sort the problems by difficulty (the orange symbol).

Will there be any interactive problems?

OMFG IS IT RATED?

not sure if you're joking or you can't read english

whatefk dude why arent you replying to his question?

why are you bully me for I dont know if it rated or not??

zOMG WTF is it rated please i want to know so i know if i can know to participate or no! :( ty

THATS EXACTELY QWHAT I ASKEDFM THE HOST BUT HE NO RESPONDE!!!!

WHATEFK what WE DO????

Looks like you're the one who has brain damage.

african kid look at you fucking rating before comment! noob!

excuse me but that's racist :).

exuse ,me like who care

lol you have brain damage you are unironically taking part in contests on this website lol

noob

I just have one doubt, I am almost sure that, codeforces admins are fully aware of the fact, that

CodeChefis having contest on sunday at 9:30 pm from more than 2 years continuously,why in the world, CODEFORCES HAS CONTEST EXACTLY AT THE SAME TIME !!!!!! :P :P :P

is it rated man

You have brain damage man

shut up! you are probable unemployed and live in your mammy basement! noob!

you are at the end of the world indonesia who the fuck cares you are unironically taking part in contests here and commenting? you legitimately have brain damage

you are all losers like +trwinfrarmageddons

I hope I will be candidate master today and shahidul_brur will gain +100.

if you watch anime you should be restricted from accessing the internet same applies if you're reading / have read homestuck

lol i see i cant register it's only for russian dumbfucks (which is a pleonasm i'm sorry) haha apes lol

Who else couldn't access this site for the last 30 min? Is there any way I can report this?

It was like 10 minutes...

Maybe it was shorter, you're right, I mean it felt like 30 minutes to me :p

Yes, codeforces was unavailable. KAN, will the round be rated?

Yes

ok, is it still rated after the second server error (and you don't give any extra time for us)?

i can't even submit my C

should be unrated dude

But my rating.....

Hm, now when more serious problems came we have to declare the round unrated.

Why not considering rated for submissions before server issues? Everything seemed okay before 90 minutes of contest.

Due to the second crash (cca 10 mins after first one), I recomend stopping the competition in it — then rating will be moreless fair, as people had time to send their solutions during previous crash and there is almost no advantage for people who had the problems opened offline.

Yeah I was not able to access the site

Unrated Pls! I can't read the statements/submit/hack for an hour!

Ok! Now I can't read the statements/submit/hack for 80 mins!

Farewell! Expert nervend!What about people who left contest? More than 20 minutes of downtime in 120 min contest is enough to lose interest. should be unrated IMO.

IMO, they should change the ratings only to those who would get a raise.

Solved G but can't submit. When CF back it's over... Even this comment took time...

Btw, will 3

nlog^{2}3npass G (Chattering, Div1. D)? Update: TLE :( Updated to 3nlog3nat query stage and worked.In fact, It could be passed it you try to shorten the time[submission:45958962]

Yes, and can even shorten more by relation .

Found a typo in my code 1min before the end of contest, opening (already loaded) problem page in browser, click "Submit" tab and see "502 Bad Gateway". Perfect!

The same situation, i send mine 10 seconds before 2 hours are gone, and seen 502 Bad gateway, but then i realised that it reached the server and passed pretests...But now who cares, haha

The site was down even during the extended time. Not able to submit question D. Is it still going to be rated?

With constant

"502 Bad Gateway"this round was quite unpleasant for me.502 Bad Gateway...

the 30 minutes extension did nothing because the site was down during the whole 30 minutes anyway

Is it going to be extended again? The site was down at least for the last 5 minutes of the first extension period and it was impossible to submit during that time.

In my case, it was down for a while, then it came back for a few seconds with the message "The round is extended for 20 minutes.", after a few second later, it's gone again, and came back after the ending of contest.

Awesome, isn't it?

Oh, my fu**ing God ! This contest and up-time is absolute sh*t.

I spent 15 minutes trying to submit in the last of the second hour AND COULDN'T EVEN OPEN ANY PAGE during additional 20 minutes.

What was the point to add them if it's still COMPLETELY UNACCESSIBLE ???

It would be disrespectful for the community to make them pay with the rating for CF server issues. Feel free to comment if you agree it should be unrated

Calm down. It’s only virtual points. Nobody is disrespecting anybody.

tr00

Website was down even during the extended time, for the last 30 minutes or so. Please it should not be rated.

You're unrated anyway what's the big deal for you?

I was aiming to get a good rank that's why.

With constant "_502 Bad Gateway_" this round was quite unpleasant for me.

I have solved the problem C but I can't submit it in last 20 minutes

same problem man,

No for first and yes for second question :V

Bad connection round... I've solved problem D, but Codeforces was unavailible. :(

Guys, let’s not downvote the post. It’s not the problemsetters’ fault that the servers were down.

You just reminded me to downvote the post.

ɯoɔ˙sǝɔɹoɟǝpoɔ

That moment when you realize the two mangolian accounts had a point in asking if it's rated

Is it rated? Codeforces had 502 for a long time!

SUCH A SHAMEThe round should 70% be unrated from the first server issue. The second one, ironically fell right into the extended time, just further confirmed the validity of that decision.

I even can not submit in extra time. It's unfair if this contest is rated.

How about judging until certain time (e.g. before the site went down, or at least without the extended contest timeline?) Since the contest went pretty smooth in the first 90 minutes. We can disregard the next 30 minutes which was down most of the time anyway.

Rated or not, Please put problems to practice section fast T_T

Phucc dis shiet nigguh

I feel so bad for missing the special case in B where the input contains only two different values. Spent 60min on that while I could have easily done D in less :(

OH MY GOD THAT WAS IT?!?!?!?!?!?!?!?!?!

unrated...

Is this contest rated ?? :D ??

I have been delayed and do not know when codeforces website working again. So bad

Guys, sorry, it was unexpected dos-attack (

I believe on codeforces always.

Are they ever expected?

That's OK,but I realy don't want it rated.

Lol, what kind of an asshole doses Codeforces?

Ok, my suspicion is that tourist was afraid of losing first place in overall ranking to Radewoosh, so that was his last resort.

What did you say?

That tourist shot himself in a foot xD

more like

OK, MY SUSPICION IS THAT TOURIST WAS AFRAID OF LOSING FIRST PLACE IN OVERALL RANKING TO RADEWOOSH, SO THAT WAS HIS LAST RESORT.

It's like the dumbest way to waste electricity

Someone who wasn't able to solve nothingg but the first problem in 90 mins :D

EDIT: I should refresh the page before replying — it showed me "a moment ago", because I spent 5 mins reading the others.

What reason for attacking codeforces?? For fun, or is it another CP site)))0)0)?

Why not just deploy the site on some well-known third-party platform such as AWS or something similar? These platforms are run by big companies and, as such, have very good stability, handle traffic better, plus a lot of security features (including DOS mitigation).

What is the reason for not doing this? I honestly can't remember the last day in which codeforces wasn't broken for at least a few minutes. It doesn't have to be like that... I get there is a cost-component to using these services, but as far as I know it's not significant and it would really improve the user experience.

So basically, if you want to have high rating, you should just DOS attack the site unless you do well on the first hour and a half or so. That way you never lose rating!

You forgot about failing systests,

That's what the time machine is for.

Errichto, is that you?

(p.s. He'd have an incredible rank drop this time.:)

contest will be rated or not

My best performance during a round so far. Probably would've gotten at least a +300 rating increase. Too bad there were server problems. It probably sucked for others. Oh well. That's just our luck, we gotta move on.

Since you did so much better than your current rating, surely you will earn a good rating increase next contest :)

It doesn't work this way :)

I'm just trying to be positive okay :|

DELETED

Two previous rounds were also organised by 3 rounds at once (official, div.1 and div.2), but CF was stable.

But sum of number of participants is nearly same as in div1+2 round...

I think that it should be rated for people that are going to get some positive rating. They wasted their time participating and it will be unfair not to reward them somehow.

Serious, unrated for all :((

I mean I agree because I did great on this round, but doing great once wouldn't really change much. You can have 1 great round and not compete for a year and your rating would be "high", but it wouldn't really matter because it wouldn't represent your real skill.

Sadly, the main problem is that it's not the first time it happens.

Yeah, that sucks. I rarely have time to participate in actual contests so when there are server problems during that time it's like a slap to the face.

So round 485 had the same issues and was rated and this one won't be. What's the logic of choosing if rounds are rated or not?

MikeMirzayanov KAN

Please do rated, please!

talk about my luck the day i solved four problem site went down,and contest unrated

How unlucky am I? Returned to Codeforces after 13 months to solve a rated round and possibly became violet, quite succeeded — currently 119th before system testing (even when I had to wait for 15 mins to send prob. D), and it was all a waste of time :-(

EDIT: Murpy's law really holds — all Accepted, final rank 88th.

I feel so sad that I stay up late in China, only to find the contest unrated.

I have a college quiz tomorrow, I still found time to give contest only to find it unrated

Upgrade your damn servers. This is like the 100th time this shit happens. It's bloody irritating for people with negative rating if it remained rated, and EVEN MORE FUCKING IRRITATING for people with positive rating when it's unrated. I am seriously starting to hate CF, it's my favourite and I don't want to hate it, but this, this is absolute shit.

Yeah, for the longest time I thought CF rented servers dynamically from AWS or some other cloud provider. I heard that was what registration was for.

Then the ITMO move post came around and I realized it's still basically running on a bunch of PCs in a garage.

In that case, what's even the point of registration, if your compute power is constant...

(Although in this particular instance I believe it can be forgiven because it was apparently an attack.)

what do you mean by attack?

http://codeforces.com/blog/entry/63267?#comment-472165

make it rated ! at least for the guys with rating raise or something like this !

because they have do good and get rating in the contest is the prize for them !

agree with you please make it rated!!!!!!!!!!!!!!!

that's impossible, for someone rise other need to down.

Thx for servers, nice job

Am I the only person who think that task A was a little bit difficult for 500 points?

Yes.

The actual problem wasn't difficult, but the statement was definitely a bit too long and confusing.

C < A for me.

Why can't codeforces use services like "cloudflare DOS protection" ?

Else, they should have some system for rating in such contests. (and provide problems statements in a dropbox/drive)

Cloudflare costs money.

I think codeforces is sponsered by telegram.

There’s a free tier.

Again, That's what happens when you forget to thank MikeMirzayanov

I am glad that I switched to Codechef. And also my bro Mr. shahidul_brur was supposed to get -88. So, I am glad for him too that he is still blue.

is Div2E like this:

If number of distinct elements <= 2 then answer = n

Else, First compute dp[i][j] denoting number of ways to form a subset of sum i, using exactly j elements.

Now, put each element in map cnt. And for each key, iterate over the number of times to pick that element, and check if dp[key * times][times] == ncr(cnt[key], times) then take max of all such times for every key.

How do you compute the dp table? I got stuck at that part

dp[i][j][k], where i is the starting from item i, j is the weight left, and k is the items left to pick. dp[i][j][k] = dp[i + 1][j][k] + dp[i + 1][j — w][k — 1] the second term is only if you can pick item[i]

I did like this

That's my solution. But the dp should be dp[i][j][k], where i is the starting from item i, the other two are as you said. I couldn'y submit so I am still not sure if it is AC.

After you compute using dp[i][j][k], you just require dp[i][n][k].

dp[n][sum_weights][num_items]

my dp definition was:

dp[i][j][k] = number of ways to form a subset of sum i, using first j elements, and picking exactly k elements

Aha, mine is starting from item i, j is the weight left, and k is the items left to pick.

Just a confusion, sorry.

If the number of distinct elements is 2, then we need to make sure that their sums are different first.

It's not required since, in case of two distinct elements a1 and a2 with freq c1 and c2, just query with sum = a1*c1, total=c1, Now you identified c1 elements. The rest elements are c2. or you can do vice versa.

for n = 6 with the following a_i:

2 2 2 3 3

just query for total weight = 6, and number of elements = 3, then you know the remaining weights are 3,3.

Or, you can query for total weight = 6, and number of elements = 2, then you know the remaining weights are 2, 2.

so, we identified all elements using 1 query.

Oh sorry, my bad :'D

dp[i][j] could be the maximum and minimum value you used to form a subset of sum i, using exactly j elements. Now if max == min, it's a good one, and update your answer. I think is easier that way. And you avoid possible overflow issues. EDIT: AC code

I have thought in this problem like you, but can't the value of dp (and also value of ncr(cnt[key], times)) be very huge? it can be something like ncr(80, 40) which will overflow.

I thought of taking the DP and nCr values mod large prime number to minimize the probability of collision.

I thought of this too but I wasn't sure about the probability of collision as I haven't used this technique much.

Just got accepted using MOD 1e9+7

http://codeforces.com/contest/1079/submission/45941195

mohamedeltair, my observation was correct. Momentum's solution without MOD.

You can ensure 0 probability of collision by keeping values modulo multiple co-prime numbers. I used 2^64, 10^9+7 and 10^9+9 here and was able to squeeze within TL using O3 optimisation level. This is enough since their LCM > 2^100 > C(n,r). Thanks to CRT, there will be no collision.

Instead of using 2 primes in the order of 10

^{9}you can just use one large prime of the order 10^{18}since the modulo is performed for addition operation only (no multiplication).Right. That submission was during contest and I didn't remember there is no multiplication, so I just used 2 primes of 10^9 order. Using one prime will certainly speed it up. Thanks!

Some cells in dp table will surely overflow, but some will not, but our answer will be among the unoverflowed cells. If you observe carefully, you know that ncr value will always be less than or equal to the dp value. And for each key in map, we are iterating times in descending order, i.e from cnt[key] to 1, as soon as we met the condition, we break. The dp value where we break should not be that large imo because for large number of picked items, number of ways will also small. Not sure though.

Can you provide any case where it might go overflow?

If you are iterating on times in descending order I am not really sure that it will overflow, but I have no proof that it won't.

Just got accepted. it didn't overflow.

http://codeforces.com/contest/1079/submission/45942726

I solved it by counting too, but if the count of anything is more than 2, I set it to 2.

I tried this approach at first but my dp was working on the original elements (take the element at position i or leave it) so it didn't work. Your dp is working in a different way (take i elements from value v where i ranges from 0 to count of v), this considers i elements from value v one time only in contrast with the first dp which considers the i elements nCi times. Well done!

Best codeforces round ever, i totally didn't want to submit problems. What i really wanted was to waste 2.5 hours of my time. Should have chosen cookoff...

Why didn't you want to solve the problems? I think the tasks were nice (except div.2 A).

I solved 5, but i just didn't feel like submiting. I'd rather waste 2.5 hours and not be able to connect to codeforces for most of the contest.

Why don't you make contest rated only for those participants who hove positive rating change? I believe that's what CSAcademy did once(ore more) when it was some technical issues during the contest.

Rating inflation.

Anybody cares?

Yes.

Lol, why care too much about the rank? Codeforces rank can't help you get a job, to get money, to help your family and your future. Be realistic guys, spend less time on cf, go sleep early instead, get a healthy life and prepare for your future. They are more important than b***** cf color.

Actually, codeforces rank CAN help you get a job — it is quite common to append these things into CV if you are good enough.

Oh my Buddha, the only reasonable comment here and so much minuses

Look like kids on Codeforces are butt hurt. at least 55 idiot users just press downvote instead of reading. I said nothing wrong here! you can't just spend all day doing codeforces, then put your handle into your cv! you have to train many other skills to get the job, not only problem solving. I gave you a healthy advice, you ignore and press downvote! okay you shit head kiddo just stay with your cf dream

Bruh, first time seeing you so enraged throughout the times.

Still, I fully agreed with your points. It's not that Codeforces rating doesn't matter. The problem is that people cared

"too much about the rank", causing them to lose consciousness of the surroundings, the issues that makes the round unrated (c'mon, even Mike don't ever want such to happen, and that being said, could you ever expect a DDOS?), and the better designs behind the system.The next part is highly sarcastic and offensive. If you CF guys got triggered and pissed off by this, you have your rights to downvote me.Many Codeforces users are weird. Instead of improving the speed to comprehend and solve problems, they chose to increase their speeds on blindly judging people's opinions. Just increasing speed, the other aspects, no improvement, if not neglecting them.thank you bro. i just want to point out that cf rank doesn't matter much. When i see my opinion getting unreasonable downvotes, i feel uncomfortable, so some of my reply may be off topic. Again, don't bother too much about this cf rank. Whining about missing a rating change, or wasted efforts for unrated round seem really stupid, because as i said, this rank doesn't have much meaning for your life.

at least for high school student like me, training in CF give me more opportunity to compete in IOI (and help me to perform better to). which will help me to get a better university for better job

OK, maybe slightly more on topic, how do you solve A?

Div. 1 I hope? dp[i][j], where i is the current number, and j is the finger for that number. Check dp[i-1][0], dp[i-1][1] and etc. Also we need to have dp1[i][j], where we put the number of previous finger. It is important to make output.

It is the one with the manhattan streets and the diagonal street

I don't know. I have a solution, but I'm not sure is it right.

We will do binsearch to calculate, what is the most optimal point on the diagonal street to go from the point A. Then just binsearch what distance we will cover on diagonal street. Here is the answer. Don't forget to calculate a case, where we shouldn't use the diagonal street.

Find intersections line

ax+by+c= 0 with linesx=x1,x=x2,y=y1,y=y2. It's easy.If shortest way is on diagonal then you can split path in three pieces: A-diagonal, diagonal, diagonal-B. A-diagonal ends at either first or third point. diagonal-B starts with either second or forth point. So you can loop over two points and find minimum path.

P.S.Nevermind. I'm failed)P.P.S.Now I'm glad that round is unrated))P.P.P.S.evermind about my first 'Nevermind'. It was just stupid overflow. My solution is correct.It isn`t much of a surprise. Every time I do good in a contest, issues like these arise..

The best CP platform in the world should be stable and safe from attacks etc. Such a disappointment.

I don't know, many want it rated, many dont. But the the round must be fair. Many struggle with poor connection, solve problems and get their good rankings but they dont get anymore rating, it does not worth their effort. So I think people with positive rating should be awarded

Or at least count rating gains/losses at 0.5 times the original change.

If you reward just the people with positive ratings, you contribute to rating inflation.

Plus, ratings on codeforces are calculated comparatively. You might get more points than you deserve because you placed better than another contestant who WOULD have placed better than you IF there were no connection problems.

That is why "make is rated for people with positive ratings" will never work on codeforces (within the current system).

P.S: the problem wasn't "poor connection". There was no connection at all. The service was denied.

Lol, n=1 is really absent from pretests in D xD. Fortunately I got this one right, but this alone should be a sufficient reason to declare that an unrated round :P.

EDIT: Ah, I didn't manage to send my D in time anyway even though I got it right well before an end of extended round xD

If my solving is failed on a test with a huge data(10000 numbers), is there any possibility to see the whole input, not only cutted part of it?

No

Problem C. Playing Piano

This code got accepted , but this is a wrong code

http://codeforces.com/contest/1079/submission/45940667

Case n=1 not handled, like this case

input

1 50

expected output : any number from 1 to 5. my output : 50.

KAN can you check this ?

Does D2C have a greedy solution?

What do you mean by greedy? In one pass? Of course

Er no, that's not what greedy means. Greedy means choosing the locally optimal solution to subproblems every time. That probably won't work here since the subproblems are overlapping (locally optimal != globally optimal), and even if greedy did work the DP solution is much simpler.

It is a little bit complicated for me, but i guess the simpliest solution just follow the direction adding or substructing 1, and every time when direction is changing change previous number to 1(or if not possible to 2) in case of increasing and to 5(or to 4) if decreasing... and thats it...And of course you can not know what is the next number so you can not make choose optimal solution before it. (sorry if i didnt get, i dont have strong mathematical background)

Wow, I didn't think of that! You're right, that is a greedy solution.

Sorry,I don't understand what "(or if not possible to 2)" means,I just change previous number to 1 but got wronganswer.Just like 8 5 4 3 3 4 5 6 7

Next finger according to problem conditions can not repeat previous one...

so if you have key numbers 50 40 30 20 10 10 you can write fingering as 5 4 3 2 1 2 (you can not finish 1, 1), so now if key numbers starts increasing you can not convert last number to 1... The same is with decreasing and 5

It seems that Div2E has weak cases. I sent my solution assuming that the maximum sum is 5300 (It should be 100*100) and got AC. Code

Test on C task: 1 1 hack my code, but i got ac, add this test.

How to solve D?

My solution (slowest in time comparing to other solutions): triple the array to get rid of the rotation, build log-step trees tr[i] where each tree will answer the span [l, r] of cells x..y after 2^i seconds. After the trees are ready, calculate results from cell n+1 to n*2:

at cell n+1, do a binary search for the minimum time (min 1 max n) so that span length is not less than n; in each check, use the trees to expand the range in log(n).

for remain cells, as the different between adj cells cannot larger than 1, we can check for result in last-1,last,last+1.

In problem B why is this case incorrect (the difference of * is at most 1)

Test 87

Participants Answer

5 17

aoNtJAeHshvQrvwRg

ZHkrdxwyaaHOIsyEM

xtRNkM*ifYfRoRbam

pjmPoUVpN**JvSvEy

aQjEvGcRAJJS*PORp

Jury Answer

5 17

aoNtJAeHshvQrvwRg

ZHkrdxw*yaaHOIsyE

MxtRN*kMifYfRoRba

mpjmPoUVpN*JvSvEy

aQjEvGcRAJJSPO*Rp

the pairwise difference of any pairs not just consecutive rows must be at most 1

btw using 'i.e.' in the statement to give an example is confusing and wrong

thanks so much got it

You can't write two * side by side in a row. that's why you got wa

sure you can as long as the difference between rows is at most 1

Why are you downvoting this post? I can't understand codeforces community voting behaviour.

I read the problems, and they are good. I know that the round is unrated, but is not the fault of the setter.

This post was published after technical issues last year. MikeMirzayanov can repeat it

About Codeforces Round 445 and Technocup 2018 — Elimination Round 3

Huh, it was Technocup — Elimination round 3, too? This looks to be more than a coincidence — but why would someone want to ruin this Russian competition?

Hello, could anybody help to find how to download full input data of the test #23 of "C. Playing Piano" problem? It's 100000 elements, truncated in the rendered html.

You can't download full input data for testcases.

~~But I can tell you that your constructive algorithm approach is too complicated (and probably won't work always), try DP instead.~~No, it works, fixed a bug, got AC in submission #45944625 it's O(N), no DP necessary for this problem

My mistake, I guess this is why I didn't get the problem during the contest :|

If you want to find where is fault in your algorythm check is it that test by checking first 100 symbols of input, then when you find that in some position answer is -1, instead of output -1 output 10 numbers before...Hope you got idea

well... I don't see the reason why codeforces doesn't allow downloading tests after the context is over. It would be so much easier instead of following such hacky dumps. The bad story is that my algorithm depended on both forward and backward scans over all numbers, so in my case 10 additional numbers would not help much. Thank you anyway

yes, i dont see the reason too

it was fucking unrated why have you said it is rated are you mentally ill? you cant fucking read??? omfg wtf dumb cunts cant read

Y so triggered my friend :) chill..

Everytime vintage_Vlad_Makeev handle mentioned, I see color changed. Such a legend. This is consistent rating change here.

When will the editorial be published?

6 hours passed, no editorial. Maybe 504 bad gateway...

In the div2D . i forgot to think that either a=0 or b=0 ,but i got AC i think it shoudle be RE,because sometimes the denominator is 0

Where is editorial?

How are we supposed to find out whether or not we are invited to the final?

On techocup site, where you have registered for this olympiad

Thanks

Will there be an editorial for the round?

How to Solve Div2-D?

If !a or !b, the result must be the Manhattan's distance between A and B. Else, let res be Manhattan's distance between A and B, the result is min(res, dis(A, PA) + dis(PA, PB) + dis(PB, B)), with dis(A, B) is the distance between point A and B, PA = {points stay in the avenue that have the same x or y with point A}, the same goes to PB.

how to find the points in PA/PB i tried Binary Search on the equation. my implementation doesn't work...

if you want to use the line ,you should go to the line directly .Therefore, PA is the intersection of A along the direction of the parallel coordinate axis with a given line. So PB is.PA and PB both have two possibilities.

go to the line directly but how to find the points to go on to the line..

like if given point is A(x,y) and B(s,t) my choice is go to (x+p,y),(s,t+i)/(x,y+p')(s+i',y) how to find these points...

There is no need to use binary search, just replace the value x and y respectively of points A, B in the equation.

ax + by + c = 0.

So, you get points {x1, -(c + x1 * a ) / y } and so on.

Replace A's x or y to Avenue's equation and you get another y/x, that's how you get PA! Yay math is so easy!

EDIT: You can check my submission here if my explanation is still unclear: 45935987

Thanks a lot.. Silly me.. I wasn't thinking straight ..

So,where is the tutorial as the problem is too difficult for me ?

How to solve Div2 Problem C ??

Here is the most naive solution:

First, understand whether it is possible to create such a sequence b or not. Loop through a and if you find 6 or more consecutive increasing or decreasing monotonically numbers, output "-1". If you find 5 consecutive increasing or decreasing monotonically numbers and the one preceding all these 5 or the one that follows these 5 is equal to his neighbor from this subsequence, output "-1". Otherwise, there exists such a sequence b.

Going from i=0 to i=n-1, for each a[i] compute b[i] depending on how this a[i] compares with a[i-1] and a[i+1], trying to put the greatest possible numbers at the beginning of each decreasing subsequence of a, the smallest possible numbers at the beginning of each increasing subsequence of a, and the middle numbers, such that 2 or 3, in each constant subsequence (you should alternate 2, 3, and 4 in order to save 1 and 5 for the previous 2 cases).

Thanks for your efforts. But can someone explain DP solution for this problem?

Let dp[i][j] be true if you can reach position i of the array with final finger j and false otherwise. Also dp[1][j] is true for all fingers j. Then, you can see that if dp[i-1][f] is true for some valid finger f (f is a valid finger if the rules allow you to move from f to j in position i), then dp[i][j] is true. It is possible to play the entire array if some dp[n][j] is true for some j. Reconstructing the solution is quite trivial.

Thank you so much :)

Problem B was really nice

includingcatch with test 4.

Editorial ?

Problem Div1A/Div2D "Barcelonian distance" is very similar to the problem of the Spanish Informatics Olympiad 2018: "Barcelona distance"