1388A - Captain Flint and Crew Recruitment
Idea: Denisov
Tutorial
Tutorial is loading...
Solution (Karavaev1101)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int q;
cin >> q;
while(q--){
int n; cin >> n;
if(n <= 30){
cout << "NO" << endl;
}
else{
cout << "YES" << endl;
if(n == 36 || n == 40 || n == 44){
cout << 6 << ' ' << 10 << ' ' << 15 << ' ' << n - 31 << endl;
}
else{
cout << 6 << ' ' << 10 << ' ' << 14 << ' ' << n - 30 << endl;
}
}
}
}
1388B - Captain Flint and a Long Voyage
Idea: Karavaiev
Tutorial
Tutorial is loading...
Solution (Karavaev1101)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int q;
cin >> q;
while (q--) {
int n; cin >> n;
int x = (n + 3) / 4;
for (int i = 0; i < n - x; ++i) {
cout << 9;
}
for (int i = 0; i < x; ++i) {
cout << 8;
}
cout << endl;
}
}
1388C - Uncle Bogdan and Country Happiness
Idea: Karavaiev
Tutorial
Tutorial is loading...
Solution (Karavaev1101)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
vector < int > gr[N];
bool access = true;
int p[N], h[N], a[N], g[N];
void dfs(int v, int ancestor = -1) {
a[v] = p[v];
int sum_g = 0;
for (int to : gr[v]) {
if (to == ancestor) continue;
dfs(to, v);
sum_g += g[to];
a[v] += a[to];
}
if ((a[v] + h[v]) % 2 == 0) {} // first
else access = false;
g[v] = (a[v] + h[v]) / 2;
if (g[v] >= 0 && g[v] <= a[v]) {} // second
else access = false;
if (sum_g <= g[v]) {} // third
else access = false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int q;
cin >> q;
while (q--) {
int n, m; cin >> n >> m;
for (int i = 0; i < n; ++i) cin >> p[i];
for (int i = 0; i < n; ++i) cin >> h[i];
for (int i = 0; i < n - 1; ++i) {
int a, b; cin >> a >> b;
--a, --b;
gr[a].push_back(b);
gr[b].push_back(a);
}
dfs(0);
cout << (access ? "YES" : "NO") << endl;
access = true;
for (int i = 0; i < n; ++i) gr[i].clear();
}
}
1388D - Captain Flint and Treasure
Idea: Denisov
Tutorial
Tutorial is loading...
Solution (Denisov)
#include <bits/stdc++.h>
#define ll long long
#define all(a) a.begin(),a.end()
using namespace std;
vector <vector <int> > edge;
vector <ll> a;
vector <int> b, used;
vector <int> order[2];
ll ans;
inline void dfs (int v) {
used[v] = 1;
for (int to : edge[v]) {
if (!used[to]) dfs(to);
}
ans += a[v];
if (b[v] != -1 && a[v] > 0) {
a[b[v]] += a[v];
}
if (a[v] > 0) {
order[0].push_back(v);
}
else {
order[1].push_back(v);
}
}
inline void solve () {
for (auto &i : edge) i.clear();
edge.clear();
a.clear();
order[0].clear();
order[1].clear();
b.clear();
used.clear();
int n, x;
cin >> n;
edge.resize(n);
a.resize(n);
b.resize(n);
for (auto &i : a) cin >> i;
for (int i = 0; i < n; i++) {
cin >> x;
if (x != -1) {
--x;
edge[x].push_back(i);
}
b[i] = x;
}
ans = 0;
used.assign(n, 0);
for (int i = 0; i < n; i++) {
if (!used[i]) {
dfs(i);
}
}
cout << ans << '\n';
reverse(all(order[1]));
for (auto &i : order[0]) cout << i + 1 << ' ';
for (auto &i : order[1]) cout << i + 1 << ' ';
cout << '\n';
}
main()
{
ios::sync_with_stdio(0);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
Solution (Karavaev1101)
#include <bits/stdc++.h>
#define Vanya Unstoppable
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n;
cin >> n;
long long a[n];
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
set < int > s;
for (int i = 0; i < n; ++i) {
s.insert(i);
}
int b[n];
vector < int > sz(n);
for (int i = 0; i < n; ++i) {
cin >> b[i]; --b[i];
if (b[i] == -2) continue;
++sz[b[i]];
if (sz[b[i]] == 1) {
s.erase(b[i]);
}
}
long long sum = 0;
vector < int > ans[2];
while (!s.empty()) {
int v = *s.begin();
s.erase(s.begin());
int w = b[v];
sum += a[v];
if (a[v] >= 0) {
if (w >= 0) {
a[w] += a[v];
}
ans[0].push_back(v);
} else {
ans[1].push_back(v);
}
if (w >= 0) {
--sz[w];
if (sz[w] == 0) {
s.insert(w);
}
}
}
cout << sum << endl;
for (int to : ans[0]) cout << to + 1 << ' ';
reverse(ans[1].begin(), ans[1].end());
for (int to : ans[1]) cout << to + 1 << ' ';
cout << endl;
}
1388E - Uncle Bogdan and Projections
Idea: perekopskiy
Tutorial
Tutorial is loading...
Solution (perekopskiy)
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
const double eps = 1e-9;
double xl[N], xr[N], y[N], pi = acos(-1), mn_x, mx_x;
int ind_l, ind_r;
double point_pr(double x, double y, double ctg) {
return x - y * ctg;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
vector<pair<double, int> > q;
vector<pair<double, pair<int, int> > > events, prom_left, prom_right;
cin >> n;
pair<double, double> mx, mn;
mx = {-1.0, -1.0};
mn = {2e9, 2e9};
mn_x = 2e9;
mx_x = -2e9;
for(int i = 0; i < n; ++i) {
cin >> xl[i] >> xr[i] >> y[i];
if(xl[i] < mn_x) {
mn_x = xl[i];
}
if(xr[i] > mx_x) {
mx_x = xr[i];
}
if(mx.y < y[i]) {
mx.y = y[i];
mx.x = xl[i];
ind_l = i;
}
else if(mx.y == y[i] && mx.x > xl[i]) {
mx.y = y[i];
mx.x = xl[i];
ind_l = i;
}
if(mn.y > y[i]) {
mn.y = y[i];
mn.x = xl[i];
ind_r = i;
}
else if(mn.y == y[i] && mn.x < xl[i]) {
mn.y = y[i];
mn.x = xl[i];
ind_r = i;
}
}
double a1, a2;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(y[i] > y[j]) {
a1 = (xr[i] - xl[j]) / (y[i] - y[j]);
a2 = (xl[i] - xr[j]) / (y[i] - y[j]);
q.pb({a1, 1});
q.pb({a2, 2});
a1 = (xl[i] - xl[j]) / (y[i] - y[j]);
a2 = (xr[i] - xr[j]) / (y[i] - y[j]);
events.pb({a1, {i, j}});
events.pb({a2, {-i - 1, j}});
}
}
}
if(q.empty()) {
cout << fixed << setprecision(9) << mx_x - mn_x << endl;
return 0;
}
sort(q.rbegin(), q.rend());
int cnt = 0;
double last = 0;
for(auto i : q) {
if(i.y == 2) {
--cnt;
if(!cnt) {
events.pb({i.x, {-1e9, -1e9}});
}
}
else {
if(!cnt) {
events.pb({i.x, {-1e9, -1e9}});
}
++cnt;
}
}
sort(events.rbegin(), events.rend());
double ans = 1e18, ang;
last = -1e18;
for(auto i : events) {
if(i.y.x == i.y.y) {
unordered_set<int> s;
vector<int> to_check;
for(auto j : prom_left) {
s.insert(j.y.x);
if(j.y.x == ind_l) {
to_check.pb(j.y.y);
}
}
prom_left.clear();
for(auto j : to_check) {
if(!s.count(j)) {
ind_l = j;
break;
}
}
s.clear();
to_check.clear();
for(auto j : prom_right) {
s.insert(j.y.y);
if(j.y.y == ind_r) {
to_check.pb(-j.y.x - 1);
}
}
prom_right.clear();
for(auto j : to_check) {
if(!s.count(j)) {
ind_r = j;
break;
}
}
s.clear();
to_check.clear();
double res = point_pr(xr[ind_r], y[ind_r], i.x) - point_pr(xl[ind_l], y[ind_l], i.x);
if(ans > res) {
ans = res;
ang = i.x;
}
}
else if(i.y.x < 0) {
if(abs(i.x - last) > eps) {
unordered_set<int> s;
vector<int> to_check;
for(auto j : prom_right) {
s.insert(j.y.y);
if(j.y.y == ind_r) {
to_check.pb(-j.y.x - 1);
}
}
prom_right.clear();
for(auto j : to_check) {
if(!s.count(j)) {
ind_r = j;
break;
}
}
s.clear();
to_check.clear();
}
prom_right.pb(i);
}
else {
if(abs(i.x - last) > eps) {
unordered_set<int> s;
vector<int> to_check;
for(auto j : prom_left) {
s.insert(j.y.x);
if(j.y.x == ind_l) {
to_check.pb(j.y.y);
}
}
prom_left.clear();
for(auto j : to_check) {
if(!s.count(j)) {
ind_l = j;
break;
}
}
s.clear();
to_check.clear();
}
prom_left.pb(i);
}
last = i.x;
}
cout << fixed << setprecision(9) << ans << endl;
return 0;
}
Thanks for the quick editorial!
Feel free to downvote, but this is my honest opinion; Personally, I think that the grammar of problem C made it abit annoying to understand.
Agreed. If not for the notes, I probably would have wasted a lot of time understanding the statement.
Yup, I don't mean to complain, but statements similar to these felt somewhat distracting-> "Every person has its own mood: somebody leaves his workplace in good mood but somebody are already in bad mood."
Totally disagree. You can of course point out a few subtle grammar mistakes, but they don't obscure the general idea.
was writing " was made it a bit annoying" on purpose? If so, it's funny. If not, it's sad XD
Lengthy background but interesting problems.
I agree. you know most of the participants mother language isn't english and they can't get the statement easily, when you make the statement hard to understand, it will be really hard for them and sometimes they just skip the problem and lose it points because they can't understand the statement, and that will give them a really bad point at the contest. so please take more care for the statements.
Yes, I totally agree with you. As I am not a native English speaker or a native Russian speaker(I am Chinese), for some problems the statement is very difficult to understand(QAQ) and extremely complicated, although the statement itself is quite easy.
Lol I was in bad mood after reading the long statement of C. Missed it by one case
do yoga it will help you
For problem D--can anyone please explain or give a test case where my solution is going wrong. The testcases in problem are too big to debug.
Here is the link to my submission.
I am bascially making a directed graph where an edge from u to v denotes that operation on u-th element must be done before v-th element of the array a. Then I am running a dfs on transpose of this graph and updating all elements(suppose v-th and w-th index element needs to be operated before u-th element, then updating a[u]=a[v]+a[w]) and adding those to answer while maintaing this order.
Your solution fails on that test case:
3
6 -5 1
2 3 -1
9
1 2 3
Your solution works that way because after doing some operations $$$a_{b_i}$$$ can become positive and you can improve other $$$a_j$$$ using that $$$a_{b_i}$$$
How to solve D if we remove additional constraint ( if Cycle is there ) ?
Would anybody help me with Question D?
My submission --> 88521832.
Approach: I made a 2D array of row size n to see whether there is any index that must be ahead than index i(0<=i<n). And then I just simulated for indices based on the array to determine the answer.
Variables: a and b are input array, c is array to determine which indices should come prior index i. array d is for storing the answer array. ans is calculated based on d. s is just counter to see all n indices are in d. every array is 0-indexed.
I'm sorry that my English is not very well.
There's a situation in the process of Adding $$$a_i$$$ to $$$a_{b_i}$$$ that it may change $$$a_{b_i}$$$ from negative to positive.In this situation,if $$$b_{a_{b_i}}$$$ doesn't equal to $$$-1$$$,it should be also ahead some than some index.But it seems that you didn't manage to do this.
Note that there's a principle that no matter what $$$b_i$$$ is,we should always put the index with $$$a_i > 0$$$ ahead of the index with $$$a_i < 0$$$.
there's a sample that your algorithm makes mistakes:
Input
3
-2 -1 4
-1 1 2
Output
8
3 2 1
But your output is:
5
1 3 2
Hope my reply could help you.
Thanks man! I got it now.
Video solution of the whole problemset
hoping it won't let us down
Why don`t topological sort works in D?88526038
I solved this problem using topological sort. You can check my submission.
here's my AC submission with topological sort -> 88536305
Can You Explain it.
How are you maintaining the last sequence ? UPD: I got it.
Performing the operation on any ai < 0 before any aj > 0 may decrease the maximum sum, right?
That's why you have to perform the operation on those positions at last (from bottom to top in topological order, so that it won't affect any ai < 0 too), so that it won't affect the maximum sum.
My submission using topsort
In fact,the solution by Karavaev1101 is topological sort,though it's hard to tell.
You're right
It's my 2nd contest.I solved a no. problem.But still no rating given.How long does it take to get ratings after a contest is finished?
Hey, The ratings have arrived. You can see them if you want.
Yeah!
I got 242 plus ratings!
Greattt!!! Keep going mate...
In my humble opinion problem set was amazing, but problem B was made a lot obvious by the example input, it could have been swapped with problem A if problem A constraints were made a bit tighter and brute force was not allowed.
Hey I think prob A was very easy...
I mean just look at the code, it's basic brute force...
``
Yeah isn't B also a relatively basic observation.
Yeah sure but I missed a very important line NOTE resulting in my WA twice and then I was able to get it right...XD
Because of that I missed problem C.
hello, in problem B if I have n = 5 then the number must be 9 9 9 9 9
in binary : 1001 1001 1001 1001 1001
but after removing last 5 digits then it become
1001 1001 1001 100- ----
which makes it a 4 digit number, so making that 5 digit number I need to make it all 0s :
1001 1001 1001 1000 0000
but this doesn't the case.
Can anyone help me with that ?
Why do you think 0's binary is considered 0000? Why not 0000000000000 or anything else? Answer this and you'll get your answer as well.
did u know, you wasted 61 seconds in this counting!! lol :>
what kind of error is it "wrong output format Unexpected end of file — int32 expected" ? i did not see before . 88520911
The grader was expecting more numbers(int32) in the output, but your solution did not print them. Check if you are printing the required output in the specified format. You can check my submission for more clarity.
Great round, guys!
In problem C How can (av+hv)/2 count the number of people in a good mode?
suppose X are the people that were happy at city A and Y were the people that were not happy at the same city. Then X+Y = total citizens that visited the city(total citizens in subtree of that city). X-Y = (happy-sad) given for city. Add both equations and get the value of X which is same as described in the editorial.Hope you understand.
Edit- by happy i mean good mood as in problem statement.
Thanks!
Honestly I didn't solve it like that, but I'll explain.
Think that moods are G good and Y bad, in a city with P people. Do you agree that P == G + |Y|? Do you agree that H = G — |Y| ?
Then P + H = G + |Y| + G — |Y| = 2G, and we are done.
Thanks!
let gv be the number of people in a good mood that passes through node v, and bv the number of people in a bad mood. With that we can write the following system of equations: gv-bv = hv and gv+bv = av. If we sum the both equations we get 2gv = av + hv and thus gv = (ah+hv)/2
Thanks!
Me to the second question :: WHy you do this to me????? :(
https://codeforces.net/contest/1388/submission/88510199 whats wrong with this submission for C?
I don't understand, in problem E — isn't there an easier way to calculate the projections? I don't know what the Convext Hull Trick is, but I mean, you have the angle and you have the height, that should be enough. Is the problem the fact that there could be error in the calculation and you will get a wrong result?
It's a problem that you can't project every segment for every angle because it takes too much time, so we need to find the rightmost and leftmost projections quickly
If you calculate the projection of $$$O(n)$$$ vectors for each possible angle (there are $$$O(n^2)$$$ of them) the complexity becomes $$$O(n^3)$$$.
Ahhhh never mind I completely missed something. I thought the "no go" zones make a full range [theta1,theta2], and then you are left with only 2 angles to check. I understand now that there could be many options.
By merging overlapping angle segments, it is possible to pass the time limit via this brute force method.
88545255
Here I am generating a ton of primes and trying to do sliding window 3 sum with prefix sum to solve 2A and still couldn't. :(
RIP rating. I'm sad.
I also had a sad story but it turned out ok.
At first I read the problem as "multiple" instead of "sum". I solved it though xD
You just need the prime factorization and you need to pair up 3 pairs of different primes. (8 * 3 * 5 * 7 ==>> 2*3, 2*3, 2*5). (That made me 15 minutes behind :| )
Edit: I need to start making it a priority to look at the god damn sample cases to verify I read the problem correctly.
My video solutions to problems A, B, C, D.
Enjoy watching.
https://youtu.be/0ExktAwScLc
thanks a lot!!
Wow, that's weird, why your rating started from 0? (Normally it starts from 1500)
Did I miss some updates?
Unfortunately, I couldn't find the blog for you. but yes, new account ratings start from 0 now.
Thanks :)
You missed this
Oh, thanks!
Didn't got AC at C be cause I was using python. Rewrote it in C++ and got AC. Don't use python in recursion problems...
Look at my solution, I use this "boostrap" decorator that someone posted a while back (I use it all the time and it always works), that replaces the recursion.
It looks like this:
Just notice —
To make the recursive call, you have to use yield.
When you call recursively, you can't do 'if yield dfs(..)' or stuff like that, you have to first save the value with 'x = yield dfs(...)'.
When you want to return something, you have to use yield (i.e., 'yield 5').
At the end of the function, if you return nothing, you have to use 'yield' with nothing after. THIS IS THE MOST IMPORTANT POINT. if you forget this you will spend eternity debugging.
Thank me later.
Can we implement it in c++
Well, you don't need it in c++... 10**5 recursion works fine for you.
I just wanna try, how to replace the *args thing what is that??
Lol you will literally not be able to do that, You have to implement a generator and I have no idea how you could do that in cpp.
There's a reason python exists. One of those reasons is that you can do stuff like this in less than 1000 lines of code.
Can someone help me find the missing case here in my submission of problem C? I am unable to find the corner case here:My Submission
Thanks in advance
https://codeforces.net/contest/1388/submission/88541430
Got it... Thanks Again
https://codeforces.net/contest/1388/submission/88555906 Can you please check my code, It fails on test case 3 and I am unable to find actual test case
Can't see where you are using condition: "If person is in bad mood he won't improve it."
grey Can you please see where I am going wrong. My submission. Thanks in advance god[i] is number of good people in city i into[i] is number of people who pass through city i
I had the same idea as the tutorial for problem no C, don't know where I messed up. :(
My friend who got into coding tried CF for first time and he received RE on both of his solutions, while locally it worked. As I'm not familiar with python, can somebody explain what is wrong? Thanks
submissions: https://codeforces.net/contest/1388/submission/88484222, https://codeforces.net/contest/1388/submission/88506487
'input' doesn't work like that. First of all, input is a function, so it should be 'input()'.
Second of all, it only reads one line.
To get a line with an int you do int(input()).
To get a list you do [int(x) for x in input().strip().split()] or list(map(int,input().strip().split())) or some other way.
Can anybody please tell me where am I going wrong. Thanks in advance here B, G is no.of people in a bad and good mood respectively
Update : I am dumb
Use spoiler for posting your code
you if conditions are wrong recheck them
Kudos on -50 contribution _pastor_
(ಥ﹏ಥ) thyyaanxx
for problem c, i checked if(abs(h[i])>count[i] || count[i]%2 != abs(h[i])%2 ) then its not possible where count[i] = number of people visiting that node and h[i] = happiness value of i node.the second condition ensures that for a node with count = 5,the possible hvalues are -5,-3,-1,1,3,5 only.can anyone tell me why is it wrong? https://codeforces.net/contest/1388/submission/88539137
You have only checked the upper limit i.e. abs(h[i])>count[i]. There will be a lower limit as well. suppose there are 2 cities i and j with i being the parent of j. now, let count be the number of people visiting j. Then let x be the the number of people with good mood and y be people with bad mood. Clearly , x+y=count and x-y = h[i].From here you can get x and y. Now , for the city i, the range would be [x-y,x+y].Because, There must be atleast x people with good mood. If you want the sol , refer to — 88508137
Can someone please explain why in Problem D we reverse the second array ( the array with -ve elements ).
So that negative values don't add up at any vertex.
For problem E, the leftmost/rightmost segments can be handled in a similar manner as the "feasible angles" approach, by sequentially "trimming" the ranges where each of the $$$n$$$ segments is the leftmost/rightmost one.
Code (sorry for too few newlines)
Can anyone please tell me? In solution of C, how g[v]=(a[v]+h[v])/2 ?
g[v](which is total good mood persons passes through vertex v)...................... calculate it through this given happiness index and no. of people passes. now the happiness index will be (acc. to question) (g[v]-(a[v]-g[v])),where (a[v]-g[v]) is sad people passes. hope u got it
let $$$b_v$$$ be the number of people who visited city $$$v$$$ in a bad mood then $$$h_v = g_v - b_v,\,a_v = g_v + b_v$$$, and $$$\frac{a_v + h_v}{2} = \frac{g_v + b_v + g_v - b_v}{2} = g_v$$$
Thanks a lot!! :D Got it!
I tried C with a little different approach. I calculated the number of people who travelled through a particular node with dfs and then applied bfs to check if the sum of unhappy people in children should be more than or equal to the number of unhappy people who travelled through the ancestor. I cannot figure out my error. A little help will go a long way. Code
It is not not necessary that sum of unhappy people in children should be more than or equal to the number of unhappy people who travelled through the ancestor because some of the unhappy people might live in the ancestor city.
Thanks for the tutorial. I really need this to improve myself.
ok, during contest my solution for B was correct but now its showing TLE but if i submit it again it got accepted what is happening, here are both submissions TLE submission AC submission
I am not sure but it has something to do with dynamic strings you are using, in first submission you code might have encounter memory issues. like you are making a string of size (maxN). when ever you push a char into it. string needs a contiguous free space to instert if it is not there then string will move the whole string to a place where memory is available. and this operation takes O(n) time to execute.
that means complexity of your code could have crossed $$$N^2$$$ in this way on multiple occassions.
look at this submission : https://codeforces.net/contest/1388/submission/88556412
i just wanted to see how it looks to add code like this in comments.
in this code i reserved a contiguous memory space of N for my string at very first. and look it only took 30ms to execute while your code did same in ~1000ms.
yeah but time limit was
2 sec
. i get the point that it is O(N*N) because i am coping the string every time like s=s+'9' every time s is copied here in right side of operator.and also after the contest same code at test case 7 run in around 600ms and the other TLE solution(same code during contest) run for >2000ms thats what i am asking i mean why is this happening just to be safe from next time.
and btw thanks for reply.so s = s + '9'; this statement can run in either $$$O(1)$$$ time or $$$O(n)$$$ time. if memory is available it will run $$$O(1)$$$ time, but if mmemory not available in contiguous manner in memory this statement will take $$$O(n)$$$ as i said it will copy the whole string to a place in memory where is avalable.
so it is not truly $$$O(n^2)$$$.
it depends on the collsions (when contiguous memory is not available and compiler will perform $$$O(n)$$$ operation.) and your code at the time of contest got more collisions than when you ran it after contest.
it might have something to do with may be that memory is under more demand during a contest in comparison to after contest.
if your code's string get assigned a memory place from which a contiguous space which required is available in that your code will run in 30ms.
If you want to be safe from next time then becareful while using dynamic memory allocations. and reserver memory before hand as much required in one statement. like most common mistakes like these are using unordered_map. link. https://www.geeksforgeeks.org/unordered_map-reserve-in-c-stl/
i have a friend who uses char arrays instead of string to be extra safe.
Nice problems.. Short solutions... quick editorial.. :)
This link is my submission to question C of yesterday's contest. Could someone please help by pointing out where am I going wrong?
Thanks in advance
In Problem C, you guys gave the necessary conditions with simple proofs, but what is the proof that these conditions are sufficient??
For problem C i checked for each node whether the number of happy people in that city is less than or equal to its parent node.Can someone tell why this approach is giving wrong answer?
You should check sum of happy people in all children of a parent is less than or equal to happy people of parent as happy people cannot increase.
But in your approach happy people can increase.
Take example A is parent and B,C,D are children. Happy at A=6, Happy at B=5, Happy at C=5, Happy at D=5. In this case your all conditions are satisfied and answer should be yes according to you but answer is no.
In this situation you see that happy people at parent is 6. But moving ahead happy people increases it becomes 5*3=15 at children. It means bad mood people are decreasing that is not the answer to this question.
That is why your answer is giving wrong answer.
Got it.Thank you for helping.
Yeah its fine bro. I also did similar mistake hence i thought to reply as its a learning platform and we can learn only by helping others and taking help from others.
https://codeforces.net/contest/1388/submission/88555647
can anyone help me with this solution for problem D?
C question was awesome, it helped me revise all concepts of dfs.
Then try D with dfs. I liked it better.
For question D, the dfs solution given in the editorial doesn't always work, since the starting point is random with straightforward dfs.
It seems to fail for —
expected — 9 given — 8
no it is not.
we are only starting from the leaves. and that is the logic.
Explain how is your expected result is 9?
The editorial solution (dfs) doesn't seem to enforce the condition that we should start from leaves. Like in the example that I have given, I ran it and the output was 8. But if we enforce the condition, it would have been 9.
i don't see how you are getting 9..?
because your test case is too small here are possible answers to you test case
1 2 3 = -3
1 3 2 = 8
2 1 3 = -3
2 3 1 = -3
3 1 2 = 8
3 2 1 = 8
there is no 9.
It seems that test
3
1 -5 6
-1 3 2
is incorrect because we have cycle $$$2, 3,2$$$ and the addition constraint says that the graph doesn't contain any cycle.
In my solutition starting point can be any vertex, but I create graph with different from the editorial edges: from $$$b_i$$$ to $$$i$$$. The solution of Karavaiev is written in the same way as editorial.
In Karavaiev solution you should change (int sum) to (ll sum) and (int a[N]) to (ll a[N]) and it will pass all the tests.
Actually, there is
#define int long long
in his code :)Yeah, sorry, didn't notice that)
I have joke for question C but I am not in good mood to tell. :)
Go back to the capital we shall then talk
In problem B, the number we are expected to find should be as small as possible, and r, as big as possible. So if the input is say 11, should the answer not be 99999999800 instead of 99999999888?
by adding 0's at last you are not agreeing with the maximum possible value for r , You can do better with adding 8 instead !Try it out on paper
Remember that each digit will be converted to binary first and only then we remove N binary digits from the resulting string.
So the idea is to maximize the number of binary digits, that's why we only use number 8 and 9 in our answer, because they are the only decimal digits that, when converted to binary, have 4 digits (1000 and 1001, respectively).
Can someone help me out with the Problem C, here is my solution, I used the similar idea as described in the tutorial, but used a different approach for implementaion.
Instead of using a single DFS, I made 2 dfs calls, one for updating the visitedPersons array for each node, then updating the happyPersons in each city and side by side checking the first two conditions. Then made another DFS call for the third condition.
I dont know where I messed up. Can someone please help. My submission
So many contests in the contest list but no div3 :(
I am eagerly waiting for a div3 after so many difficult contests. Just to gain some confidence :)
can someone suggest a test case where my solution fails 88565587
In problem C, if I am not incorrect, $$$to_1, to_2, …, to_k$$$ for city $$$v$$$ are the cities belonging to the subtree of the node which city $$$v$$$ belongs to. So, the third condition states that among such cities, sum of number of happy people entering each city must be less than or equal to the number of happy people entering the city $$$v$$$. Can someone please explain this condition? What I think is that for the happy people getting off at some city $$$to_i$$$, they will be counted every time they visit a city which is on their way home. So how is this repetition avoided?
Well, I have another approach if anyone is interested.
we will have two arrays one of positive count(person who ended up happy in subtree) and one of a negative_count(person who ended up sad in subtree)
apply dfs
You cannot change the positive_count(because they are happy in the subtree and should be happy at this node also) but you can change the mood of a person in negitive_count and persons that ended up at this node.
When You are at a node then sum the number of positive_count and negative_count in the subtree. check the condition (it is possible to get the required happiness at this node) and if it is possible then adjust the value and update the positive and negative count at that node.
code 88577713
Exactly, it didn't make sense to me,too
It's only for immediate children. They are not considering all the children in the subtree.
Nobody cares what a pupil thinks, but i'll drop it anyway. I say you are correct, we are counting duplicates as well, but here's my thinking. Consider a number of happy people in node i. Now from node i, consider we can move down to three nodes, i+1,i+2,i+3. Now, the child nodes will have a "subtree sum" of their own. now assume this to be some s1,s2,s3. Now, how did we get these many people in those subtrees? It is only because they travelled through the parents node, i. So now we can see that when you add the sum of good people from all three subtrees, to the parent node, It should be strictly greater than the sum of the individual subtree sum of their chidlren. (since that node must have 0 or more happy people) so s>=s1+s2+s3.
Can someone please help why am I getting a WA on problem D on test-7. Link to my submission Thanks in advance :)
UPD- I got the mistake.
If anyone need Detail Explanation(not a video tutorial) of C Here
Can anyone explain the solution of E in tutorial? I see most of the solution use trisection search. Is the tutorial also use the trisection search? Forgive my terrible understanding of the code in tutorial.
In Problem A: It is said to print "4 different positive integers", but why one of those 4 positive integers can not be zero ('0')? Where is the range is mentioned? Please help me to understand the constraint. Thank you.
Because 0 is not positive? :|
Auto comment: topic has been updated by Karavaiev (previous revision, new revision, compare).
C was such a good problem even though I participated virtually and solved it 10 minutes after the contest. I did not read the question properly and missed the point that once the person becomes sad cannot become happy again.
It would have been better (easier) C if this was not the condition.
How stupid, I missed that point even it was in Bold.
WHAT SHOULD I DO NOT TO GET RATING IN CONTEST?
Solve it virtually.
hello, in problem B if I have n = 5 then the number must be 9 9 9 9 9
in binary : 1001 1001 1001 1001 1001
but after removing last 5 digits then it become
1001 1001 1001 100- ----
which makes it a 4 digit number, so making that 5 digit number I need to make it all 0s :
1001 1001 1001 1000 0000
but this doesn't the case.
Can anyone help me with that ?
How will the last digit be Zero. zero has a single digit representation in Binary.
okay but why should be 8 ?
could you elaborate a bit .
because we want a number with 4 bit binary representation. That way, our number will be maximum. We have only two options for this. 8 or 9.
why not nine ? I got that 0 cannot be the answer but not getting that how 8 (1000) fixes in the answer ? can you please explain the above example n = 5?
Why not nine? because 99...8 is smaller than 99...9 Read the problem again, They both give same answer unless n%4=0 for n=5
1001 1001 1001 1001 1001
Why not your logic?
1001 1001 1001 100,1 1001
You're gonna remove everything after the comma. So if you're gonna remove it anyway, you might as well make it as small as possible.
1001 1001 1001 100,0 1000
Notice that in this way, all digits are still 4 bit and it is also smaller than all 9's
I have an alternate solution for problem D . First transform the array b into a forest of directed trees with all edges away from the root by drawing edges from vertex x to b[x] when b[x]!=-1 (the nodes with b[x]= -1 will be the roots of the respective trees of the forest). Now, run a dfs from the root of each tree and for every node x, calculate a value say sum[x] such that sum[x] is equal to (sum of max(sum[z],0) for all children z of x) plus a[x]. The sum of sum[x] for all nodes of the forest is the required answer.
Also construct an auxiliary graph such that if sum[x]>0 draw a directed edge from x to b[x], otherwise draw an edge from b[x] to x(provided b[x]!=-1) . Sort the vertices in this graph topologically to get the permutation. 88585416
I solved C a bit differently. I used the name $$$liv$$$ instead of $$$p$$$ to indicate resident number of a node. For every node $$$v$$$, I maintained a range $$$[L_v, R_v]$$$ in which it's happiness index must lie. Thus, $$$L_v\leq h_v\leq R_v$$$ For a leaf, the range is $$$[-liv_v, liv_v]$$$.
Now, a node $$$v$$$ returns a different range for the residents of $$$v$$$ who started the journey from $$$par_v$$$. Notice that this range will be $$$[h_v, R_v]$$$, because if happiness in $$$v$$$ is $$$h_v$$$, then it was at least $$$h_v$$$ on its parent, with the possibility that it might be as high as $$$R_v$$$ ( Mind that one's mood gets bad only on the road AND the unhappy people never improve their mood ). Also, $$$R_v-h_v$$$ has to be even, by the definition of happiness index.
For an intermediate node $$$u$$$ and $$$v$$$ $$$\epsilon$$$ $$$children(u)$$$, $$$[L_u, R_u] = [-liv_u+\sum_{}L_v, liv_u+\sum_{}R_v]$$$. Because the lower limit for $$$u$$$ can be as low as "everyone's" lower limit, including itself. Same goes for the upper limit. Return the range $$$[h_u, R_u]$$$ with appropriate checking as mentioned above. if you get a valid range at the root, it's ok. Otherwise the machine has error and print NO.
My submission 88504884
For problem C, can someone provide a test case where my solution fails.
I have added appropriate comments to my code for better readability.
Please help!
I think your definition of $$$a$$$ and $$$b$$$ in $$$dfs2$$$ function is wrong. In $$$pto_v$$$, you have basically the number of people that have ever passed node $$$v$$$, right? Then what does
pto[p]+hp[p]
even mean?pto[p] is what you have said. hp[p] is the given happiness of the city (i.e given as input).
Even the tutorial has this formula. I cannot understand what is wrong with pto[p]+hp[p].
Can you please elucidate a bit more?
I see. Your code comment was misleading. $$$a$$$ and $$$b$$$ were $$$2$$$ times of happy and sad people respectively, though it will eventually be true a little later. Anyways, in that case, I'd want to ask you, what does your
dfs2
actually do? What I think is that it returns how many happy people have reached some node. In that case, you should return $$$a$$$, not $$$a+sum$$$ ! The $$$sum$$$ is needed to check any discrepancy at the children, but it shouldn't be added. In fact, I just submitted your code withreturn a;
indfs2
and got AC. Maybe you were "too lucky" to get past this many testcases.Yes, I forgot to mention that a and b are twice of happy and sad people respectively (usual stupidity that I do, sorry)
I was not able to enforce the necessary conditions in dfs1, so I wrote dfs2 to declutter my code.
Extremely grateful to you for going through my code and pointing the error. Now, I understand what was wrong with my code.
Thanks a lot again.
Help please Problem D https://codeforces.net/contest/1388/submission/88590473 checkler log is showing sequence have duplicates.
In the 'else' in the 'while', you need to lower the indegree of brr[ind] (not only inside the if, but also in the else).
Thank You very much. You have saved me a lot of time. Thanks again
Can somebody explain me if there were cycles in D, how to calculate the maximum value in the cycle after removing all non cyclic elements? (in O(n))
Congratulations to adedalic for amazing coordination of this round!
Please help me clarify my doubt:
In the second question (B) since we are asked to output the smallest value of x such that r is maximized after removing last n digits, so why the answer is not like this if n = 5 then x minimum x can be 99980 but the correct output is 99988 the value of k will be the same in both cases k = 100110011001100 and 99980 less than 99988 then why the answer is 99988. please explain to me if I am wrong or the question is cause i was stuck on second problem and then i lost hope and stopped attempting further.
What makes you think 0 can be represented as '0000' instead of straightforwardly as '0' !
but if we cannot use zero still then our answer can end with one like for n = 5, k is same for 99981 and 99988
No, if you use any other digit that 8 or 9 the resulting binary string will be shorter.
Dude, binary of 1 to 7 is three digits, its that straightforward, it can't be greater than 8 or 9.
No, only the numbers from 4 to 7 have 3 digits in binary.
Anyway, could you please explain the editorial for problem C ? I am having difficulty in following it.
https://codeforces.net/blog/entry/80828?#comment-672428
I explained it in a comment above. The comment right below mine has explanation too. See these 2 and it may answer all your questions.
Hi, Would anybody help me with Question C?
This is my submission. https://codeforces.net/contest/1388/submission/88520244
My way of approaching the problem is the same as the editorial except I calculate number of bad people instead of the number of good people.
My submission is wrong at the 27th input of the 3rd Test Case.
Thanks for the help.
Try this test case 1
The answer is "NO" Because the total sum of good people cities 2 and 3 is 12.
amount of good people in city 1 is 8.
the statement says that we can't increase the number of good people.
(srry if my english is not so good)
My submission is "YES". But I think the answer is "YES" also
Because happiness in city 1 is 14 and there is 14 people visit city 1. so number of good people = (14+14)/2 = 14 people. The number of good people leaving city 1 is 12 (14 — 2(people staying in city 1)). The total sum of good people in cities 2 and 3 is 12 which is (=) the number of good people leaving city 1. So the number of good people did not increase.
Do I have any misunderstanding on the problem? Thanks for your reply and kindness.
Try this test
Answer must be no. 3 bad and 2 good people at vertex 1. h[1] = -1, OK. 3 bad people will visit vertex 2. h[2] must be -3. Therefor answer is NO
ok Yes, that's it. I am wrong because I ignore all the vertex that has 1 connected vertex when I consider the 3rd Criteria. (All the leaf of the tree are of the size 1) But I forget that vertex 1 can be size of 1 too.
Thanks a lot for your help and kindness.
88635193 Can you explain why my code fails? my contest submission was -- 88482149, I know in the contest submission I did a calc error but the idea of my solution was the same, but after rectifying the calc error it's still showing wrong answer. Though it's written if there are multiple answers we can print any of them.
for condition a==44 you have used 13 as one of the number which is incorrect because 13 is itself a prime number.
Yes I thought about it but in the question says
Captain Flint guessed an integer n and asked you: can you represent it as the sum of 4 different positive integers where at least 3 of them should be nearly prime.
where they said 3 of them should be nearly prime rest can be a distinct integer apart from these 3. Maybe I got the question wrong but the above lines I directly copied from the question.
You submitted code of A in instead of B
It literally tells you "wrong answer Sum of numbers is not equal to n (test case 4)". Test case 4 is n=36.
88635193 my solution was 15 10 6 5. where 3 of them are nearly prime 15,10 and 6
Do you know what "Sum of numbers is not equal to n" means?
Edit: now I see that n=36 is fixed in that code; you should actually submit it to the correct problem.
first of all this is your code for 1st task and submission on 2nd task. you are seeing jury's answer as your answer.Your answer is the participant's output
hello, i am a newbie in coding and I didn't understand how problem D is connected to graphs. Can anyone tell me what's the idea/algorithm behind this question. Should I be knowing something before trying this question??
the values of b array were forming a chain(that is b was connected to the index in a and further the value of b in the new index was connected to some other index of a) and to solve such chaining question we can use graphs.
Could someone explain why does the following code for problem C gives WA ? I am not able to find any substantial difference between this code and the official solution's code.. In particular, it will be nice to have someone give me a test-case where my code fails. Also please do let me know if anything is unclear in my code; I will explain what I intend to do using that particular instruction.
}
Can someone explain me what's the difference in the logic of my submission please? I have been trying to figure it out for a while but am not able to find any difference, so could someone tell me please ? In particular, my code seems to fail on the 27th test case of the 3rd test, but I am unable to view this, so could someone at least tell me what this test case is ?
Thanks in advance!
UPD: I found the mistake — a really stupid one. Instead of keeping sum <= good[v], I kept sum<= peo[v], a big overlook!
Sorry for pestering anyone who intended to help me.
https://codeforces.net/contest/1388/submission/88842110 WHATS WRONg WITH ThiS?
how can i find answers of all the proplems ?(sorry if my English is bad)
if the editorial is not good enough you can check submissions by other competitors
I think in the editorial for problem B it should read "at most 4*p-3" instead of "at least 4*p-3"
"at least" is correct.
My reasoning was incorrect, you are right. Thanks a lot, nice problem.
For problem C, shouldn't this give a wrong answer?? I didn't check if number of people in good mood in a city are non-negative.
What's wrong with my solution? I used BFS two times.
1) Operate on the nodes that are +ve or become +ve while traversal, from top to bottom. Mark them.
2) Operate on the remaining negative nodes. From bottom to top
can anyone check and help me understand why memory limit is exceeded in my solution for problem C 89311627
Damn, i forgot to clear the global vector
yeap )
In 1388C — Uncle Bogdan and Country Happiness, consider the 3rd condition:
gto1+gto2+…+gtok ≤ gv, where to1, to2, …, tok are the cities where the resident can move out of the city v on the way home.
Shouldn't we compare gto1+gto2+…+gtok with number of happy (in good mood) people leaving the city v instead of comparing gto1+gto2+…+gtok with gv (number of people in a good mood who visit the city v = number of people in good mood passing through city v + number of people in a good mood who live in city v), to ensure no one becomes happy during the journey.
Nice problems except for the long essays here
I have solved problem D using the concept of topological sort order in DAG. You may have a look at the tutorial that I have written for this problem in my blog, Link.
Good job )
Problem D: 279808093 — is causing a WA7 due to wrong output format Unexpected end of file — int32 expected.
It worked fine for larger inputs in Tests 4, 5 and 6. But for some reason fails on 7, could someone help me debug the code?