Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

pikmike's blog

By pikmike, history, 13 days ago, translation, In English,

1303A - Erasing Zeroes

Idea: Roms

Tutorial
Solution (Roms)

1303B - National Project

Idea: adedalic

Tutorial
Solution (adedalic)

1303C - Perfect Keyboard

Idea: Roms

Tutorial
Solution (Ne0n25)

1303D - Fill The Bag

Idea: Roms

Tutorial
Solution (Roms)

1303E - Erase Subsequences

Idea: adedalic

Tutorial
Solution (adedalic)

1303F - Number of Components

Idea: Ne0n25

Tutorial
Solution (Ne0n25)

1303G - Sum of Prefix Sums

Idea: Ne0n25

Tutorial
Solution (BledDest)
 
 
 
 
  • Vote: I like it
  • +78
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it -47 Vote: I do not like it

Why this post doesn't have any comments?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain a little bit about the proof of algorithm of problem F? Why considering all the delete queries in the last doesn't affect the final results?

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because the delete queries are after the add queries.

    when considering color $$$t$$$,all the add queries is the queries with

    $$$c_i=t$$$

    ,then for sure,they are consquent,and so for sure all the delete queries are after the add queries
    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But this is true for a particular color right? Like for a color c what ideally should have been done is to perform add query and then immediately after that perform it's delete queries but in code above they are doing all add first and then all delete query.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No...for a certain color c and all the queries with ci=c,the queries are consquent,so they changed some of the cells into color c.There isn't any delete query between them.After that,some queries may change the color of some cells which were color c,these are the delete queries.

        Like this example:

        2 2 4
        1 1 1
        1 2 1
        2 1 2
        1 1 2
        

        For color 1,the add queries are the 1st and the 2nd while the delete query is the 4th.

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

          Sorry but I think I didn't convey my doubt properly. I am talking about this part of code ..

          forn(i, clrs) recalc(add[i], +1);
          forn(i, clrs) recalc(del[i], -1);
          

          Here we are processing all the delete queries at the end (even after the add queries of same cell i.e. even after add query of (x, y) from c1 to c2).

»
12 days ago, # |
  Vote: I like it +11 Vote: I do not like it

In problem D

If in binary representation of n the i-th bit is equal to 1 and we have at most one box of size 2^i,

I think this should be at least?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain me about problem B why TotalG = ceil(needG / g) * (g + b) , i don't understand that clearly =)) ????

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    every (g + b) days have exactly (g) days good, we call it a block. So if we need (needG) days good, we must have ceil(needG / g) blocks, thus TotalG = ceil(needG / g) * (g + b).

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Firstly you should know needG is the Title requirements(make sure that at least half of the highway will have high-quality pavement),

    then y = ceil(needG / g) means the units of good days you can meet the requirements,

    next the days is again g good days, b bad days and so on, so y*(g+b) is the least days you need to meet the requirements,

    at the end, if some highway is still not repaired, answer should add it.

    Now are you clearly? My english is not good, so hope you can understand my words.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok thank you i understood it obviously =))

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the time complexity for G? nlgnlgn?

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Yes. You process each node O(lg n) times using centroid decomposition and each time you do it, you add 2 lines and you make 2 queries for the best path in O(lg n). Total is O(n lg^2 n).

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

1330-D HELP

Why in this test case answer is 4 ?

182 6

1 1 1 2 2 256

We can divide the box of 256 into two boxes of size 128(less than 182) in One division. Then why the answer is 4 divisions ?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Binary 182 = 10110110
    So u need 2^7 + 2^5 + 2^4 + 2^2 + 2^1
    Which is 128 + 32 + 16 + 4 + 2

    So given = 1 1 1 2 2 256
    Division 1 = 1 1 1 2 2 (128 128)
    Division 2 = 1 1 1 2 2 (64 64) 128
    Division 3 = 1 1 1 2 2 (32 32) 64 128
    Division 4 = 1 1 1 2 2 (16 16) 32 64 128
    Now you can regroup as 1 (1 1) (2 2) (16) (32) (128) 16 64
    All these terms in brackets give you the above values that will fill the box

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

I have a doubt, in B, does it mean at least half of the highway (consecutive units) must be done on good days or does it mean it can be done any way but at least half of it must be done on good days?

Example,

Should it be: g skip skip skip g skip skip skip g b b b

or

should it be: g b skip skip g b skip skip g b skip skip

or, even better

should it be: g b b b g skip skip skip g

If it's latter, then the minimum number of days will be different.

I got this doubt after looking sample test case when n = 1000000, g = 1, b = 1000000. If done with first approach, the answer will be same as the output given (499999500000), but if done with second approach, then the answer will less than the output given (I think).

ceil(n / 2) = 1000000 / 2 = 500000
Good days appear on: 1st, 1000001st, 2000001st,... days
It's basically an AP where a0 = 1, d = g + b - 1 and an = a0 + (n - 1) * d.
So 500000th good day appears on a500000 = 1 + (500000 - 1) * (1 + 1000000 - 1) = 499999000001
Then if we add remaining bad days (500000), then the answer is 499999500001.
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

if(g>n)cout<<n<<endl; long long int nnn=(n+1)/2; cout<<nnn*(g+b)-b<<endl; in the above segment of code which test cases fails ??????? Can anyone give me any example????

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting Wrong Answer in C. Here is the link.

My approach is first check for cycle: if parent[x] exists and adj(y, x) and parent[y] != x, then error. Here parent means immediate parent.

Example,

input: abcda

then, a->b->c->d->a, here parent['a'] = 'a', parent['d'] = 'c' and at the end of input, we are trying to make parent['a'] as 'd' which is not possible since 'a' already has a parent assigned, thus error.

If no error occurs,

  1. add first input symbol,
  2. add first child to the beginning and repeat the process
  3. add second child to the end and repeat the process
  4. add remaining characters.

Is there some test case which I missed?

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

    For my dfs approach, I checked for cycles and that degree of each vertex is less than 3.

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

      Thanks. Yeah, that was my initial approach and I am sure it gives AC. But, I thought my current approach automatically handled the check for degree. I will have a look at it again and see if the check is required to be explicitly handled.

      EDIT: Yeah the condition wasn't handled, now it gave AC :-)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone used adjacency list to solve C ? If so could you share your idea/implementation thanks

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

    Here is my submission — 70873445
    Just store the letter as an undirected graph and make sure that every vertex has degree 1 or 2.
    Then loop through all the vertex and find the vertex which has degree 1 because that would be the start/end of the graph.

    Now go for dfs, if you find a cycle in the graph, that means it's not possible, otherwise dfs will give you the starting letters of the keyboard.

    Then just add the remaining alphabets back in the string.

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

The problem statement of F says

$$$1 \le c_i \le max(1000,\lceil \frac{2⋅10^6}{nm} \rceil)$$$

.

Should not that be $$$min$$$ instead of $$$max$$$?

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand why my code for G is TLE on test 33? I've read the editorial and I think I am doing the same thing.

https://codeforces.com/contest/1303/submission/71252477

  • »
    »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I had also struggled from test 33, and finally made it accepted.

    I don't know what exactly is test 33, but this test generator code would be helpful. It takes about 20 sec on N=150000 on your code.

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <vector>
    #include <random>
    #include <ctime>
    #include <queue>
    #include <cmath>
    
    using namespace std;
    
    inline int randint(int a, int b) {
    	return rand()%(b-a+1) + a;
    }
    
    int main() {
    	int n;
    	//cin >> n;
    	n = 150000;
    	
    	cout << n << endl;
    	
    	srand(time(0));
    
    	vector<int> perm(n+1, 0);
    	for (int i=1; i<=n; i++) perm[i] = i;
    	for (int it=n*10; it--; ) {
    		int a = randint(1, n);
    		int b = randint(1, n);
    		swap(perm[a], perm[b]);
    	}
    
    	// sqrt tree, binary tree
    	int sq = sqrt(n);
    	// int sq = 2; // binary
    	queue<int> qu;
    	qu.push(1);
    	int p = 2;
    	while (p <= n) {
    		int a = qu.front(); qu.pop();
    		for (int i=0; i<sq; i++) {
    			cout << perm[a] << ' ' << perm[p++] << endl;
    			if (p == n+1) break;
    			qu.push(p-1);
    		}
    	}
    	/* */
    	
    	for (int i=1; i<=n; i++) {
    		cout << randint(1, 1000000) << ' ';
    	}
    	cout << endl;
    }
    
    

    Use the output of the generator code as the input.

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

      For me, it was a problem from cache. I had used so many random-accessing on arrays, and it became x8 faster when I fixed into a cache-friendly code.

      • »
        »
        »
        »
        9 days ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Thanks I may have a chance to fix it now. All my own generated samples ran in <2 seconds

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the solution for problem b

i think it gives right answer for 5 1 5 but wrong for 10 1 10

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

Typo in D, case 2, "most" should be "least".

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

How to proof that D solution is optimal(finds min number of divides)?

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

Getting WA on Test 2: "Jury has found answer but participant has not (test case 34)" https://codeforces.com/contest/1303/submission/71554557

Help pls.

»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi pikmike! Why the scheduled codeforces educational round 83 was deleted?

»
31 hour(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I wanna ask that in problem D, how can we make sure that when sum of all the ai is >= n, the answer is yes. I don't really get it :(

P/s: Now i got it, we don't have to put all the boxes into the bag. Right