Dynamic Programming Training [Div. 3 Walkthrough]

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
38:15:47
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя nskybytskyi

Dynamic Programming Training [Div. 3 Walkthrough]

Автор nskybytskyi, история, 4 года назад, По-английски

First of all, apologies for a rather long absence, I was a bit tired after Round #694 (Div. 1) in which I got a significant positive rating change. It is always nice to see your work paying off, but let us get back to business.

Codeforces has an excellent archive of training contests, named gyms!

But it is very well possible that you do not know about the one beginner-friendly gym that I want to cover today, and the reason is that it is only available in Russian :|

I translated the statements to English for you, and recorded a problem walkthrough, in case you ever get stuck.

We will cover more gyms from this old but gold series by Saint Petersburg State University in the future, so stay tuned!

Разбор задач 2012-2013 Тренировка СПбГУ С #5. Динамическое программирование.

#youtube, #dp

nskybytskyi
4 года назад
37

Комментарии (26)

Показать архивные | Написать комментарий?

abhisar1414

4 года назад, # |

+11

will you upload same for div 2 and div1 too ?

→ Ответить

nskybytskyi

4 года назад, # ^ |

← Rev. 2 →

I'm not sure if this series contains Div. 1 problemsets, but I'll cover Div. 2 DP training problemset in the future.

→ Ответить

Jratos

11 месяцев назад, # ^ |

hey, can you point it out the div2 dp training?

→ Ответить

Alisher_Kamolov

4 года назад, # |

+11

Thank you very much nskybytskyi

→ Ответить

orendon

4 года назад, # |

+11

This is great, thanks for doing this! PD: Would be nice if the english PDF can be attached along with the russian one,

→ Ответить

nskybytskyi

4 года назад, # ^ |

I agree. I'll contact Mike when I have enough translated problemsets, but I don't want to waste too much of his time asking him to add each time separately.

→ Ответить

Noureldin

4 года назад, # ^ |

I added it for you.

you could have done it yourself, just turn coach mode on in the gym

→ Ответить

nskybytskyi

4 года назад, # ^ |

Oh, thank you! Maybe I was not around when this feature arrived and did not realize that I have such permissions.

→ Ответить

captcha01

4 года назад, # |

nskybytskyi In problem J's input file format, I think you wanted to write $$$0 \leq n \leq 22$$$. BTW, Nice Effort :D

→ Ответить

nskybytskyi

4 года назад, # ^ |

Thanks, corrected

→ Ответить

TiredOfLife

4 года назад, # |

Hi ! Can you please tell me the meaning of this in problem H "if any two of its elements differ at least two times." At least two times with respect to what ?

→ Ответить

MuhammadAl-Halaby

4 года назад, # ^ |

I had some trouble understanding it at first but I wrote a solution to verify my understanding.

Here is a better statement:

"We call a set of positive integers peaceful, if for every pair of elements in the set, the larger number in the pair is at least twice the value of the smaller one.

We call the sum of the elements of the set its strength. Find the number of peaceful sets of a
given strength."

→ Ответить

TiredOfLife

4 года назад, # ^ |

Thanks :)

→ Ответить

atlas_flame

4 года назад, # ^ |

← Rev. 2 →

I know it is late but can you help me understand the sample test case? UPD: I got it and solved the problem but I think the problem statement should be "a set of non-negative integers..."

→ Ответить

nskybytskyi

3 года назад, # ^ |

No, why? If we allow 0, then the number of ways gets multiplied by an extra factor of 2. You can check from the samples that this is not the case, i.e. 2 = 2 only, 2+0 is not allowed.

Perhaps your confusion arises from the (false) belief that a set needs to have at least two elements. This is not the case either, one-element sets are totally fine.

→ Ответить

OtabekJurabekov

3 года назад, # ^ |

Thank u bro. I was confused

→ Ответить

not-an-alt

4 года назад, # |

Why does your solution to the problem K work ? You said in the video that it is a well known formula. Where can I learn about it ?

Code

#include<bits/stdc++.h>
using namespace std;

int main() {
	int N, P;
	cin >> N >> P;
	int last = 0;
	for (int i = 1; i <= N; i++) {
		last = (last + P) % i;
	}
	cout << last + 1 << '\n';
	return 0;
}

→ Ответить

monna4335

4 года назад, # |

← Rev. 4 →

Update:Solved.

I'm getting wa on 1 in problem J.I tried to run my code on cf's Ide.It worked.Can Anyone help me to find out my error?

code

→ Ответить

epsilon_delta

3 года назад, # |

Problem-E [help]
please help what I am doing wrong??

Spoiler

#include <bits/stdc++.h>
using namespace std;
 
void solve(){ 
   int n;cin>>n; 
   vector<vector<int>> vec;
   vector<vector<int>> dp(n,vector<int>(n,-1000000));
for(int i=0;i<n;i++){
    vector<int> v;
    for(int j=0;j<=i;j++){
        int k;
        cin>>k;
        v.push_back(k);
    }
       vec.push_back(v);
}

dp[0][0] = vec[0][0];
int mx = -100000000;

 for(int i=1;i<n;i++){
    for(int j=0;j<=i;j++){
      if(j>0) dp[i][j] = max(dp[i-1][j-1]+vec[i][j],dp[i][j]);
      if(j<i) dp[i][j] = max(dp[i-1][j]+vec[i][j],dp[i][j]);
      if(i==n-1) mx = max(mx,dp[i][j]); 
    }
 }
 cout << mx;
}
 
 
int main(){
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ; cout.tie(0) ;
    cout.precision(20);
    int T=1;//cin>>T;
    while(T--){
        solve();
        if(T)cout << endl;
    }
    return 0;
}

→ Ответить

AlexPop28

3 года назад, # ^ |

$$$n = 1$$$ fails. Other than that, it seems correct to me.

→ Ответить

Beginner

3 года назад, # |

can you please open the permission to see others solution @nskybytskyi (hope this work),it would be very helpful :D

→ Ответить

nskybytskyi

3 года назад, # ^ |

First, mentions work like [user:Beginner] : Beginner. Second, the decision not to show solutions is intentional, for educational purposes. Please take your time to solve the problems yourself, and refer to the video if necessary.

If you really can't wrap your head around a problem after spending a good chunk of time on it, it may be better to just forget about it and come back after a longer period of time. Otherwise, you are unlikely to learn much from reading the code of others.

→ Ответить

abhishek_kira

3 года назад, # ^ |

Sir The submission on J problem bad substrings is getting a Runtime Error on test 1 , I have cross-checked it with ur solution , getting same RE on test 1 ? Any fix..

→ Ответить