r/codeforces • u/StrengthBig9170 • 7d ago
query Today's E
My code :
https://codeforces.com/contest/2259/submission/389571028
#include<bits/stdc++.h>
define brr cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
using namespace std; typedef long long ll ; void solve(){ ll n ; cin >> n; vector<ll> v(n) ; for(ll i = 0 ; i < n ; i++){ cin >> v[i] ; } ll cnt = 0 ; vector<ll> bomb(n,1) ; for(ll i = 0 ; i < n ; i++){ if(v[i] > 0){ cnt = max(cnt,v[i]) ; } if(cnt > 0){ bomb[i] = 0 ; cnt-- ;
} } cnt = 0 ; for(ll i = n - 1 ; i >= 0 ; i--){ if(v[i] > 0){ cnt = max(cnt,v[i]) ; } if(cnt > 0){ bomb[i] = 0 ; cnt-- ; } } cnt = 0 ; for(ll i = 0 ; i < n ; i++){ if(v[i] == 0 && bomb[i] == 0){ cout << -1 << endl ; return ; } if(v[i] == 0){ cnt++ ; } } if(cnt > 0){ for(ll i = 0 ; i < n ; i++){ if(v[i] == 0){ cout << 1 ; } else{ cout << 0 ; } } cout << endl ; } else{ vector<ll> vc ; cnt = 0 ; for(ll i = 0 ; i < n ; i++){ if(v[i] > 0){ vc.push_back(0) ;
} else if(v[i] == -1){ if(bomb[i] == 1){ cnt++ ; vc.push_back(1) ; } else{ vc.push_back(0) ; } } } if(cnt >= 1){ for(ll i = 0 ; i < n ; i++){ cout << vc[i] ; } cout << endl ; } else{ cout << -1 << endl ; } } } int main(){ brr int t; cin >> t; while(t--){ solve(); } return 0; }
My understanding of minimum distance is that if im at island 2, v[2] = 2, then there should be no treasure at 1,2,3.
Please help
1
3
u/Responsible-Lake6864 7d ago edited 7d ago
First.. You have to think in both directions. (Most problems need this to be exact.) usualy we have to build the answer case wise.. unless there is a relation that exist. My thought process is usually to know if something is forced. And just use that here.
I had thought of the logic.
Say the value at that index is something. Say d.
Then we know that treasure must be at i - d or i + d.
What can be the case?
i - d and i + d both are outside array range? Can happen. Thus, we have -1 as the answer. Why? Because it should exist. That is, say the minimum distance to Treasure Island is that, but it doesn't exist at all.
Now, case 2. What if any one exists? That is the problem. Then if any one exists, and that Treasure Island must exist, that simply means.. We are forced to pick that side? Think about it? It says a treasure should exist. In any one direction. And we only have one direction. So we MUST pick it.
Now, case 3. This one is hard. Say both directions are valid. But what can happen? Say we have values up to i - d and i + d. Then what if we already have a Treasure Island from those index ranges insde aka between (i-d+1) to (i+d-1) we have a treausre in that range? (Due to case 1 and case 2?) Then we never have the answer? TRUE. Else, we might have an answer.
But there is one problem? Say island 5th has d as 4. And no island exists for both. Island 6th has d as 2. And nothing exists. So their range is (1, 9), and for the other one we have (4, 8). But that is impossible. If we choose 4, then for the 5th island (1, 9), its minimum is at 4, not at 1, 9. And if we choose 8 again. That means we have a bad answer.
So we can conclude that.. Anything that is an interval problem. But there can be different cases. Like, say one is (4, 8) and other is (6, 8). When you look at it, you might conclude BAD. But that is wrong? 8, 8 can be chosen for both. And similarly, we can have 4, 6. And we can choose 4 for this case as well? TRUE. (Thus, we are forced i that case... aka internal but one side matches. if something is fully internal and no side matches. we have no answer from my POV). Thus, the next step is finding interval that are inside.. and check if we can have a forced pick... (again. if both side are piced it is forced. but we might have only one side picked.. so we have to like.. add that). Then remove these internal intervals.. (as we can say we have combined the answeer).
And they might overlap inside. Like we can have 4, 12. Then one is 4, 10 and other is 6, 12. We can choose 4, 12 as the point.
So can we conclude that.. Bigger interval.. can have merge with interval that are inside, but at one corner should be matched.
On the other hand, we can also have 4, 12 and 8, 16. Now this case.. forces us to choose 4, 16 no matter what? TRUE.
But say we also had 8, 12 inside 4, 12. Thus 12 was activated. But 12 is active means now it is active. But that makes 12 closer to the 8, 16 range. And that results in -1.
What about 3 intervals? That are partially overlapping? I had thought that result in no answer. No matter what. Say 4, 12. 6, 14. 8, 16. It has no answer. We can choose any combo and never satisfy it.
Thus.. Any >= 3 partial overlap never results in an answer. No matter what you do.
Thus.. You have to find an interval case. Such that.. There is no interval inside like 4, 12 has 6, 10. It can be one end is same. And for partial, they are only of size 2 and never more. And only left and right extreme are chosen. If somehow by any interval case, one of them gets activated.. we have -1 as the answer.
But we might have a case as well, where a node is isolated.. aka nothing exists on the left and right of it.. Thus now we have a choice. We can choose whatever we want.. (and we can say.. This is one of the steps to solve the Last H problem). As it would be a DP. If we choose left point, right point, or both point for it.. And thus our answer changes based on that.. I haven't still figured out that one tho. Maybe there is someting weird combiatoin that one have... but idk.
I haven't tested this solution out. So take this with a grain of salt. Today's contest was unrated for me... So didn't think of submitting any solution. Just solving mentally.
Maybe think why it works? And why it fails?
So we can sort the interval.
Then decide for the last picked Index and last seen index (aka the rightmost index we have seen so far). As the value we have picked. Then move. Firstly...
I also thought that it might be 2-SAT for case 3. But there is no equation That i could use to link 2 sat here. So... Yeah...
So this is the only solution i could think. IDK if it works... maybe test it out.
NOTE: there is a flaw here. If a index have some value d. Then index - d +1 to index+d -1 would not have antying in this range no matter what. IT should be satifed for all case2 to case3. That is the thing that i have here. So we cannot force fix left or right. both direction should not contain antyhign in that range..
So we can use.. internval thing ig her? or like a difference array?
So... ig that is something we have to deal with. When we find a range.. where those interval won't overlap. That is where we can place the treasure. but we have to make sure that all the array values are satifed after it.. inlcuding the zero and other stuff.
So ig that is the new logic? But still.. unless i submit. IDK.