vovuh's blog

Codeforces Round #555 (Div. 3) Editorial
By vovuh, history, 6 years ago, In English

1157A - Reachable Numbers

Idea: BledDest

Tutorial
Solution

1157B - Long Number

Idea: BledDest

Tutorial
Solution

1157C1 - Increasing Subsequence (easy version)

Idea: MikeMirzayanov

Tutorial
Solution

1157C2 - Increasing Subsequence (hard version)

Idea: MikeMirzayanov

Tutorial
Solution

1157D - N Problems During K Days

Idea: MikeMirzayanov

Tutorial
Solution

1157E - Minimum Array

Idea: vovuh

Tutorial
Solution

1157F - Maximum Balanced Circle

Idea: MikeMirzayanov

Tutorial
Solution

1157G - Inverse of Rows and Columns

Idea: vovuh

This is the comment about the quadratic solution. Thank you so much for mentioning this fact, STommydx!

Tutorial
Solution
  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (27)
| Write comment?
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The editorial for Problem G looks like a little the editorial of Problem F

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

    Thank you for mentioning, I just forgot to fix this place :)

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

it was a greedy contest :D Good round by the way

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

My solution problem D after contest(sad): 1)Find minimum first element with binary search 2) let's get maximum suffix, when we can add 1 for all numbers on segment, do it, while exist this is segment 3) end O(nLogn), and write easy

https://mirror.codeforces.com/contest/1157/submission/53393728

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

1157D — N Problems During K Days can be solved simply by putting $$$1,2,\dots,k$$$ initially and then trying to put $$$(n-(k*(k+1)/2))/k$$$ elements in each, and then from reverse order adding as many elements in each position as possible, without considering special cases separately.

You can go through my submission for clear understanding.

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

Anyone help me in finding the cause of TLE in Problem D in my solution.

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

    "erase" for vector works in linear time of size of the whole vector

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

This problem also has a solution like D:

https://www.codechef.com/SNCK1B19/problems/MAXPRODU

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

Does anyone have a solution for problem E which does not involve STL structures, specifically without using multiset,set,map or multimap ?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem D: "Then if nn != k — 1 or k = 1 then this answer is correct."

Any explanation for this ?

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

For problem 1157c1, what if the input is

7 7 4 5 6 3 2 1

The solution code out puts 5 RRRRL But if I discard 7 and take the subsequence [4 5 6 3 2 1],it's possible to get a strictly increasing subsequence of size 6, right?

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

When is the next div3?

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

What's wrong with my solution for problem B? https://mirror.codeforces.com/contest/1157/submission/53566680 I am getting wrong answer on test case 7

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved D in a different way. Mine

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm kind of late, but problem D can be easily (more or less) solved by binary searching the first element, and then binary searching every other element as well, from left to right, so that the minimum possible sum is <= n and the maximum possible sum is >= n. My submission

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

For the D problem, I just initialized array to 1,2,...,K then added (S — (K * (K + 1)) / 2) / N to every element in the array, and then just distributed (S — (K * (K + 1)) / 2) % N from the behind appropriately. Just wondering why there were so less submissions for this problem?

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

How to solve problem Minimum Array using segment trees??

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    I solved with segment tree, so I will try to explain my solution:

    First we need to sort B array, to be able to find some index j for each $$$A_i$$$ such that $$$A_i + B_l \lt n$$$ for all $$$l \lt j$$$, and $$$A_i + B_r \ge n$$$ for all $$$r \ge j$$$. We'll have only one index j for each $$$A_i$$$, because $$$max(A) + max(B) < 2n$$$.

    After that we can divide B array in two parts and find the best among these greedly, using segment tree here to get minimum, and then updating the used element to not be taken more than once.

    Submission

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me mathematical proof of E i just wanted to know why finding greater element is optimal than finding lesser value element if n-a[i] is not found

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    It is because for any $$$k\geq n-a[i]$$$ and any $$$0\leq b < n-a[i]$$$, you will have $$$(a[i]+k) \mod n \leq a[i] + (n-1) \mod n < a[i] \leq a[i]+b < n$$$.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E first I used a sorted vector to store the elements of array b and used lower_bound+erase operations to find the appropriate element for the current a[i]. But it gave TLE on test 16. But when I used multiset instead of vector it passed all the tests. Can anyone explain why vector solution gave TLE?

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

    This is because erase function in vector works in linear time(n), but in set or multiset, the data is already sorted so it works in constant time.o(1).

    → Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i think i have better solution for D. We can search maximum value of c that sum of array(c, c + 1, c + 2 .... c + k) <= n; then we can run through this array from the end and greedily add 1 while the problem condition is being met. since we have to add a maximum of k units, we will be able to do this.

→ Reply