PikMike's blog

By PikMike, history, 7 months 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

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

  • »
    »
    7 months 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.

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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

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

    could you please tell me the wrong things went there 51097407 ?

  • »
    »
    7 months 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

    • »
      »
      »
      7 months 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;
      }
      
      • »
        »
        »
        »
        7 months 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);

        • »
          »
          »
          »
          »
          7 months 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.

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

    I used the same logic but I implemented it using a map where where the map has n keys and the value of ith key corresponds to number of painters painting the ith fence but I got a TLE

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

  • »
    »
    7 months 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)

    • »
      »
      »
      7 months 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.

»
7 months 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

  • »
    »
    7 months 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

    • »
      »
      »
      7 months 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) ?

      • »
        »
        »
        »
        7 months 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

        • »
          »
          »
          »
          »
          7 months 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 :(

          • »
            »
            »
            »
            »
            »
            7 months 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

            • »
              »
              »
              »
              »
              »
              »
              7 months 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 :)

»
7 months 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)).

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

    thanks for awesome tip.

  • »
    »
    7 months 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. :)

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

  • »
    »
    7 months 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.

  • »
    »
    7 months 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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to understand tutorial for problem C. Can anyone help me out?What is the purpose of arrays p1[],p2[]and p3[]?

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

»
7 months 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.com/contest/1132/submission/50838090

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

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

  • »
    »
    7 months 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

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

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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!

      • »
        »
        »
        »
        7 months 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).

  • »
    »
    7 months 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.com/contest/1132/submission/50845077

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 months 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?

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

in problem f it given jn editorial Thefirstletterofthesubstringisdeletedalongsidewithsomeotherletter

but why we r deleting 2 charaters at differemt places.. we have to delete them in a given subarray . Roms

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

  • »
    »
    7 months 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].

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

could someone please explain the problem E in detail?? i'm unable to understand the editorial.

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

»
7 months 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"?

  • »
    »
    7 months 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.

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

»
7 months 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.com/contest/1132/submission/50862512

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain in D, how to check if current x is enough to keep all laptops charged for k minutes?

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

****what is the difference between problem F- Clear the string and problem d-Flood Fill div(2 round 538 ) can anyone plz explain ?

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

//Solution: DIV2 — C

Simple Bruteforce Solution:

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