Записи в блоге

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

We hope you liked the problems! We apologize for the weak pretests for A and B -- that was a major oversight on our part. Hopefully you were still able to enjoy the contest regardless :)

We have to apologize to antontrygubO_o a bit here -- the rejection count mentioned in the editorial for Codeforces Round 655 (Div. 2) actually also included this round, as the problems from that round and problems A through G in this round were created together. We did have one more problem rejected after that round happened, bringing up the total to 73. For reference, here are the overall rejection counts for each problem:

Rejection Counts

Without further ado, here are the tutorials for each of the problems:

Tutorial is loading...

Solution (Kotlin) by golions

import java.io.*
import java.util.*
import kotlin.math.*

fun main(){
	val f = BufferedReader(InputStreamReader(System.`in`))

	for(q in 1..f.readLine().toInt()){
		val n = f.readLine().toInt()
		val array = f.readLine().split(" ").map{it.toInt()}.toHashSet()

		if(array.size == 1){
			println(n)
		} else {
			println(1)
		}
	}
}

Solution (Java) by MagentaCobra

/*
Omkar orz
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class ModelPasswordA
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int T = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         while(T-->0)
         {
            int N = Integer.parseInt(infile.readLine());
            int[] arr = new int[N];
            st = new StringTokenizer(infile.readLine());
            for(int i=0; i < N; i++)
               arr[i] = Integer.parseInt(st.nextToken());
            int res = N;
            for(int i=1; i < N; i++)
               if(arr[i] != arr[i-1])
                  res = 1;
            sb.append(res+"\n");
         }
         System.out.print(sb);
      }
   }

Solution (C++) by hugopm

#include <bits/stdc++.h>
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using ll = long long;

void solve() {
	int n; cin >> n;
	vector<int> vec(n);
	for (int i = 0; i < n; ++i) {
		cin >> vec[i];
	}
	sort(all(vec));
	if (vec.front() == vec.back()) cout << n << "\n";
	else cout << "1\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int nbTests;
	cin >> nbTests;
	for (int iTest = 0; iTest < nbTests; ++iTest) {
		solve();
	}
}

Idea: MagentaCobra and qlf9

Preparation: MagentaCobra

Tutorial is loading...

Solution (Kotlin) by Tlatoani

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val jin = BufferedReader(InputStreamReader(System.`in`))
    val out = StringBuilder()
    for (c in 1..jin.readLine().toInt()) {
        val line = jin.readLine().split(" ")
        val n = line[0].toInt()
        val k = line[1].last().toString().toInt() % 2
        val array = jin.readLine().split(" ").map { it.toLong() }.toLongArray()
        var m = array.max()!!
        for (j in 0 until n) {
            array[j] = m - array[j]
        }
        if (k == 0) {
            m = array.max()!!
            for (j in 0 until n) {
                array[j] = m - array[j]
            }
        }
        out.appendln(array.joinToString(" "))
    }
    print(out)
}

Solution (Java) by MagentaCobra

//Omkar, Holy Light
import java.util.*;
import java.io.*;
import java.math.*;

   public class ModelB
   {
      public static void main(String omkar[]) throws Exception
      {
         //query based
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int T = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         while(T-->0)
         {
            st = new StringTokenizer(infile.readLine());
            int N = Integer.parseInt(st.nextToken());
            long K = Long.parseLong(st.nextToken())%2;
            if(K == 0)  K = 2;
            int[] arr = new int[N];
            st = new StringTokenizer(infile.readLine());
            for(int i=0; i < N; i++)
               arr[i] = Integer.parseInt(st.nextToken());
            for(int turns=0; turns < K; turns++)
            {
               int max = arr[0];
               for(int x: arr)
                  max = Math.max(max, x);
               for(int i=0; i < N; i++)
                  arr[i] = max-arr[i];
            }
            for(int i=0; i < N; i++)
            {
               sb.append(arr[i]);
               if(i+1 < N)
                  sb.append(" ");
            }
            sb.append("\n");
         }
         System.out.print(sb);
      }
   }

Solution (C++) by tfg

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int t;
	std::cin >> t;
	while(t--) {
		int n;
		long long k;
		std::cin >> n >> k;
		std::vector<int> a(n);
		for(int i = 0; i < n; i++) {
			std::cin >> a[i];
		}
		if(k > 1) {
			k = 2 + k % 2;
		}
		while(k--) {
			int mx = -1000000000;
			for(int i = 0; i < n; i++) {
				mx = std::max(mx, a[i]);
			}
			for(int i = 0; i < n; i++) {
				a[i] = mx - a[i];
			}
		}
		for(int i = 0; i < n; i++) {
			std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
		}
	}
}

Idea: MagentaCobra

Preparation: MagentaCobra

Tutorial is loading...

Solution (Kotlin) by Tlatoani

import kotlin.math.max

fun main() {
    for (c in 1..readLine()!!.toInt()) {
        val n = readLine()!!.toInt()
        val hs = readLine()!!.split(" ").map { it.toLong() }
        var answer = 0L
        for (j in 1 until n) {
            answer += max(0L, hs[j - 1] - hs[j])
        }
        println(answer)
    }
}

Solution (Java) by qlf9

import java.util.*;
import java.io.*;

public class OmkarAndWaterslide {
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(f.readLine());
        while(t-->0){
            int n = Integer.parseInt(f.readLine());
            long[] arr = new long[n];
            StringTokenizer st = new StringTokenizer(f.readLine());
            for(int i = 0; i < n; i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }
            long ans = 0;
            for(int i = 0; i < n-1; i++){
                ans+=Math.max(0, arr[i]-arr[i+1]);
            }
            out.println(ans);
        }
        out.close();
    }
}

Solution (C++) by tfg

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int t;
	std::cin >> t;
	while(t--) {
		int n;
		std::cin >> n;
		long long last = 0;
		long long ans = 0;
		while(n--) {
			long long x;
			std::cin >> x;
			x += ans;
			if(x >= last) {
				last = x;
			} else {
				ans += last &mdash; x;
			}
		}
		std::cout << ans << '\n';
	}
}

Idea: qlf9

Preparation: qlf9

Tutorial is loading...

Solution (Kotlin) by Tlatoani

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val jin = BufferedReader(InputStreamReader(System.`in`))
    val out = StringBuilder()
    for (c in 1..jin.readLine().toInt()) {
        val n = jin.readLine().toInt()
        val s = jin.readLine()
        if (s.all { it == s[0] }) {
            out.appendln((n + 2) / 3)
        } else {
            var k = 0
            while (s[k] == s[0]) {
                k++
            }
            var answer = 0
            var curr = 0
            var chara = s[k]
            for (j in k until k + n) {
                if (s[j % n] == chara) {
                    curr++
                } else {
                    answer += curr / 3
                    curr = 1
                    chara = s[j % n]
                }
            }
            answer += curr / 3
            out.appendln(answer)
        }
    }
    print(out)
}

Solution (Java) by qlf9

import java.util.*;
import java.io.*;

public class OmkarAndBedWars {
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(f.readLine());
        while(t-->0){
            int n = Integer.parseInt(f.readLine());
            String str = f.readLine();
            boolean same = true;
            for(int i = 1; i < n; i++){
                if(str.charAt(i) != str.charAt(0)){
                    same = false;
                    break;
                }
            }
            if(same){
                out.println((n+2)/3);
                continue;
            }
            ArrayList<Integer> count = new ArrayList<Integer>();
            int last = 0;
            int cnt = 1;
            for(int i = 1; i < n; i++){
                if(str.charAt(i) == str.charAt(last)){
                    cnt++;
                }else{
                    count.add(cnt);
                    last = i;
                    cnt = 1;
                }
            }
            if(str.charAt(n-1) == str.charAt(0)){
                count.set(0, count.get(0)+cnt);
            }else{
                count.add(cnt);
            }
            int sum = 0;
            for(int i: count) sum+=(i/3);
            out.println(sum);

        }
        out.close();
    }

}

Solution (C++) by Ari

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

void solve() {
    int n, ans = 0;
    cin >> n;
    string s;
    cin >> s;
    int cnt = 0;
    while(s.size() && s[0] == s.back()) {
        cnt++;
        s.pop_back();
    }
    if(s.empty()) {
        if(cnt <= 2) {
            cout << "0\n";
            return;
        }
        if(cnt == 3) {
            cout << "1\n";
            return;
        }
        cout << (cnt + 2) / 3 << '\n';
        return;
    }
    s.push_back('$');
    for(int i = 0; i + 1 < s.size(); i++) {
        cnt++;
        if(s[i] != s[i + 1]) {
            ans += cnt / 3;
            cnt = 0;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--)
        solve();
}

Idea: Tlatoani

Preparation: Tlatoani

Tutorial is loading...

Solution (Kotlin) by Tlatoani

fun main() {
    val n = readLine()!!.toInt()
    for (x in 1..n) {
        for (y in 1..n) {
            if (x % 2 == 0) {
                print(1L shl (x + y))
            } else {
                print(0)
            }
            print(" ")
        }
        println()
    }
    val q = readLine()!!.toInt()
    for (j in 1..q) {
        val k = readLine()!!.toLong()
        var x = 1
        var y = 1
        print("1 1 ")
        for (e in 3..2 * n) {
            if ((x % 2 == 0) == (((k shr e) % 2L) == 1L)) {
                y++
            } else {
                x++
            }
            print("$x $y ")
        }
        println()
    }
}

Solution (Java) by golions

//make sure to make new file!
import java.io.*;
import java.util.*;

public class DuckSolution{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      int n = Integer.parseInt(f.readLine());
      
      long[][] board = new long[n][n];
      board[0][0] = 0L;
      board[n-1][n-1] = 0L;
      
      for(int k = 0; k < n; k++){
         for(int j = 0; j < n; j++){
            if(k == 0 && j == 0) continue;
            if(k == n-1 && j == n-1) continue;
            
            if(k%2 == 0){
               board[k][j] = 1L << k+j;
            }
         }
      }
      
      for(int k = 0; k < n; k++){
         StringJoiner sj = new StringJoiner(" ");
         for(int j = 0; j < n; j++){
            sj.add("" + board[k][j]);
         }
         out.println(sj.toString());
      }
      
      out.flush();
      
      int q = Integer.parseInt(f.readLine());
      for(int t = 0; t < q; t++){
         long i = Long.parseLong(f.readLine());
         
         ArrayList<Integer> x = new ArrayList<Integer>();
         ArrayList<Integer> y = new ArrayList<Integer>();
         
         int curx = 0;
         int cury = 0;
         
         x.add(1);
         y.add(1);
         
         while(curx < n-1 || cury < n-1){
            if(curx == n-1){
               cury++;
            } else if(cury == n-1){
               curx++;
            } else {
               long and = Math.max(board[curx+1][cury],board[curx][cury+1]);
               if(((i & and) > 0) ^ (board[curx+1][cury] > 0)){
                  cury++;
               } else {
                  curx++;
               }
            
            
            }
            
            x.add(curx+1);
            y.add(cury+1);
         }
         
         StringJoiner sj = new StringJoiner(" ");
         for(int k = 0; k < x.size(); k++){
            sj.add("" + x.get(k) + " " + y.get(k));
         }
         out.println(sj.toString());
         out.flush();
      }
      
      
      
      
      
      
      
      
      out.close();
   }
   
      
}

Solution (C++) by hugopm

#include <bits/stdc++.h>
#define len(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define chmax(x, v) x = max((x), (v))
#define chmin(x, v) x = min((x), (v))
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int side; cin >> side;
	vector<vector<ll>> grid(side, vector<ll>(side, 0));
	for (int i = 0; i < side; ++i) {
		for (int j = 0; j < side; ++j) {
			if ((i-j+side)&2LL) grid[i][j] = (1LL << (i+j));
			cout << grid[i][j] << " \n"[j==side-1];
		}
	}
	cout << flush;
	int nbQuery; cin >> nbQuery;
	for (int iQuery = 0; iQuery < nbQuery; ++iQuery) {
		ll sum; cin >> sum;
		cout << "1 1";
		int row = 0, col = 0;
		for (int diag = 0; diag < 2*side-2; ++diag) {
			ll should = sum&(1LL<<(diag+1));
			if (row+1<side && grid[row+1][col] == should) ++row;
			else ++col;
			cout << " " << row+1 << " " << col+1;
		}
		cout << endl << flush;
	}
}

Idea: Tlatoani

Preparation: Tlatoani and golions

Tutorial is loading...

EDIT: The fact that the order of operations doesn't matter turned out to be harder to prove than I thought (thanks to the comments for pointing this out), so I decided to add the following proof:

If you have two sequences of maximal operations, then what we want to show is that they have to consist of the same operations (possibly in different orders). Since they are both maximal, they must either both be empty or both be nonempty. If they are both empty then we are done.

If they are both nonempty: consider the current state of the vector (before applying either sequence of operations). Since the sequences are nonempty, there is at least one operation $$$\alpha$$$ that can be immediately applied on the vector.

Here we should make the observation that applying an operation at some index cannot prevent operations at other indexes from being able to be applied (it can only allow other operations to be applied).

Therefore, applying other (different) operations cannot prevent operation $$$\alpha$$$ from being able to be applied, so operation $$$\alpha$$$ must occur in both sequences. From our observation, we can see that if, in either sequence, operation $$$\alpha$$$ does not occur initially, then operation $$$\alpha$$$ can be applied initially because by performing it earlier we are not preventing any of the operations in between from being applied.

Thus, the first operation of each sequence is now the same, so we can apply the same argument to the remainder of the sequence (since it must be finite).

Solution (Kotlin) by Tlatoani

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {
    val jin = BufferedReader(InputStreamReader(System.`in`))
    val n = jin.readLine().toLong()
    val tokenizer = StringTokenizer(jin.readLine())
    var sum = 0L
    for (j in 0L until n) {
        sum += tokenizer.nextToken().toLong() - j
    }
    val joiner = StringJoiner(" ")
    for (j in 0L until n) {
        joiner.add(((sum / n) + (if (j < sum % n) 1L else 0L) + j).toString())
    }
    println(joiner)
}

Solution (Java) by qlf9

import java.util.*;
import java.io.*;

public class OmkarAndLandslideNumber2 {
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        long n = Long.parseLong(f.readLine());
        long sum = 0;
        StringTokenizer st = new StringTokenizer(f.readLine());
        for(int i = 0; i < n; i++){
            sum+=Long.parseLong(st.nextToken());
        }
        long k = ((sum - n*(n - 1)/2) / n);
        long diff = sum - (n*k + n*(n - 1)/2);
        StringBuilder ans = new StringBuilder();
        for(long i = 0; i < n; i++){
            if(i < diff){
                ans.append(k+i+1L);
                ans.append(" ");
            }else{
                ans.append(k+i);
                ans.append(" ");
            }
        }
        out.println(ans.toString().trim());
        out.close();
    }
}

Solution (C++) by Devil

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	ll n;
	cin >> n;
	ll s = 0;
	for (ll x, i = 0; i < n; ++i)
		cin >> x, s += x;

	ll l = (s - n * (n-1) / 2) / n + 1;
	s = l * n + n * (n-1) / 2 - s;
	for (int i = 0; i < n; ++i)
		cout << l + i - (n-i <= s) << " \n"[i+1==n];

	return 0;
}

Idea: Tlatoani

Preparation: Tlatoani and qlf9

Tutorial is loading...

Solution (Kotlin) by Tlatoani

import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.max
import kotlin.math.min

fun main() {
    val jin = BufferedReader(InputStreamReader(System.`in`))
    var line = jin.readLine().split(" ")
    val n = line[0].toInt()
    val m = line[1].toInt()
    val k = line[2].toInt()
    val dpLeft = IntArray(1 shl k) { n + 1 }
    val dpRight = IntArray(1 shl k) { -1 }
    var original = jin.readLine().reversed().toInt(2)
    var goal = jin.readLine().reversed().toInt(2)
    val permutation = IntArray(k) { it }
    dpLeft[original] = 0
    dpRight[goal] = 0
    for (j in 1..n) {
        line = jin.readLine().split(" ")
        val a = line[0].toInt() - 1
        val b = line[1].toInt() - 1
        var c = (original shr permutation[a]) and 1
        var d = (original shr permutation[b]) and 1
        original -= c shl permutation[a]
        original -= d shl permutation[b]
        original += d shl permutation[a]
        original += c shl permutation[b]
        c = (goal shr permutation[a]) and 1
        d = (goal shr permutation[b]) and 1
        goal -= c shl permutation[a]
        goal -= d shl permutation[b]
        goal += d shl permutation[a]
        goal += c shl permutation[b]
        dpLeft[original] = min(dpLeft[original], j)
        dpRight[goal] = j
        c = permutation[a]
        d = permutation[b]
        permutation[a] = d
        permutation[b] = c
    }
    var best = -1
    var l = -1
    var r = -1
    for (mask in (1 shl k) - 1 downTo 0) {
        for (e in 0 until k) {
            if ((mask shr e) and 1 != 0) {
                dpLeft[mask - (1 shl e)] = min(dpLeft[mask - (1 shl e)], dpLeft[mask])
                dpRight[mask - (1 shl e)] = max(dpRight[mask - (1 shl e)], dpRight[mask])
            }
        }
        if (dpLeft[mask] + m <= dpRight[mask] && Integer.bitCount(mask) > best) {
            best = Integer.bitCount(mask)
            l = dpLeft[mask] + 1
            r = dpRight[mask]
        }
    }
    println(k - Integer.bitCount(original) - Integer.bitCount(goal) + (2 * best))
    println("$l $r")
}

Solution (Java) by qlf9

import java.io.*;
import java.util.*;

public class OmkarAndPies {
    public static int INF = Integer.MAX_VALUE/2;
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int bitstr = Integer.parseInt(f.readLine(), 2);
        int goal = Integer.parseInt(f.readLine(), 2);
        int[] arr1 = new int[n];
        int[] arr2 = new int[n];
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(f.readLine());
            arr1[i] = Integer.parseInt(st.nextToken());
            arr2[i] = Integer.parseInt(st.nextToken());
        }
        int[] lefts = new int[n+1];
        int[] rights = new int[n+1];
        rights[0] = goal;
        lefts[0] = bitstr;
        int[] permutation = new int[k];
        int[] indices = new int[k];
        for(int i = 0; i < k; i++){
            permutation[i] = i;
            indices[i] = i;
        }
        for(int i = 0; i < n; i++){
            int temp = indices[arr1[i]-1];
            indices[arr1[i]-1] = indices[arr2[i]-1];
            indices[arr2[i]-1] = temp;
            permutation[indices[arr1[i]-1]] = arr1[i]-1;
            permutation[indices[arr2[i]-1]] = arr2[i]-1;
            lefts[i+1] = applyPermutation(indices, bitstr, k);
            rights[i+1] = applyPermutation(indices, goal, k);
        }
        int[] dpLeft = new int[(1 << k)];
        int[] dpRight = new int[(1 << k)];
        Arrays.fill(dpLeft, INF);
        Arrays.fill(dpRight, -INF);
        for(int i = 0; i <= n; i++){
            dpLeft[lefts[i]] = Math.min(dpLeft[lefts[i]], i);
            dpRight[rights[i]] = Math.max(dpRight[rights[i]], i);
        }
        for(int i = (1 << k)-1; i > 1; i--){
            int temp = i;
            int count = 0;
            while(temp != 0){
                if(temp % 2 == 1){
                    dpLeft[i-(1 << count)] = Math.min(dpLeft[i-(1 << count)], dpLeft[i]);
                    dpRight[i-(1 << count)] = Math.max(dpRight[i-(1 << count)], dpRight[i]);
                }
                temp/=2;
                count++;
            }
        }
        for(int i = 0; i < (1 << k); i++){
            if(dpLeft[i] == 2 && dpRight[i] == 8){
                System.out.println(i);
            }
        }
        int maxVal = -INF;
        int intLeft = -1;
        int intRight = -1;
        for(int i = 0; i < (1 << k); i++){
            if(dpRight[i]-dpLeft[i] < m) continue;
            int a1 = lefts[dpLeft[i]];
            int a2 = rights[dpRight[i]];
            int count = 0;
            for(int j = 0; j < k; j++){
                if(a1 % 2 == a2 % 2) count++;
                a1/=2;
                a2/=2;
            }
            if(count > maxVal){
                maxVal = count;
                intLeft = dpLeft[i]+1;
                intRight = dpRight[i];
            }
        }
        out.println(maxVal);
        out.println(intLeft + " " + intRight);
        out.close();


    }
    public static int applyPermutation(int[] permutation, int bitstr, int k){
        int ans = 0;
        for(int i = k-1; i >= 0; i--){
           if(bitstr % 2 == 1){
               ans += (1 << (k-permutation[i]-1));
           }
           bitstr/=2;
        }
        return ans;
    }
}

Solution (C++) by mohammedehab2002

#include <bits/stdc++.h>
using namespace std;
int p[20],dp[2][(1<<20)];
int getmask(string s)
{
	int ans=0;
	for (int i=0;i<s.size();i++)
	ans|=((s[i]-'0')<<i);
	return ans;
}
int main()
{
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	string a,b;
	cin >> a >> b;
	for (int i=0;i<k;i++)
	p[i]=i;
	for (int i=0;i<(1<<k);i++)
	{
		dp[0][i]=1e9;
		dp[1][i]=-1e9;
	}
	dp[0][getmask(a)]=0;
	dp[1][getmask(b)]=0;
	for (int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		x--;
		y--;
		swap(p[x],p[y]);
		string aa(k,'0'),bb(k,'0');
		for (int j=0;j<k;j++)
		{
			aa[p[j]]=a[j];
			bb[p[j]]=b[j];
		}
		dp[0][getmask(aa)]=min(dp[0][getmask(aa)],i);
		dp[1][getmask(bb)]=i;
	}
	int o1=count(a.begin(),a.end(),'1'),o2=count(b.begin(),b.end(),'1');
	pair<int,pair<int,int> > ans(0,{0,0});
	for (int i=(1<<k)-1;i>=0;i--)
	{
		if (dp[1][i]-dp[0][i]>=m)
		ans=max(ans,make_pair(k-(o1+o2-2*__builtin_popcount(i)),make_pair(dp[0][i]+1,dp[1][i])));
		for (int j=0;j<k;j++)
		{
			if (i&(1<<j))
			{
				dp[0][i^(1<<j)]=min(dp[0][i^(1<<j)],dp[0][i]);
				dp[1][i^(1<<j)]=max(dp[1][i^(1<<j)],dp[1][i]);
			}
		}
	}
	printf("%d\n%d %d",ans.first,ans.second.first,ans.second.second);
}

Idea: Tlatoani

Preparation: Tlatoani

Tutorial is loading...

Solution (C++) by zscoder

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int MOD = 998244353;

vector<int> fact;
vector<int> ifact;
vector<int> pow2;
int add(int a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
	return a;
}
void radd(int &a, int b)
{
	a=add(a,b); 
}
int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}
void rmult(int &a, int b)
{
	a=mult(a,b);
}
int modpow(int a, int b)
{
	int r=1;
	while(b)
	{
		if(b&1) r=mult(r,a);
		a=mult(a,a);
		b>>=1;
	}
	return r;
}
int choose(int a, int b)
{
	if(a<0) return 0;
	if(b<0) return 0;
	if(a<b) return 0;
	if(b==0) return 1;
	if(a==b) return 1;
	return mult(fact[a],mult(ifact[b],ifact[a-b]));
}
int inverse(int a)
{
	return modpow(a,MOD-2);
}
void init(int _n)
{
	fact.clear(); ifact.clear(); pow2.clear();
	fact.resize(_n+1);
	ifact.resize(_n+1);
	pow2.resize(_n+1);
	pow2[0]=1;
	ifact[0]=1;
	fact[0]=1;
	for(int i=1;i<=_n;i++)
	{
		pow2[i]=add(pow2[i-1],pow2[i-1]);
		fact[i]=mult(fact[i-1],i);
		//ifact[i]=mult(ifact[i-1],inv[i]);
	}
	ifact[_n] = inverse(fact[_n]);
	for(int i=_n-1;i>=1;i--)
	{
		ifact[i] = mult(ifact[i + 1], i + 1);
	}
}
	
int solve_slow(int n, int m)
{
	vi f(n+1,0);
	for(int k=1;k<=n;k++)
	{
		int sum=0;
		for(int l=1;l<=k;l++)
		{
			for(int i=0;i<=n;i++)
			{
				int coeff = mult(mult(choose(k,l),mult(choose(n-k,i-l), mult(fact[i], mult(m, fact[n+m-i-1])))), ifact[n+m]);
				radd(sum, mult(coeff, add(f[k-l],i+1)));
			}
		}
		{
			int l=0;
			int sumcoeff=0;
			for(int i=0;i<=n;i++)
			{
				int coeff = mult(mult(choose(k,l),mult(choose(n-k,i-l), mult(fact[i], mult(m, fact[n+m-i-1])))), ifact[n+m]);
				radd(sum, mult(coeff, i+1));
				radd(sumcoeff,coeff);
			}
			int actualcoeff = add(1,MOD-sumcoeff);
			assert(actualcoeff!=0);
			f[k]=mult(inverse(actualcoeff),sum);
		}
	}
	return f[n];
}

int solve_fast(int n, int m)
{
	vi f(n+1,0);
	int presum=0;
	for(int k=1;k<=n;k++)
	{
		int sum=mult(presum,choose(n+m,m+k));
		radd(sum,mult(fact[m-1],mult(choose(m+k+1,m+1),choose(n+m+1,m+k+1))));
		int outsidecoeff = mult(fact[k],mult(fact[n-k],mult(ifact[n+m],m)));
		sum = mult(sum, outsidecoeff);
		f[k]=mult(mult(m+k,mult(ifact[k],fact[k-1])),sum);
		//f[k]=mult(mult(k,mult(fact[m+k-1],ifact[m+k])),sum);
		radd(presum,mult(fact[m+k-1],mult(ifact[k],f[k])));
	}
	return f[n];
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	init(int(1e7)+100);
	int n,m; cin>>n>>m;
	//cout<<solve_slow(n,m)<<'\n';
	cout<<solve_fast(n,m)<<'\n';
}

Solution (Java) by qlf9

import java.util.*;
import java.io.*;

public class ZSShufflesCards {
    public static long MOD = 998244353;
    public static long[] fact;
    public static long[] invfact;
    public static long[] pow2;
    public static int MAX = 4000005;
    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        fact = new long[MAX];
        invfact = new long[MAX];
        pow2 = new long[MAX];
        fact[0] = 1;
        invfact[0] = 1;
        pow2[0] = 1;
        for(int i = 1; i < MAX; i++){
            pow2[i] = add(pow2[i-1], pow2[i-1]);
            fact[i] = mult(fact[i-1], i);
        }
        invfact[MAX-1] = inverse(fact[MAX-1]);
        for(int i = MAX-2; i >= 1; i--){
            invfact[i] = mult(invfact[i+1], i+1);
        }
        long[] ans = new long[n+1];
        long currsum = 0;
        for(int k = 1; k <= n; k++){
            long sum = mult(currsum, ncr(n+m, m+k));
            sum = add(sum,mult(fact[m-1],mult(ncr(m+k+1,m+1),ncr(n+m+1,m+k+1))));
            long outsidecoeff = mult(fact[k],mult(fact[n-k],mult(invfact[n+m],m)));
            sum = mult(sum, outsidecoeff);
            ans[k]=mult(mult(m+k,mult(invfact[k],fact[k-1])),sum);
            currsum = add(currsum,mult(fact[m+k-1],mult(invfact[k],ans[k])));
        }
        out.println(ans[n]);
        out.close();

    }
    public static long add(long a, long b){
        return((a+b)%MOD+MOD)%MOD;
    }
    public static long mult(long a, long b){
        return((a*b)%MOD+MOD)%MOD;
    }
    public static long pow(long a, long b){
        long ans = 1;
        while(b > 0){
            if((b&1) == 1) ans = mult(ans, a);
            a = mult(a, a);
            b>>=1;
        }
        return ans;
    }
    public static long ncr(long a, long b){
        if(a<0) return 0;
        if(b<0) return 0;
        if(a<b) return 0;
        if(b==0) return 1;
        if(a==b) return 1;
        return mult(fact[(int)a],mult(invfact[(int)b],invfact[(int)(a-b)]));
    }
    public static long inverse(long a){
        return pow(a, MOD-2);
    }
}

Solution (Kotlin) by Tlatoani

const val MOD = 998244353L

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }
    val factorial = LongArray(4000002)
    factorial[0] = 1L
    for (j in 1..4000001) {
        factorial[j] = (j.toLong() * factorial[j - 1]) % MOD
    }
    val factInv = LongArray(4000002)
    factInv[4000001] = factorial[4000001] pow -1
    for (j in 4000000 downTo 0) {
        factInv[j] = ((j + 1).toLong() * factInv[j + 1]) % MOD
    }
    fun choose(a: Int, b: Int) = if (a < 0 || b < 0 || b > a) 0L else (factorial[a] * ((factInv[b] * factInv[a - b]) % MOD)) % MOD
    val answer = LongArray(n + 1)
    var currSum = 0L
    for (k in 1..n) {
        var sum = currSum * choose(n + m, m + k)
        sum %= MOD
        sum += factorial[m - 1] * ((choose(m + k + 1, m + 1) * choose(n + m + 1, m + k + 1)) % MOD)
        sum %= MOD
        sum *= (factorial[k] * ((factorial[n - k] * ((factInv[n + m] * m.toLong()) % MOD)) % MOD)) % MOD
        sum %= MOD
        answer[k] = sum * (((m + k).toLong() * ((factInv[k] * factorial[k - 1]) % MOD)) % MOD)
        answer[k] %= MOD
        currSum += factorial[m + k - 1] * ((factInv[k] * answer[k]) % MOD)
        currSum %= MOD
    }
    println(answer[n])
}

const val MOD_TOTIENT = MOD.toInt() - 1

infix fun Long.pow(power: Int): Long {
    var e = power
    e %= MOD_TOTIENT
    if (e < 0) {
        e += MOD_TOTIENT
    }
    if (e == 0 && this == 0L) {
        return this
    }
    var b = this % MOD
    var res = 1L
    while (e > 0) {
        if (e and 1 != 0) {
            res *= b
            res %= MOD
        }
        b *= b
        b %= MOD
        e = e shr 1
    }
    return res
}

Idea: zscoder

Preparation: zscoder

Tutorial is loading...

Solution (C++) by KLPP

#include<bits/stdc++.h>

using namespace std;
#define MAX 262144
#define MAXN 1000000
long long int a[MAXN],b[MAXN];


using cd = complex<double>;
const double PI = acos(-1);
vector<cd> A(MAX),B(MAX);
vector<cd> Amx(MAX),Bmx(MAX);
vector<cd> Amn(MAX),Bmn(MAX);
vector<cd> E11(MAX),E12(MAX),E21(MAX),E22(MAX);
vector<cd> SQ1(MAX),SQ2(MAX);
vector<cd> V(MAX);
vector<long long int> A1(MAX),A2(MAX);

void fft(vector<cd> & a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd & x : a)
            x /= n;
    }
}
void prod(vector<cd> &a, vector<cd> &b, vector<cd> &c){
  for(int i=0;i<a.size();i++){
    c[i]=a[i]*b[i];
  }
}

int main(){
  long long int n,m,q;
  scanf("%lld %lld %lld",&n,&m,&q);
  
  for(int i=0;i<n;i++){
    scanf("%lld",&a[i]);
  }
  for(int i=0;i<m;i++){
    scanf("%lld",&b[i]);
  }
  for(int i=0;i<MAX;i++){
    A[i]=cd(0,0);
    Amn[i]=cd(0,0);
    Amx[i]=cd(0,0);
    B[i]=cd(0,0);
    Bmn[i]=cd(0,0);
    Bmx[i]=cd(0,0);
  }
  for(int i=0;i<n;i++){
    A[a[i]]+=cd(1,0);
  }
  for(int i=0;i<n-1;i++){
    Amn[min(a[i],a[i+1])]+=cd(1,0);
  }
  for(int i=0;i<n-1;i++){
    Amx[max(a[i],a[i+1])]+=cd(1,0);
  }
  for(int i=0;i<m;i++){
    B[b[i]]+=cd(1,0);
  }
  for(int i=0;i<m-1;i++){
    Bmn[min(b[i],b[i+1])]+=cd(1,0);
  }
  for(int i=0;i<m-1;i++){
    Bmx[max(b[i],b[i+1])]+=cd(1,0);
  }
  
  fft(A,0);
  fft(Amn,0);
  fft(Amx,0);
  fft(B,0);
  fft(Bmn,0);
  fft(Bmx,0);
  prod(A,Bmn,E11);
  prod(Amn,B,E12);
  prod(Amx,B,E21);
  prod(A,Bmx,E22);
  prod(Amn,Bmn,SQ1);
  prod(Amx,Bmx,SQ2);
  prod(A,B,V);
  fft(E11,1);
  fft(E12,1);
  fft(E21,1);
  fft(E22,1);
  fft(SQ1,1);
  fft(SQ2,1);
  fft(V,1);
  for(int i=0;i<MAX;i++){
    A1[i]=round(SQ1[i].real())-round(E11[i].real())-round(E12[i].real())+round(V[i].real());
    A2[i]=round(SQ2[i].real())-round(E21[i].real())-round(E22[i].real())+round(V[i].real());
  }
  for(int i=1;i<MAX;i++){
    A2[i]+=A2[i-1];
  }
  for(int i=MAX-2;i>-1;i--){
    A1[i]+=A1[i+1];
  }
  for(int i=0;i<q;i++){
    int query;
    scanf("%d",&query);
    //cout<<A1[query]<<" "<<A2[query-1]<<endl;
    printf("%lld\n",A1[query]-A2[query-1]);
  }
  return 0;
}

Idea: KLPP

Preparation: KLPP

Полный текст и комментарии »

Блог пользователя Tlatoani

ORIGINAL:

UPDATE: