Makaty's blog

Gym solutions
By Makaty, history, 6 months ago, In English

Hello, since gym doesn't allow to see others solutions could someone help with this problem:

i have tried this solution but got WA

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Makaty (previous revision, new revision, compare).

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

instructions unclear: solution page not able to be viewed please send your code in a code block instead

→ Reply
  • »
    »
    5 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    hello, sorry for that :), here is my code:

    #include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define iinf INT_MAX
#define pi pair<int,int>
#define endl '\n'
#define ld long double
#define linf LONG_LONG_MAX
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T>
using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
/*
// find_by_order, order_of_key
*/
void fastio(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
void file(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);
#endif
}
 
#define int ll
#define mod (int)(1e9+7)
int n,k;
int t[300007];
int dp[300007];
int best(int cur) {
    if(cur == n) return 0;
    int &ret = dp[cur];
    if(ret != -1) return ret;
    ret = 1 + best(cur+1);
    if(t[cur] != -1) {
        for(int i = cur+1; i<=t[cur]; i++) {
            ret = min(ret,best(i));
        }
 
    }
    return ret;
}
void solve1() {
 
 
 
}
 
 
void solve() {
    cin >> n >> k;
    memset(t, -1, sizeof(t));
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i<k; i++) {
        int a,b; cin >> a >> b;
        t[a] = b;
    }
    cout << best(1) << endl;
 
 
 
}
 
signed main() {
 
    file();
    fastio();
    int t = 1;
    cin >> t;
    while(t--) solve();
 
}
    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      2 declarations of $$$t$$$? One as an array and another as an input integer? Looks more like Compile Error than WA to me...

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

        yeah i see, but unfortunately it wasn't compile error, when i used t in main the compiler took the block scope one instead of the global var so it worked

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

You actually don't need DP to solve this problem.

Think of it like this, Bus Stops means that you have segments in the form $$$(li, ri)$$$. In these segments you don't need to walk.

This means that if consecutive segments (let's say $$$(li, ri)$$$ & $$$(lj, rj)$$$ assuming $$$ri<=lj$$$ and $$$rj>=ri$$$) are intersecting you don't need to walk in the segment $$$(li, rj)$$$ at all.

So now this problem becomes for the distance (1, n) how many places have no segments. That is the answer. For merging segments you can sort and merge, I think it's pretty well known.

code
→ Reply