vovuh's blog

By vovuh, history, 6 years ago, translation, In English

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 awoo Piklyaev, Maksim Neon 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 love.zy for testing the round!

UPD3: Editorial is published!

UPD4:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 dgkutd605 8 282
2 maguihong1238 7 347
3 dreagonm 7 373
4 DeathYmz 7 571
5 BaiBatyr 6 189

Congratulations to the best hackers:

Rank Competitor Hack Count
1 achaitanya.sai 448:-33
2 Disappointment 127:-20
3 wzw19991105 39
4 ismagilov.code 50:-23
5 Kucha 20:-3
919 successful hacks and 365 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A ImNotExpert 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

  • Vote: I like it
  • +176
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it

vovuh get ready to surpass Petr in the contribution table

»
6 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Recovery Time of Rating. :)

»
6 years ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

Nice round ID! I love it :)

»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Only if this was my last div 3 :(

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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))$$$

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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 :)

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -32 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hacks in phase of hacks do not change anything

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 !!

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

case 1 5 1 2 3 4 5

case 2 5 5 4 3 2 1

case 3 1 2

Thanks in advance

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    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.

»
6 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
6 years ago, # |
  Vote: I like it +45 Vote: I do not like it

 Greedy Festival XD

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Here is my solution.

»
6 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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) :(

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Need Help in Problem C1: why im gettting TLE in Testcase 10 whereas other similar soln's are working?? 53371370

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 years ago, # |
  Vote: I like it +85 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your great idea!:)

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very nice! thank you

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    1. Either toggle the first row or not
    2. Toggle every column with a one in the first row
    3. Toggle every row with a one in the first column

    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:

    1. check if either datastructure can be made all zeroes
    2. If either could, output its current row- and column flips.
    3. Otherwise, toggle the last bit that is not yet toggled in both. This essentially changes the solution we want to produce from all zeroes to zeroes in all but some suffix.
    4. If there was no bit to toggle, output NO
    5. Otherwise, update the two structures, and go back to step 1.

    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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D with binary search?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    Suppose an integer x can be used as a1.

    Let the restritions:

    1. sum of all ai for i from 1 to k should be n;
    2. the condition ai<ai+1≤2*ai should be satisfied for each i from 1 to k−1.

    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:

    • If $$$\dfrac{(x+x+k-1)*k}{2} ≤ n ≤ x*(2^{k}-1)$$$, this x can be used;
    • If $$$\dfrac{(x+x+k-1)*k}{2} > n $$$, we have to decrease x;
    • If $$$ x*(2^{k}-1) < n$$$, we have to increase 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))

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

»
6 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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)

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

achaitanya.sai Hackcount 448 Wow! good job!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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}