Hi all!

This weekend, at Oct/21/2018 11:10 (Moscow time) we will hold Codeforces Round 517. It is based on problems of Technocup 2019 Elimination Round 2 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 authors are Kostroma, Golovanov399, komendart, Denisson and Dashk0.

Have fun!

The round is over, congratulations to the winners!

Technocup 2019 - Elimination Round 2

Codeforces Round 517 (Div. 1, based on Technocup 2019 Elimination Round 2)

Codeforces Round 517 (Div. 2, based on Technocup 2019 Elimination Round 2)

The editorial is published.

CF rounds on weekends are the most fun.

I feel the same

Perfect time for Chinese users!

..

It's not a weekend in most Arabic countries XD

it's not weekend in Iran too .

How many problems? When do we know the score distribution?

PD: Just a joke: Where is thanks to Mike and Polygon and ITMO??

Elimination round(not CF) will be rated or no?

Rated

very less participation :(

All who qualifies for the elimination round are not here.

now the round is delayed because of you

Sad :(

Delayed by 5min!

Before the contest 00:01 remainingMe: Let's bring it on!

Before the contest 04:59 remainingMe: Oh f**k.

At least 5 min

Thanks, I afraid something went wrong with my connection

delay :(

Score distribution?

I love contests at 3 am :)

I am not able to submit code, getting error "you have submitted exactly the same code before". Please someone look into this matter. I have not done any submission in that problem.

Please, check PMs

div2D was dp or bfs?

Both of them :)

I spent so much time on this problem and didn't manage to do it in the end, is there a way to compute for each

`i, j`

the lexicographically smallest path from`i, j`

to`n, n`

?I did it with dynamic programming. For each field you just need to know if you want to go right or down. So create a table

`int dp[2001][2001]`

with 3 possible values: 0 — go down; 1 — do right; 2 — it doesn't matter (both going down and right will produce same string). We fill entries of dp from`n, n`

to`1, 1`

(backward). how to fill this array? For boundary entries (i = n and j = n) it is obvious, for others`dp[i][j] = fillDp(i + 1, j, i, j + 1);`

Edit: arr = original array with lettersComputing path is just going with pointers in dp.

I can't actually prove it works in O(nm) but I got accepted. Here is my solution — a little more verbose: 44647952

What was pretest 15 in div2 C? :(

Something like 147694707 63714381

The sum

m+nin this case should be 20562.It works for me, and I got pretest 15 wrong. What's special about this test case?

I stress-tested my WA on pretest 15 with the solution that passed that test case to get that. I'm sorry that I don't see anything special about this test case :(.

Got 6 WA in that. But, figured it out. It was because of not using long long int.

300iq Becomes Legendary Grandmaster!!

Хайпожор

Ага

He won't dye his hair pink for a week.

How do you solve div2B?

DP by O(16n) I'm not sure it's a correct algorithm.

I did it this way, and it seems to work

Could you elaborate, please?

DFS is enough.

Sorry! I find a hack data to hack DFS. It is:

answer is:

I have hacked lots of codes using DFS to solve problem B. If we add this data for judging, a lot of codes will be hacked.

The reason why it can hack DFS is when

a= 3 andb= 0,tcan be 0, 1, 2, 3.Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!

Because if

t_{i}has been determined,t_{i + 1}will have only one value to choose. Specially, ifa= 3,b= 0,tcan be 0, 1, 2, 3. But ift_{i}has been determined, we should not worry aboutt_{i + 1}.Brute force the value of

t_{n}. Givena_{i},b_{i}, andt_{i + 1}, it is easy to show that there can be at most onet_{i}that satisfies the given constraints.Yes, and

t_{i}equalsa_{i}+b_{i}-t_{i + 1}. Becausex&y +x|y=x+y.How did you get this relation?

By Binary Numbers.

x + y = x + y — x & y + x & y = x + (y — x & y) + x & y

Because any digit of x and that of (y — x & y) are different,

So x + (y — x & y) = x | y

So x + y = x | y + x & y

Wow, thanks!

Div2F / Div1D was bfs?

I finished fixing div2.D and the contest is over

Now, I hope my solution is not correct ...

Don't worry, it isn't.

Fine.

Not correct....

Lose to constructing.

How to solve div2-C , i tried bin Search but i knew it's not working good ,, any hint ?

Let

`k`

be the largest integer such that`1 + 2 + ... + k <= a + b`

. Then it's always possible to construct an answer with`n + m = k`

.thank you :D

Can you explain how?

Like before, we have

`S = 1 + 2 + ... + k <= a + b`

. Just iterate over`i = k...1`

and greedily subtract from`a`

whenever`i <= a`

. If`S < a`

, then we're done, otherwise it should be easy to see that we can always get a subset of elements that sum exactly to`a`

, in the end, so the sum of remaining items is`S - a <= b`

.Why is it so?

It's explained in the editorial, perhaps more nicely than I can do here.

Ok thanks!

in B all a[i] and b[i] gives only two numbers except when a[i]=3 and b[i]=0 then t[i]=1 and t[i+1]=2 or t[i]=0 and t[i+1]=3 right?

I couldnt submit my last solution because I did not understand my new stupid error while debugging which is we can't write cout<<1&3; that gives an error and Idk why

when you type cout << 1&3 compiler reads << as bit shifting

man if my solution was right and i couldnt submit it because of that ... meh

edit: it's wrong anyway:P

I slept just 3 hours to take this CF, let's see how my C fares the system tests :Dd. Already had to resubmit once during the contest

How to solve it?

I use bfs for

n≤ 12. Ifnis greater than 12, find the last 1 appearance and modify it to make sure that at most two steps would be used to set the last 6 positions 0.So did bfs on bitmask for n<=12 ?

Also when is answer "No" ?

When

n> = 8, answer is always YES. So you can just brute and check if it's no forn< 8.What was pretest 8 for div2D ?

How I solve Div2-C/Div2-A:

Write a greedy solution, get WA on test 15.

View submission detail and realize the checker's answer is not the same as the sample answer.

wow, very weak pretests again

Full Feedback contests are the best.

But remember that in most rated Codeforces round, you don't receive full feedback, especially when the pretests are weak :D.

I'm of the opinion that problems which are going to have very few solves anyway almost always ought to have virtually full feedback, i.e., the systests should not have anything special (new cases, etc) that the pretests don't have, especially considering that if you fail systest you get a score of 0.

It seems that div2C/div1A system tests are weak. After the contest I found a bug in my code that makes it fail : for the test

`7 1`

it gives the following output :which is obviously wrong. And still my solution got AC. (tmw when you think that the pretests are weak but after the systests it turns out the systests are weak too xd)

Solutions should be rejudged if that's the case.

What is the answer to this case for C? LHiC's AC code gives NO.

My AC code gives

Weak tests

`¯\_(ツ)_/¯`

Similarly, I resubmitted because my first submit uses too many operations in the case

(line breaks added for clarity)

But turns out my first submit would also have passed :/

Waiting for tutorial.

Waiting for my new rating... And of course waiting for tutorial....

The tests for div1 C seem to be so weak that some wrong codes passed.

44641451 The hack data is : 1 1 0 1 0 1 0 1 0 1 0 ...

Uhhhh that is the obvious "naive" solution that I didn't bother coding because

surelyit wouldn't pass right?.... but it does.And then I didn't find a good solution during the contest :/

After more thinking I realise this solution is quite solid with a small tweak. If try it twice and take the best solution, once normally and once ignoring the first 1 (and do the first 1 manually later) then it is perhaps not possible to make a counter case.

Anyway there are like dozens of solutions and I came up with zero of them during the contest.

can someone plz tell me whats wrong with my code for Div2D?? 44650538

As I see, the problems and the score distribution in the Technocup Round and in the Div 2 version were the same. However, the scores obtained in the Technocup Round were smaller compared to the Div 2 version. For example, score 2500 is in top 40 in the Technocup, whereas in the Div 2 version, someone with 2500 is on the 200th + position. So I guess that participation in the Technocup would have helped you increase your rating more than in the Div 2 version.

Maybe the tests for Div1C are not strong enough

these solutions were hacked by my data.

44638710

44641451

44641456

data:

Update: Oh, after posting this review, I found that cuizhuyefei has already mentioned it

Well, after contest, I have found a hack data to hack DFS solution in Div2.B.

We just use a form like:

answer is:

If you use DFS to solve this, you will get Runtime Error.

If possible, please add this data to hack someone who didn't solve the question well, including me :-) . Thanks.

Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!

I faced problem in B when ai =3 and bi=0 then ti and ti+1 can take 0,1,2,3 .can anyone help?

You can try to make first

t(t_{1}) be 0, 1, 2, 3. And the sequence will be constructed.We can think about this:

If

t_{1}has been determined,t_{2}will also be determined. Obviously, ift_{i}has been determined,t_{i + 1}will be determined, too. For example, ifa_{i}= 3 andb_{i}= 0,t_{i}can take 0, 1, 2, 3. But don't forget thatt_{i}has been determined.t_{i}will only has one value to choose, and it's easy to solve. Hope I can help you :-).the rating changes is unfair. in official round if you solve just 3 problem you will get high rating changes but in Div2 round if you solve 3 problem your rating change is not as high as rating chane in official round.

I noticed that the announcement and editorial are not linked to the problems, can some admin do this? Thanks

Does anyone know if there will be a parallel open round again for the upcoming Technocup Elimination Round 3 in a few days?