Vladosiya's blog

Codeforces Round #787 (Div. 3) Editorial
By Vladosiya, history, 3 years ago, translation, In English

1675A - Food for Animals

Idea: MikeMirzayanov

Tutorial
Solution

1675B - Make It Increasing

Idea: MikeMirzayanov

Tutorial
Solution

1675C - Detective Task

Idea: Gol_D

Tutorial
Solution

1675D - Vertical Paths

Idea: MikeMirzayanov

Tutorial
Solution

1675E - Replace With the Previous, Minimize

Idea: myav

Tutorial
Solution

1675F - Vlad and Unfinished Business

Idea: Vladosiya

Tutorial
Solution

1675G - Sorting Pancakes

Idea: Vladosiya

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

Comments Comments (29)
| Write comment?
»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

With respect to the F problem, another (maybe simpler?) explanation:

  1. hang the tree from x (or y, it's equivalent)

  2. iteratively remove all leaves that are not in a or [x, y], we'll end up with only nodes that we'll visit

  3. all edges from the resulting graph need to be traversed twice (back and forth), except the ones connecting x to y

  4. if the graph after step 2 has n edges, the solution is 2 * (n — 1) — depth[y]

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

In case someone is interested, I made video Solutions for D-F

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

.

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

Maybe C is simpler if we do

3 Cases:

  1. It is a '?' increment counter

  2. it is a 0, return counter + 1

  3. it is a 1, reset the counter and set it to 1.

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

Can anyone explain what does int lend = min(j, k - a[i]); mean, in problem G?

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

    It's the number of pancakes, we need to take from dishes with bigger index. k — a[i] is how many is missing to get sum = k but we can't need more than j, because all pancakes on previous dishes are placed, so it's min(j, k — a[i]).

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

Question D，why I always got tle if i look for the path from up to bottom?

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

    and also tle with the tutorial's method

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

My $$$O(n * m^3)$$$ for G almost got TLE. Submission

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

Any resources or similar problems to better understand G? Still confused by just reading editorial.

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

Can anyone explain the solution of the problem G-Sorting Pancakes??

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

    In G, intuitively we see that a dp solution will work. If we want to put some pancakes on the ith dish, we need to have the same or more pancakes on the previous dish. To determine what can be put down later, we need to know how many pancakes we have put down previously. Hence, we need to take note of 1) how many pancakes we put down on the ith dish, and 2) how many pancakes we have put down in total. These will form our state. Hence we can have dp[i][number of pancakes on ith dish][number of pancakes put down in total] to describe our solution. The number of states for dp[n][m][m] is n * m * m which is 250 * 250 * 250 which is small enough.

    To transition to dp[i][j][k], we come from a previous state with fewer total pancakes. But the previous state's number of pancakes must be more. So we have dp[i-1][j2>=j][k-j] -> dp[i][j][k]. So, dp[i][j][k] = min(dp[i][j][k], dp[i-1][j2][k-j] + some transition value) for all j2>=j. The transition value (referred to as "add" in the editorial) is the number of moves required to go from a "pancake configuration" of having k-j pancakes in the first i-1 plates, to the same configuration but with exactly j pancakes on the ith plate. I don't know how people calculate these transition values elegantly. I had a greedy and incredibly messy way to calculate these.

    Finally, the answer is the minimum value for dp[n — 1][j][m], for 0<=j<=m. I hope this helps.

    You may refer to my solution 156195983 but it is in python, with the differences of me reversing a to solve for increasing pancakes, and I switched the definitions for j and k. So my definition is dp[i][prefix sum of pancakes up to i][number of pancakes on i].

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

      can u elaborate why the dp is : dp[i][number of pancakes on ith dish][number of pancakes put down in total] and why not dp[i][number of pancakes put down in total][number of pancakes on ith dish] ? Can we imagine this as a 3D matrix? If so, then what do the row, column and height of this matrix implicate?

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

        Both ways work. I used the latter which is dp[i][number of pancakes put down in total][number of pancakes on ith dish] in my actual solution. But the solution used in the editorial uses the former which is dp[i][number of pancakes on ith dish][number of pancakes put down in total].

        I will also discourage you from visualizing dp matrices spatially because it is very difficult and unnecessary. The important thing for doing dp is to have a firm understanding of the states, their transitions and their edge/boundary cases.

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

Can someone explain the solution for problem E. Tutorial is somewhat complicated to understand.

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

Can you please explain why in the task g dp transitions are d[i][last][k] = d[i-1][last][k-last] does it means that last = j, instead of last >= j?

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

I solved problem F with dfs, dp, and LCA+binary lifting. A lot more stuff than needed lol

156882408 Warning: Code is quite messy and I haven't commented. Enter at your own peril.

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

Can someone please explain this majestic code by jiangly? 155996756

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

Can problem B be done without applying operations on the array element?

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

    yes we can use log2() to calculate how many time do we have to divide

    like so std::log2(static_cast(arr[it]/arr[it+1]))+1

    you can check for diff test cases

    note: use std::log2() to avoid precision issues (took me 30 min to figure it out).

    → Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it 
#include<bits/stdc++.h>
using namespace std;
typedef long long lli;

int T, N;
lli ar[100];

void solve(){
	cin >> N;
	for(int i = 0; i < N; ++i)
		cin >> ar[i];

	int oprn = 0;
	for(int i = N - 2; i >= 0; --i){
		while(ar[i] > 0 && ar[i] >= ar[i + 1]){
			ar[i]/= 2;
			oprn++;
		}
		if(i > 0 && ar[i] == 0){
			cout << - 1 << "\n";
			return;
		}
	}
	cout << oprn << "\n";
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

Getting wrong answer from this solution.1675B][CONTEST:1675 - Make It Increasing

→ Reply