awoo's blog

Educational Codeforces Round 61 Editorial
By awoo, history, 6 years ago, translation, In English

1132A - Regular Bracket Sequence

Tutorial
Solution (BledDest)

1132B - Discounts

Tutorial
Solution (Roms)

1132C - Painting the Fence

Tutorial
Solution (BledDest)

1132D - Stressful Training

Tutorial
Solution (PikMike)

1132E - Knapsack

Tutorial
Solution (BledDest)

1132F - Clear the String

Tutorial
Solution (Roms)

1132G - Greedy Subsequences

Tutorial
Solution (adedalic)
  • Vote: I like it
  • +62
  • Vote: I do not like it

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

My solution for C:

Make an array a of n vectors where ai contains all the painters who paint the ith panel. Find 'total', the total number of painted panels using all of the painters. Then, we make a 2D array 'count' that is initialized to 0. Here, 'count[i][j]' is 'the number of sections that have no one painting them if i and j are removed.

So, loop over all elements of a. If a[i].size()==2, then count[a[i][0]][a[i][1]]++ and count[a[i][1]][a[i][0]]++. If a[i].size()==1, then for all j ≠ a[i][0], perform count[a[i][0]][j]++ and count[j][a[i][0]]++.

Then, simply find the minimum value of count[i][j], and subtract that from total to get your answer. Solution works in O(n2).

This took me an embarrassing amount of time to figure out, and, in addition to my A getting hacked (due to a REALLY embarrassing careless mistake which wasn't caught in the pretests), my rating really took a hit this contest :'( Which is such a shame because I got F pretty early and I thought this contest was gonna be one of the good ones... from 3rd place to 900something, lmao. Someone play Viva la Vida.

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

    By the way, great contest! I wasn't able to get E, but i especially like it and shall try upsolving it later. The problems seem really interesting and generally should have been doable if I didn't choke so hard — oh well. My only comment is that F is WAY easier than E and D, and perhaps even C for a lot of us.

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

    I did the same thing but without the crucial if(section[j].size() < 3) so it got MLE hacked. Although why exactly it MLE on that specific hack is still unclear to me.

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

      Oh wow, I did have that < 3 check in my solution, yeah. I didn't think it'd end up being important! That's a weird MLE

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

    can you please share your submission on problem c. I am still struck on it. Thanks in advance

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      #include<iostream>
#include<vector>
#include<cstring>
#define N 5000
using namespace std;
vector<int> section[N+1];
int count[N+1][N+1]; //Get i and j
bool covered[N+1];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	memset(covered,false,sizeof covered);
	int n, q; cin >> n >> q;
	for(int i = 0; i < q; i++)
	{
		int u, v; cin >> u >> v;
		for(int j = u; j <= v; j++)
		{
			if(section[j].size() < 3)
				section[j].push_back(i);
			covered[j] = true;
		}
	}
	int total = 0;
	for(int i = 1; i <= n; i++)
		total += covered[i];
	memset(count,0,sizeof count);
	for(int i = 1; i <= n; i++)
	{
		if(section[i].size()==1)
		{
			for(int j = 0; j < q; j++)
				if(j!=section[i][0])
					count[section[i][0]][j]++, count[j][section[i][0]]++;
		}
		else if(section[i].size()==2)
		{
			count[section[i][0]][section[i][1]]++, count[section[i][1]][section[i][0]]++;
		}
	}
	
	int minnie = 1000000000;
	for(int i = 0; i < q; i++)
		for(int j = i+1; j < q; j++)
			minnie = min(minnie,count[i][j]);
	cout<<total-minnie<<endl;
	cout<<flush;
	return 0;
}
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please explain why did you ignore the painters when it's more than 2? if(section[j].size() < 3) section[j].push_back(i);

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

          We only care about the sections that could become unpainted if we removed 2 painters. If there are at least 3 people painting a section already, then no matter who you remove, that section is already 'locked in'.

          Sorry for not responding to your other comment. I generally don't like debugging other people's code for them. But I think taking the min(ans) at each iteration of the loop is a mistake — if you look at my code, i have a big 2D array, do all the computations, THEN find the minimum at the end.

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

Third question is little bit more tricky from last div2"s third question.

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

    I agree, that was much harder than C questions normally are. I think the next easiest question after B is actually F (which is a standard and straightforward DP)

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

      Depends on how good you are with DP, I solved C and D, and found both of them pretty straight forward to be honest, the only thing was that the time limit for D was a bit tricky, but it took me quite a while to upsolve F after the competition ended actually. While I'm not completely hopeless at DP I still have a bit to go before I'm completely comfortable with it though.

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

Can someone explain problem F with example, I am not able to understand the dp state

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

    1.let str[i][j] (i<=j) be the string formed by characters between ith and jth characters (inclusive). 2.define dp[i][j] to be the minimum number of steps to remove all the characters of str[i][j]. 3.This removal can be done in two ways. i.remove the jth character on its own, in this case dp[i][j]=1+dp[i][j-1] ii. dont remove the jth character on its own. rather remove it another character same as the jth. there may be many such characters . let nth character be same as jth and of course i<=n<j .So u must delete all the characters between nth and jth to bring jth and nth character side by side . And u have to do it in minimum step possible . there can be many such n's between i and j . u have to choose the one that makes ur steps minimum . so here dp relation is dp[i][j]= dp[n+1][j-1]+dp[i][n] . u have iterate through all the n's between i and j such that nth letter is same as jth letter and choose the minimum one

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

      But this approach isn't taking into consideration if deleting jth elements say all three together. i.e. adaba, suppose (1-base indexed) j be 5, then we will only be checking if aa(1, 5) or aa(3, 5) or a(5) can be deleted together, why shouldn't we check deleting together aaa(1,3,5) ?

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

        if u want to delete aaa then first u have to get aa . then we will get aaa

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

          that's my point, if we already got aa and you are deleting it in one operation, next time you have to delete remaining 'a' in another operation- thus increasing the deletions to 2, instead of 1.

          For example, I was going with this greedy approach first compress the string, i.e. compressed array will have all the adjacent elements different, (e.g. aaabbabb changes to abab). Then I was solving it considering the element with highest freq. to be deleted as the last all together. Its failing on 5th test case. But this approach of mine only covers the fact that, all occurrences of highest freq. element must be deleted all together at last — that's why this dp based question is still bugging me :(

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

            However ur greedy technique is wrong . Try this one 7 acbabca correct answer : 4 but ur greedy technique outputs 5

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

              Thanks for such a short test case, will look into the dp based approach carefully then :)

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

My solution for E:

Notice that if the total sum is bigger or equal than W, the answer must be between W-8 and W. So I approached the total sum to between W and W+8 by greedly removing the itens and then I checked if I could remove the difference between the actual sum and the answer, this could be done using smaller knapsacks as the difference would be no more than 16 (W+8-(W-8)).

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

    thanks for awesome tip.

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

    The cool part is that this solution can solve the same problem with a larger limit and the knapsacks can also be optimized by using bitmasks. :)

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

Could someone please explain me why did my code get accepted? (I have no idea O.o, i thought that a pseudo brute force should work but i'm not sure why or maybe there are weak test cases, idk)

My code

Thanks in advanced.

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

    Please take a look at this code. It is as yours but I just reduce the number of iterations performed by you in outermost for loop(100 -> 2) and it still gets accepted.

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

    Interesting, but yes you were just lucky. Your code fails on

    • 5406
    • 0 0 0 0 44500000 0 31700000 449000000

    Basically take any test case that doesn't work with attempting greedily adding as much as you can from all permutations, and then just make sure that you more than max(j) (which is 100 in your case) extra of each type needed and it'll break. Like this you would need a j of about 10^16 for your code to pass

    Edit: This is test case 21 from system tests with zeros added to each of the counts, your code outputs 5405 when it should output 5406

    Edit2: Even simpler. Actually it's so easy to break. Take this case:

    • 18
    • 0 0 0 0 100000 0 0 100000

    The answer is simply take 2 5s and an 8, but your code outputs 16 as it always tries either 3 5s first or 2 8s which won't work

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

I am not able to understand the solution of E .can some one elaborate it,please?How the equation could be written like this ? Thank you in advance.

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

I solved C in something like O(nlog(q) + q^2).

Keep two prefix sums of how many segments are covered by exactly 1 and exactly 2 painters respectively. You build these in O(nlog(q)) with a sweep line over the n segments keeping track of how many painters are in each. Also keep just a single integer keeping track of how many total segments are covered by at least one painter.

Now iterate over each pair of painters and for each pair take the number of segments covered by any painter and subtract from this number the number of segments which only 1 painter (this painter) covers. Then if they intersect subtract the number of segments with exactly two painters covering it (exactly these two painters). This can all be done in O(1) because of the prefix sums built before. In my code I also added back in the number covered by exactly 1 in the intersection but as I'm writing this I see that it's of course always zero as two painters are intersecting, so it's redundant.

code: https://codeforces.me/contest/1132/submission/50838090

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

there is a typo in the tutorial of F:clear the string. It should be s_i = s_l.

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

In C,my thought process was in the following direction. Sort all the pairs according to their interval length and then iterate over each interval along with maintaining a boolean array to mark which sections are painted.Can we reach the solution using this approach,if yes how?

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

    I don't think so. As it's not only the length it's also the position. Imagine this list of segments

    • 0 5
    • 0 4
    • 0 3
    • 0 2
    • 0 1
    • 6 6
    • 7 7

    Obviously the answer would be taking the 0-5 interval, the 6-6 and 7-7 interval and then all rest are redundant but your algorithm would take the 0-5 interval and then the 4 redundant ones

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

Can C be solved using segment trees? If yes, then can someone please share an efficient solution?

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

    It can but u dont need to cause there are no updation such as changing the range of a painter. So we will solve it using only cumulative sum array or prefix array.

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

      Yeah a prefix array would be enough here. I just wanted to know if it was possible to write a segment tree solution. Thanks for the reply!

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

        Indeed it is possible . U can determine range sum in O(logn) complexity using segment tree . However using prefix array complexity would be O(1).

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

    check my solution, i used segment trees to count number of '1' and '2'

    https://codeforces.me/contest/1132/submission/50845077

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

My solution For G:

dsu on tree

https://codeforces.me/contest/1132/submission/50995547

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

    Hey, I saw a few others with dsu solutions. Can you elaborate on your idea?

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

Why is G not Increasing subsequence problem? can someone elaborate the what does the meaning of the problem G in simple way.

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

    For a = [1, 2, 100, 3, 4], you could not choose a index subsequence like [1, 2, 4, 5] because 4 is not the minimum number such that a[4] > a[2].

    The only choice is [1, 2, 3].

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

G: Managed to squeeze HLD O(n * log^2(n)) with Fenwick tree and binary search 51106103
Solution shortly : go from right to left and keep multiset of possible ending of sequence, add and delete nodes as you go. While deleting node, erase it from multiset, and add it's children to multiset. While adding node, find highest parent which you can improve with HLD & binary search. After finding this node just do += 1 from added node to it.

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

In the editorial for G, what makes a vertex marked?

Is it "if it has a node that points to it in the current subsegment"?

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

    we mark the first k vertex and the maximum is answer[1].

    then we unmark vertex 1 and mark vertex k+1, and the maximum is answer[2].

    and so on.

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

Can anyone help me. I find the test when a parsed program for problem G gives an incorrect result.

6 6 3 29 5 5 28 6

True answer : 3( a[0], a[2], a[5] )

Answer in program: 2

Or i have mistake?

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

Can someone provide a test case where this solution of E fail or provide a proof of its correctness? https://codeforces.me/contest/1132/submission/50862512

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

Can someone explain problem B ? I am not able to follow the tutorial.

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

//Solution: DIV2 — C

Simple Bruteforce Solution:

https://codeforces.me/contest/1132/submission/54590211

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

In problem F, the recurrence according to the editorial is
f(l, r) = min f(l+1, i-1) + f(i, r)

But since we are combining s[l] with s[i], can we not have a recurrence like:
f(l, r) = min f(l+1, i-1) + 1 + f(i+1, r)

the +1 coming from combining s[l] and s[i] and we start the 2nd recursive call from i+1 instead of i. How are the two different?

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

    It is not written that we are exactly combining s[l] with s[i], instead it is written that s[l] and s[i](maybe along with some s[k]'s such that s[k]=s[l]) will be deleted in a single turn.

    Your reccurence is for s[i] and s[l] only will be deleted in a single turn, which is wrong(since it may not be optimal).

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

      canyou elaborate more i didnt understand why we arenot using i+1 in second?

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

Alternative solution for problem D

Binary search the answer. Suppose that you are checking the charger with power $$$x$$$. At the beginning, consider each laptop separately and charge it as late as possible, and keep an array $$$c$$$ with the number of laptops that should be charged each minute. There are two cases:

  • $$$x \geq b[i]$$$: in this case, it would be optimal to charge the laptop iff its current power is $$$< b[i]$$$. This is easy to simulate in $$$O(\text{number of charges})$$$.
  • $$$x < b[i]$$$: in this case, it would be optimal to charge the laptop only in a suffix of minutes (because the power of the laptop is always decreasing).

Of course, if the total number of charges becomes $$$\geq k$$$, we can just return false.

The problem with this approach is that we are not considering that we can't charge more than one laptop in a minute. However, we can consider the total number of laptops that should be charged until each minute by taking the prefix sums of the array $$$c$$$. The condition is easy: the charger with power $$$x$$$ can be used iff $$$c[i] \leq i + 1$$$ for each $$$i$$$.

Submission: 90456305

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

For C, https://www.youtube.com/watch?v=4GNUt5unEnM

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

Can someone please help me figure out why O(N^3) solution for Problem-F is getting accepted ?

Since N is 500 , N^3 should give TLE .

→ Reply
»
17 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Who would have thought this will be the first question in Cisco's Online Assessment

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

in the tutorial of F in the last line in formula,Si=Sl not Sr

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

Added some hints and thought process for F. Clear the String on CF Step.

Essentially the same as the editorial, but also talks about different ways for DP transitions that might not really work, but are the first ones to come to mind during a contest.

→ Reply