Codeforces Round 637 Div 2

27

If you don’t mind, could you share your implementation? I had the same idea, But wasn’t sure how to code it.

28

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
29

@everule1 why are your codechef ID and codechef discuss names different?
One is Aditya Jain and one is Rashmi Jain

30

How many did you solve? I solved only 3🙃.

31

I solved up to div. 1 C (and almost D) = 5 in div. 2

1 Like
32

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
33

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
34

i just used
if(a[i+1]-a[i] > 1)
possible = false;

it passed pretests but system testing is due so not 100% sure.

35

@everule1 ??
Is this your ALT account?

36

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.

37

Intuitively, that seems right. I think the general idea behind the proof for it is, when you place a[i], either a[i + 1] must be the next number you place, or it would have been impossible to place a[i] in the first place.

Thinking about this now, I realize that efficiently simulating the algorithm (which is what I did) is super lame and gives zero understanding about what turns out to be a structurally simple problem.

1 Like
38

first i was also thinking of following the algo properly, but, then i realise its pattern and gave it a shot and it passed pretests :smiley: hope same for system testing.

39

Will a fast implementation of dijkstra work for E?
There are 10^4 safety lines, 10^3 points in time (0 to g, skipping g + 1 to r) . The number of states would be the product (n = 10^7). log(n) ~ 24. So n log(n) would be 2.4 * 10^8. Considering that not all states are explored, I think it will get a bit lower. Also, we can use bitset for checking visited states fast. And I added -O3 flag in a macro. Hope I get AC when CF goes up lol.

40

I don’t think that’s correct
Try this
5
3 4 5 1 2
This should be possible

41

Same.

42

It’s not abs(a[i + 1] - a[i]), it’s just a[i + 1] - a[i]. So the condition is never met for your case.

1 Like
43

A very simple solution.

Keep adding to a pointer until the number differs by 1. Then sort the array from the start of the pointer to this end.

In the end, check if the array is sorted in descending order.

#include <bits/stdc++.h>
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
 
const ll mod  = 1e9+7;
const db eps  = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf = LLONG_MAX;
 
#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl
 
void solve()
{
        ll n;
        cin >> n;
        
        vector<ll> v(n);
        for(ll i=0 ; i<n ; ++i) cin >> v[i]; 
 
        for(ll i=0 ; i<n ; ++i)
        {
            ll start = i;
            while( v[i+1] == v[i]+1 )
            {
                ++i;
            }
 
            sort(v.begin()+start,v.begin()+i+1,greater<ll> ());        
        } 
 
        
        ll i=1;
        for(auto it = v.end()-1 ; it>= v.begin() ; it--,i++)
        {
             if(*it!=i) 
             {
                cout << "No" << endl;
                return;
             }
        }
        cout << "Yes" << endl;
                return;
 
}
 
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
    #endif
 
    ll t;
    cin >> t;
 
    while(t--)
    {
        solve();
    }
 
    return 0;
}
44

Oh I see now
Nice solution!
I guess my solution was an overkill :joy:

45

yeah it is possible my code is passing.

46

Yeah, it worked . After the contest I thought that there must be some more condition as mentioned above by @sayan_244 and @everule1 . Really liked your approach @kritagya_yash