I also got WA in div2 A . Could not find any negative case. Can someone explain their approach for div2 A please?
void solve(){
int n, a, b, c, d;
cin>>n>>a>>b>>c>>d;
int maxgrain=n*(a+b);
int mingrain=n*(a-b);
int maxval=c+d;
int minval=c-d;
if(maxgrain < minval || mingrain>maxval){
cout<<"No\n";
}
else{
cout<<"Yes\n";
}
}
Maybe this will help/
1 Like
Yup the solution is right I get it. But could you mind suggesting test case where mine code fails. Thanks.
On the new test case? It’s yes. I think you misunderstood the question. You have to find if there is an intersection between the segments n(a-b), n(a+b) and c-d, c+d
1 Like
Your issue is, if both c - d and c + d are between x and y, there will be a valid answer, but you won’t find it.
1 Like
Well you checked for the boundary conditions but what about when (a - b) * n < c - d and (a + b) * n > c + d ,
you see that clearly according to your condition it would fail.
1 Like
Did you solve D? I had no clue how to approach without O(nk|d||s|\log{nk}) time complexity. I did precompute the distances between all binary strings.
Let dp[i][j] be the highest digit you can get at position i with j moves having been made. Then you can construct the string with a parent array. O(10 \cdot nk) in total.
edit: For this to work, you have to reverse the initial order of the strings.
1 Like
If you don’t mind, could you share your implementation? I had the same idea, But wasn’t sure how to code it.
Well, codeforces is down (and I don’t save code locally), but I can give the basic idea.
initialize dp to 0, par to 0
precompute distances, call the cost to convert string i to digit j cost[i][j]
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
if (dp[i][j] != 0) {
for (int nxt = 0; nxt < 10; nxt++) {
int next_cost = j + cost[i][nxt];
if (next_cost <= k) {
if (dp[i + 1][next_cost] < nxt + 1) {
dp[i + 1][next_cost] = nxt + 1;
par[i + 1][next_cost] = j;
}
}
}
}
}
}
if (dp[n][k] == 0) {
cout << "-1\n";
} else {
string res = "";
int focus = k;
for (int i = n; i > 0; i--) {
res += (char)('0' + dp[i][focus] - 1);
focus = par[i][focus];
}
cout << res << '\n';
}
there are probably typos
edit: this is incomplete, but somehow I managed to accidentally tab to the “Reply” button and hit enter.
edit 2: check if cost[i][nxt] == -1 before updating future dp, but I’m too lazy to re-tab everything
edit 3: if you want, I can share E too
2 Likes
@everule1 why are your codechef ID and codechef discuss names different?
One is Aditya Jain and one is Rashmi Jain
How many did you solve? I solved only 3🙃.
I solved up to div. 1 C (and almost D) = 5 in div. 2
1 Like
Wow. I guess there’s a quite a bit of work left to reach orange. In E, were you supposed to find all pairs of m that can be reached in exactly time g, and then use a BFS?
Edit: Now that I think of it, there will be too many edges. I just glanced at the problem before.
1 Like
BFS isn’t optimal, because there’s distance involved (and Dijkstra is probably too slow). However, you can group times by the number of g+r “cycles” and have a state like (island, time since last red) = number of red/green cycles elapsed, then your goal is to get to n in the minimum number of cycles for any given state. This you can do with 0-1 BFS (very similar to regular BFS, but with a deque).
Anyway, “A great discussion involves many voices and perspectives. Can I get anybody else involved?”
edit: a quick div1 ABC is red-level, so you might not be as far off as you think
1 Like
i just used
if(a[i+1]-a[i] > 1)
possible = false;
it passed pretests but system testing is due so not 100% sure.
No I do not have alt accounts. I’m 16 so I’m using my mom’s laptop, which is probably how her name accidently went into my discuss profile. Probably autofill.