Suddenly, this round will consist of 7 different problems also!

**UPD2**: The round will consist of 7 problems and one of them will be in easy and hard editions!

<almost-copy-pasted-part>

Hello! Codeforces Round #555 (Div. 3) will start at Apr/26/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) 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 (or 8) 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.

</almost-copy-pasted-part>

**UPD0**: I also would like to thank my friend Adilbek adedalic Dalabaev for helping me with understanding problems difficulty and other help with round preparation!

**UPD1**: Big thanks to dreamoon_love_AA, Ashishgup, jeel_vaishnav and lizi_lzy for testing the round!

**UPD3**: Editorial is published!

**UPD4**:

Congratulations to the winners:

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

1 | FloodBenz | 8 | 282 |

2 | maguihong123 | 7 | 347 |

3 | dreagonm | 7 | 373 |

4 | DeathYmz | 7 | 571 |

5 | BaiBatyr | 6 | 189 |

Congratulations to the best hackers:

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

1 | WileE.Coyote | 448:-33 |

2 | Disappointment | 127:-20 |

3 | wzw19991105 | 39 |

4 | ismagilov.code | 50:-23 |

5 | Kucha | 20:-3 |

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

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

A | ImAlsoChildish | 0:01 |

B | BaiBatyr | 0:06 |

C1 | darshit_99 | 0:10 |

C2 | Injetzk | 0:16 |

D | iamnotacoder | 0:21 |

E | BaiBatyr | 0:12 |

F | Injetzk | 0:29 |

G | Injetzk | 1:15 |

Vovuh get ready to surpass Petr in the contribution table

Yes only 1

Recovery Time of Rating. :)

Nice round ID! I love it :)

Suddenly, this round will consist of 7 different problems also!Can explain how it is possible:

"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."?

I hack myself? or i submit from other accaunt and hack this submission? in this case, how to identify this?

Probably both. It is really easy to detect — cheaters will often have something like if(n==123445): print([obviously wrong number])

Only if this was my last div 3 :(

why does Vovuh mostly sets problem for Div3 and Educational Rounds only ??? P.S: I like his problems ;)

because Vovuh loves us!

Not only Educational Rounds ;) Codeforces Round #374 (Div. 2) By the way, thanks to Vovuh

When round start me "body oh my losing all my rating"

In reference to the UPD1, what does it mean to "test a round" ?

that means the testers will solve the problems of the round, and give feedback to authors if they found a bug or statement is unclear or something

What does it mean that "the penalty for the wrong submission in this round [...] is 10 minutes"? Does this mean that if I submit a program that doesn't pass test #47 then I will only have 1h 50min for the whole competition?

It means that the 'Penalty' displayed in 'Standing' page is increased by 10.

Thank you!

How to solve D ?

Hint : With $$$x$$$ as your first number, you can construct array for all $$$n$$$ in range $$$(kx + k*(k - 1)/2, x(2^k - 1))$$$

Can first number be any integer? I took it as 1 and thought I can solve the problem with range updates easily by tracking max value of every index and what to add to reach N, but failed at TC 5. For first sample it is going like: [1,2,3,4,5,6] -> [1,2,4,5,6,7] -> [1,2,4,5,6,8]. Edit: Just saw TC 5, we can use any number as first number :)

Interesting. It's actually not stated that $$$a_1$$$ has to be $$$1$$$. If this is the case, the solution could be much simpler.

Looks like I made problem harder during contest. Spent 1 hour to fix my solution and noticed it's extra easy when you can start with any integer. (This one wrong attempt, and this one after I understood the problem)

can you please explain your approach

Take the example for N = 60 and K = 6, initial array is [1,2,3,4,5,6], and sum is 21. You need 39 to reach 60. int(39/6) = 6. Add this to each element [7,8,9,10,11,12]. 39 % 6 is 3 remaining value. Check if you can add that to last item (max value is 2*a[previous id]), in this example it can be 22, so it safe to make last item 15. If array was something like [1,2,3,4], and remaining was 3, you need to do same thing for last 2 item [1,2,4,6]. A quick explanation, hope it's clear :)

What is 5th test case of E !? Can't find any mistake in my solution >_>

In your code :- " auto bs =pam.lower_bound(n-a[i]); " It may point to pam.end();

Thanks for the catch. I got it AC now T_T

Very Very Very nice round! interesting problems!!!!!!!!!! easy to understand! hard to solve!( for me ..)

Can someone elaborate the part, where 12 hour phase of open hacks is written?

plz don't ask about the solution since the hack is still avaliable.

Hacks in phase of hacks do not change anything

Thanks! I am new on this platform, so didn't know about that!1

Can anyone please confirm if my following submission has a time complexity of O(n*n) or not for E? According to me , it does. Link. Moreover, I would appreciate if someone can hack it as I am not really aware of the working of the test generator to generate such tests. Thanks !!

Yes, it is o(n*n).try a=200000*0 b=200000*199999 , will get a tle

Hi. Thanks for replying. It got hacked but just to inform you, I think my solution will pass the test case provided by you as all the elements of input array a are same. So basically, it will only search once and in all the next iterations it'll just execute the O(1) operation. The test case over which it'll fail will be something of the type

20000 0 1 2 3 4 ............ 19997 19998 19999 0 0 0 0 0 0 ..........0 0 0

In this case, it will calculate the ideal mod for every entry in array a by going through every available value in b before choosing the optimal one.

..

Hey ! For problem C1 (https://codeforces.com/contest/1157/problem/C1) , I want to know what should be the output for these test case:

case 15 1 2 3 4 5case 25 5 4 3 2 1case 31 2Thanks in advance

case 1 and 2 are invalid input for C1 since there won't be duplicates

sorry i wanted to write 1 2 3 4 5 and 5 4 3 2 1

LLLLL and RRRRR

Okay Thank you.

Those are invalid test cases for C1.

Case 3 -> 2 LR

that's right? in case 1 and 2 are invalid for C1

If you get stuck on C1, consider cases like

`3 5 7 6 2 4 1`

.Thanks a lot.This case has just revealed a logical error in my code.

what is the expected answer for this test case

`3 5 7 6 2 4 1`

??

Case 1: Answer is 5. ( LLLLR ) or ( LLLLL )

Case 2: Answer is 5. ( RRRRL ) or ( RRRRR )

Case 3: Answer is 1. ( L ) or ( R )

The cases are valid for C1, because the first number is N, so there are no duplicates.

Okay..Thank you.

Any counter case where my solution fails for C2?

apparently codeforces is giving WA on TC 15, but string is of length>1000 so I can't dry run and see where it went wrong.

My submission

input 5 5 6 7 6 6 causes infinite loop, you don't handle well situation when A[left] = A[right]

I want to know why my solution for C1 in java got TLE while the same solution in C++ got Accepted. Java version: 53356781 C++ version: 53359020

I'd also like to know why I got compile error when I used linked list of java to solve C1. It works fine on my computer. The version of my jdk is 1.8 by the way. 53350776

Because in java String concatenation creates a new copy of the string so that the overall complexity is O(n^2). You should use

`StringBuffer`

and use`append()`

method for the concatenation. It will work in O(K). K is the number of characters.thanks

Greedy Festival XD

is multiset erase() faster than vector erase() ? My solution got accepted when I used multiset instead of vector in problem E.

yep, vector erase() in O(n) and multiset erase in O(logn)!

Oh..thank you

erase in std::vector have the complexity linear to the size of the vector (it have to move the elements after the deleted element forward), while that in multiset is have the complexity log of the size of the vector.

Yes, multiset is implemented as a self-balancing binary tree, for which deletion is O(log n).

Vector deletion is O(n) in the worst case.

Can someone please help me figure out why my solution is giving TLE on test 16 although similar solutions have passed all tests.

check this link

Sorry, "Div3 round"… There won’t be a next time.

For Problem A I used a set to add values which are not present earlier . After generating next number if it is not in set add it until you find repeating number in set . Return set.size()

Is the approach decent ?Started using STL more often now a days .

yes, I did the same but with using unordered map STL .

Here is my solution.

I wrote 2SAT for G, but I got TLE. It works O(const * N^3). For my opinion it must pass in 2 seconds :/.

UPD. Number of edges are N^2, so that all program works O(N^4) :(Need Help in Problem C1: why im gettting TLE in Testcase 10 whereas other similar soln's are working?? 53371370

Hint:

4

4 1 2 3

See what your code does

Yet another interesting case of cheating by 4ul_sharma and utkarshv3 who are from the same institute: Check here. MikeMirzayanov and Vovuh please look into it.

Problems in this round are interesting and pretty good, thanks to Vovuh for setting these problems.

How to solve F?

This might be useful.

Take it for an example:

7

4 3 5 1 2 2 1

Instead of putting people of different heights randomly with keeping the difference between two adjacent heights one (e.g. 2 1 1 2 3), you can try to find a maximum height and a minimum height and form a cycle with other heights in between them. To do it, you have to find the longest possible contiguous non-decreasing sequence of numbers with difference between adjacent numbers 0 or 1 in the sorted array of heights. Notice that we need at least 2 elements of same value except for the maxima and minima in our output sequence, else we cant form the desired cycle.

For our example we go like this, if we take 1 as our minima and we can go upto 3 as our maxima. As we have only one 3 we can't accommodate 4 here. So we can form a sequence like this, 1 2 3 2 1. So we start from our minima, climb up to the maxima and again climb down to the minima. I hope you got the insight.

In Problem B , What's wrong in this ? https://codeforces.com/contest/1157/submission/53365568 Gives WA on TC 7

Try this case:

6

234567

1 1 4 4 6 7 8 1 1

Your code stops at the 3rd element (4), while it is more optimal to continue.

Guys, given a multiset m; does someone know the explanation behind lower_bound(m.begin(), m.end(), x) timing out in E(>2000ms): here, whereas m.lower_bound(x) gives AC with 233ms: here. I feel so frustrated and confused right now.

https://codeforces.com/blog/entry/20553 BTW someone just asked same question in this post

It was useful, thanks!

I really like problem G. With 1 clever observation, you can solve the problem in $$$O(nm)$$$.

There is a solution to the problem if and only if there is a solution with first row all zeros or a solution with last row all ones.Proof: $$$n = 1$$$ is trivial. For $$$n \geq 2$$$, for a valid solution, as the array is sorted, the 0-1 boundary must lie on one row, and all the other rows should either contains all zero (rows before boundary row) or all ones (rows after boundary row).

Therefore, we can try check only 2 column configurations (1. flip all ones in first row, 2. flip all zeros in last row) to find the answer. The row configuration can be found by checking whether the row have a mix of zero and ones after flipping the columns.

Thanks for the great round! :D

Thanks for your great idea!:)

Very nice! thank you

I had a different idea resulting in $$$O(nm)$$$ time complexity. But mine was very laborous to code. Submission: 53355339

Assume that the array is fixed. How do we check if it can be turned to only zeroes?

Make an data structure that can maintain the state of this algorithm when we change bits in the original array, and make two instances of it, one with the first row flipped and one without. Then do the following:

Why is this $$$O(nm)$$$?

When you toggle a bit that is not on the first row or on the first column, the structures do not need to be updated, so the change can be done in $$$O(1)$$$. There are $$$(n-1)(m-1)$$$ such bits.

When you toggle a bit that is on the first column but not on the first row, you have to toggle one row, which can be done in $$$O(m)$$$. There are $$$n$$$ such bits.

When you toggle a bit that is on the first row but not on the first column, you have to toggle one column, which can be done in $$$O(n)$$$. There are $$$m$$$ such bits.

When you toggle the bit both on the first row and column, you have to run the algorithm again in time $$$O(nm)$$$, but there is only one such bit.

So in total, we do $$$O(1) \cdot (n-1)(m-1) + O(m) \cdot n + O(n) \cdot m + O(nm) \cdot 1 = O(nm)$$$ work.

How to solve D with binary search?

I will try to explain the idea of how i did.

Suppose an integer x can be used as a1.

Let the restritions:

The min possible sum of array a, respecting the restriction 02, is reached when we increase each element subsequent by one.

The max possible sum of array a, respecting the restriction 02, is reached when we increase each element subsequent by multiplying by 2.

Therefore, to respect the restriction 01, the inequality down needs to be true:

$$$x+(x+1)+(x+2)+(x+3)+ ... +(x+k-1) ≤ n ≤ x+x*2+x*2^{2}+x*2^{3}+ ... +x*2^{k-1}$$$

The left side is a sum of arithmetic progression and the right side is a sum of geometric progression, so:

$$$\dfrac{(x+x+k-1)*k}{2} ≤ n ≤ x*(2^{k}-1)$$$

Thus, we can binary search the x:

After find a possible x to be a1, we can binary the others elements of array a at same way.

Complexity: O(k*log(N))

I did the same but for finding k, I applied the formula: x= (n-sum(1 to k))/k.

This will give you x in O(1) time. So I don't think it necassary to apply binary search.

"And for 1600-1899 the problems will be too easy" Not quite sure about this statement :o

I overslept and finally I didn't participate this contest!Oh no.

Can anybody show me what I did wrong in my submission (problem C2).Here is my submission : https://codeforces.com/contest/1157/submission/53384089

what is trashforces without getting WA on at least one problem for making a stupid mistake that the shitty pretest couldn't alarm you about..............

If S is a multiset. And what is the difference between S.lower_bound() and lower_bound(S.begin(),S.end())?

According to documentation: Complexity of

`std::multiset::lower_bound`

is:`Logarithmic in the size of the container.`

Complexity of std::lower_bound is:

`The number of comparisons performed is logarithmic in the distance between first and last (At most log_2(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.`

`std::multiset::iterator`

is a bidirectorial iterator, but it isn't random access, thus`std::multiset::lower_bound`

will work faster ($$$O(log(N))$$$ vs $$$O(N)$$$). In general, if you have to choose between container's method and an algorithm from std, the first option is more preferable. (There are some exceptional cases, but they are not related to competitie programming)It helps a lot，thanks ：D

How to solve problem G? I tried couple things, but nothing worked.

Hi everyone

My submission 53393992 for problem E is failing on the first test case itself. But, when I run it on my terminal, it is giving the same output as the expected one. (same code on ideone.)

Can anyone tell me what's going on?

Thanks

you never initialized the vector cnts

I thought it is initialized by default to zeros. Isn't it so?

Maybe you mean

editorials???

Can someone tell me what's wrong with testcase 6 for my submission 53339053. The input is no correct.... The third line is mssing....

you get n integers instead of 9 for the third line input in your solution.

Thanks a lot, that was the solution!

Can anyone tell me why my solution is giving wrong answer for Test case 10 on problem C1. Submission 53345673

6

5 6 3 4 2 1

Thanks, such a stupid mistake I made :|

For Problem D,I the lower bound of num[i] is

`max(a[i-1]+1,(int)ceil((double)n/sumb(k+1-i)));`

what's meaning? why not`a[i-1]+1`

?(I know it's worng,but why?) Thx!wileE.Coyote Hackcount 448 Wow! good job!

what should be the answer for this test case for problem C1 test case

5

4 2 3 1 5

according me it should be 3

2 3 1

am I right ??

you misunderstood the problem. take leftmost or rightmost elements and make a strictly increasing sequence with those.

5

4 2 3 1 5

the answer is 2

LR

take 4 (the leftmost elements) first and then 5 and make this sequence that is in increasing order{4,5}