Codeforces Round 929 (Div. 3) Editorial

1933A - Turtle Puzzle: Rearrange and Negate

Idea: snowysecret, prepared: snowysecret

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += abs(arr[i]);
        }
        cout << sum << endl;
    }
    return 0;
}

1933B - Turtle Math: Fast Three Task

Idea: snowysecret, prepared: snowysecret, erniepsycholone

Tutorial

Solution

#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int k;
        cin>>k;
        int ACC=0;
        bool hv=false;
        for(int i=0;i<k;i++){
            int x;
            cin>>x;
            ACC+=x;
	    if(x%3==1){
		hv=true;
	    }
        }
        if(ACC%3==0){
            cout<<0<<endl;
        }else if(ACC%3==2){
            cout<<1<<endl;
        }else{
            if(hv==true){
                cout<<1<<endl;
            }else{
                cout<<2<<endl;
            }
        }
    }
}

1933C - Turtle Fingers: Count the Values of k

Idea: dbsbs, prepared: dbsbs, snowysecret

Tutorial

Solution

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve(int tc){
    int a, b, l;
    cin >> a >> b >> l;
    set<int> ans;
    for(int i = 0; i <= 34; ++i){
        int x = l;
        bool fail = false;
        for(int _ = 0; _ < i; ++_){
            if(x % a){
                fail = true;
                break;
            }
            x /= a;
        }
        if(fail) break;
        while(true){
            ans.insert(x);
            if(x % b) break;
            x /= b;
        }
    }
    cout << ans.size();
}
 
bool multi = true;
 
signed main() {
    int t = 1;
    if (multi)cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}

1933D - Turtle Tenacity: Continual Mods

Idea: snowysecret, erniepsycholone, prepared: snowysecret

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int a[n];
        for(int i=0; i<n; i++) cin >> a[i];
        sort(a, a + n);
        if(a[0] != a[1]) {
            cout << "YES\n";
        }
        else {
            bool PASS = 0;
            for(int i=1; i<n; i++) {
                if(a[i] % a[0] != 0) PASS = 1;
            }
            if(PASS) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

1933E - Turtle vs. Rabbit Race: Optimal Trainings

Idea: snowysecret, prepared: snowysecret

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
#define int long long 
#define double long double

void solve(int tc) {
  int n;
  cin >> n;
  int a[n + 1];
  for(int i = 1; i <= n; i++) cin >> a[i];
  int ps[n + 1];
  ps[0] = 0;
  for(int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i];
  int q;
  cin >> q;
  while(q--) {
    int l, u;
    cin >> l >> u;
    int lb = l, rb = n;
    while(lb < rb) {
      int mid = (lb + rb + 1) >> 1;
      if(ps[mid] - ps[l - 1] <= u) lb = mid;
      else rb = mid - 1;
    }
    int maxu = -1e18, optid;
    for(int i = max(l, lb - 2); i <= min(n, lb + 2); i++) {
      int t = ps[i] - ps[l - 1];
      int ut = (u + (u - t + 1)) * t / 2;
      if(ut > maxu) {
        maxu = ut;
        optid = i;
      }
    }
    cout << optid << " ";
  }
}

signed main() {
  int t = 1; cin >> t;
  for(int i = 1; i <= t; i++){
    solve(i);
    cout << "\n";
  }
}

1933F - Turtle Mission: Robot and the Earthquake

Idea: erniepsycholone, prepared: erniepsycholone

Hint

Tutorial

Solution

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int t;
    cin >> t;
    while (t--){
        int n, m;
    	cin >> n >> m;
    	bool a[n][m + 1];
    	for (int i = 0; i < n; i++) {
    		for (int j = 1; j <= m; j++) {
    			cin >> a[i][j];
    		}
    	}
    	int dp[n][m + 1];
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j <= m; j++) {
    			dp[i][j] = INT_MAX;
    		}
    	}
    	dp[0][1] = 0;
    	for (int i = 1; i <= m; i++) {
    		for (int j = 0; j < n; j++) {
    			if (a[j][i]){
    			    continue;
    			}
    			dp[j][i] = min(dp[j][i], dp[(j - 1 + n) % n][i - 1] + 1); 
    		}
    		for (int j = 0; j < 3 * n; j++) {
    			if (a[j % n][i] || a[(j - 1 + n) % n][i]){
    			    continue;
    			}
    			dp[j % n][i] = min(dp[j % n][i], dp[(j - 2 + n) % n][i] + 1);
    		}
    	}
    	int ans = INT_MAX;
    	for (int i = 0; i < n; i++) {
    		if (dp[i][m] == INT_MAX){
    		    continue;
    		}
    		int npos = ((n - 1) + dp[i][m]) % n;
    		if (npos < i) npos += n;
    		int cur = dp[i][m] + min(npos - i, n - (npos - i));
    		ans = min(ans, cur);
    	}
    	if(ans == INT_MAX){
    	    cout << -1 << endl;
    	}else{
    	    cout << ans << endl;
    	}
    }
}

1933G - Turtle Magic: Royal Turtle Shell Pattern

Idea: snowysecret, jerryliuhkg, prepared: snowysecret

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;

void solve(int tc) { 
  int n, m, q;
  cin >> n >> m >> q;
  bool b[8] = {1, 1, 1, 1, 1, 1, 1, 1};
  int ans = 8;
  cout << ans << '\n';
  while(q--) {
    int r, c;
    cin >> r >> c;
    string shape;
    cin >> shape;
    if((r + (c+1) / 2) % 2) {
      b[0] &= (shape == "circle");
      b[1] &= (shape == "square");
    }
    else {
      b[0] &= (shape == "square");
      b[1] &= (shape == "circle");
    }
    if((r + c / 2) % 2) {
      b[2] &= (shape == "circle");
      b[3] &= (shape == "square");
    }
    else {
      b[2] &= (shape == "square");
      b[3] &= (shape == "circle");
    }

    if((c + (r+1) / 2) % 2) {
      b[4] &= (shape == "circle");
      b[5] &= (shape == "square");
    }
    else {
      b[4] &= (shape == "square");
      b[5] &= (shape == "circle");
    }
    if((c + r / 2) % 2) {
      b[6] &= (shape == "circle");
      b[7] &= (shape == "square");
    }
    else {
      b[6] &= (shape == "square");
      b[7] &= (shape == "circle");
    }
    ans = 0;
    for(int i = 0; i < 8; i++) ans += b[i];
    cout << ans << '\n';
  }
}

int main() {
  int t; 
  cin >> t;
  for(int i = 1; i <= t; i++) solve(i);
}

Hope the contest was in some way helpful in improving your skills, and that you all had fun!

“If you only do what you can do, you will never be more than you are now.” – Master Oogway

Комментарии (18)

Показать архивные | Написать комментарий?

Bit_Slayer

2 года назад, скрыть # |

This Round was really amazing. I really enjoyed this round. The problems are very good.

→ Ответить

Asimo_robot

For the problem F tutorial (spoiler alert): I don't understand this part: "Finally, choose the best among all n tiles after waiting for the endpoint to cycle back." can someone explain it to me?

snowysecret

2 года назад, скрыть # ^ |

Let $$$b_i$$$ be the minimum time needed to reach cell $$$(i, m-2)$$$ in the transformed problem. Then, it takes $$$b_i + 1$$$ time to reach cell $$$(i, m-1)$$$ in the transformed problem.

The transformation we did is to imagine the robot moving down instead of the rocks moving up. Therefore in reality it takes $$$b_i + 1$$$ time to reach cell $$$(c_i, m-1)$$$ where $$$c_i = (i-(b_i+1)) \bmod n$$$. Hence, to reach $$$(n-1, m-1)$$$ we really need $$$b_i + 1 + \min(c_i + 1, n - 1 - c_i)$$$ time.

Therefore the answer is just $$$\min_{i=0}^{n-1} b_i + 1 + \min(c_i + 1, n - 1 - c_i)$$$ where $$$b$$$ and $$$c$$$ arrays are defined above.

daksh_02

I have seen solution for same problem via simple bfs to reach to end position how come that solution works scratching my head on that for a while

Akeryep

For F,I dont understand why the row update 3 times like"for(int j=0;j<3*n;j++)".I try using 2 times and get WA,3 times AC.HOW?

erniepsycholone

← Rev. 3 →

As RT can go from $$$(x,y)$$$ to $$$((x+2) \text{ mod } n,y)$$$, if x=0 currently, and $$$n \text{ mod } 2=1$$$, it would require the 2 times you mentioned. However, if $$$x!=0$$$, we need to loop $$$3$$$ times to run an entire cycle throughout a column. An example would be if RT is at $$$(3,0)$$$, with $$$n=5$$$, the following operations would be needed to run through column $$$0$$$:

$$$(3,0)$$$ --> $$$(0,0)$$$ --> $$$(2,0)$$$ --> $$$(4,0)$$$ --> $$$(1,0)$$$ --> $$$(3,0)$$$

norising

Hello,I still don't understand.I used"for(int i=0;i<200*n;i++)for(int j=0;j<m;j++)" and WA on test 36. Why we should run m before n?my submission

observe the update exprssion,you will find out that it need m first to ensure the correctness

I get your point,thanks!

sai_kamal

22 месяца назад, скрыть # ^ |

Hi, but why should it complete a cycle? like in 2 loops it is able to reach till (1,0), why should it get back to (3,0)? (my assumption is that the optimal path to reach is starting at (3,0) so going a loop back to (3,0) seems redundant)

_sazan4ek_

Thank you for the great round!) I've finally got the pupil)

Yash_Tulsani

I tried to solve problem E using ternary search but it gave TLE on 8th test case (https://mirror.codeforces.com/contest/1933/submission/249501917), can anyone share the ternary search solution for problem E.

0mar

← Rev. 2 →

My solution is quite messy but here it is: https://mirror.codeforces.com/contest/1933/submission/249548927 If you need me to explain any part of it I can.

A much cleaner solution I just found is this:

https://mirror.codeforces.com/contest/1933/submission/248605914

thinkaboutit

In E, they used the following formula to calculate the first t terms of an arithmetic series: ~~~~~ int ut = (u + (u — t + 1)) * t / 2; ~~~~~ But it is wrong because u-t+1 might be negative, and in that case, the standard formula doesn't work, but why does it pass the test cases?