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
- A: 12
- B: 16
- C: 6
- D: 19
- E: 18
- F: 2
Total: 73
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 — 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
Auto comment: topic has been updated by Tlatoani (previous revision, new revision, compare).
Thanks for the fast editorial! The contest was awesome!
Auto comment: topic has been updated by Tlatoani (previous revision, new revision, compare).
What a fast editorial!
To everyone who got hacked on problem 2 (me included)
wait how did everyone get hacked? like what was the test case?
i also got hacked, but most hacked solutions won't pass system tests anyway so yeah.
tourist : 5 problem — 12 minutes...
My whole 3hr work ... LOL
Has anyone printed this for 1392E - Omkar and Duck? (example with
n = 10)Submission: 90149344
I used the same logic that you did except that I used the last element of each row equal to the second last element instead of using 1s.
My submission — 90156646
I solved it as in the editorial
Can you explain your solution?
The matrix satisfies two properties -
First, for any cell (i,j) the path which gives the smallest sum is always RRR...DDD... and the path which gives the largest sum is DDD...RRR...
Secondly, for any cell (i,j) not lying in the topmost row or leftmost column, the maximum sum obtained in any path to the cell (i-1, j) is always 1 less than the minimum sum obtained in any path to the cell (i,j-1).
After constructing such a grid, for each query we backtrack from (n,n) to (1,1) using these maximum and minimum sums.
Let $$$S_{i, j}$$$ be the set of weights of all paths from
(1, 1)to(i, j).The idea is that $$$S_{i, j}$$$ and $$$S_{i - 1, j + 1}$$$ should be disjoint. Also, $$$S_{i, j}$$$ can be obtained by merging $$$S_{i - 1, j}$$$ and $$$S_{i, j - 1}$$$ and adding
a[i][j]to all weights.So, for each cell, you can greedily choose
a[i][j]such that $$$min(S_{i, j}) = max(S_{i - 1, j + 1}) + 1$$$. It turns out that, for each cell, $$$S_{i, j}$$$ contains consecutive elements, so you can store efficiently these sets by storing only the minimum and the maximum.Almost the same principle, but a little differences:
so my numbers bigger but still acceptable (max is 39_301_087_452_632 for 25x25)
90174692
Problems were awesome, thanks for the fast editorial
can Anyone help me with some doubts I have. i attended a interview today and it has two question. can someone could say solution for it.
https://mirror.codeforces.com/topic/82091/en2
Thanks in Advance!!!!!
anyone please!!!! just giving idea to solve will be a great help
First at least post it so people can comment on it. It is currently just a revision
Auto comment: topic has been updated by Tlatoani (previous revision, new revision, compare).
An easier solution for $$$H$$$.
First, the answer is the expected number of jokers times (the expected number of cards you draw before a joker + the joker).
The expected number of jokers can be expressed as $$$\sum_{k\geq 0}$$$ Pr[S is not full after $$$k$$$ jokers].
By PIE, Pr[S is not full after $$$k$$$ jokers]= $$$\sum_{i=1}^n {n \choose i} (-1)^{i-1} (\frac{m}{m+i})^k$$$.
So we get the answer.
Can you explain how PIE formula works here?
boboniu!
Thanks for a good round and fast editorial!
In Problem A,
According to editorial [7,4,3,7] gives '1'. But it should be 3 right! [7,4,3,7] => [7,7(4+3),7] gives 3 right! Please help!
it is 1. in the array [7,4,3,7], you can do these steps: step 1: [7+4,3,7] step 2: [11+3,7] step 3: [21] Answer = 1
Hi Akhil, How about [7,4,3,7] => [11,3,7] => [14,7] => [21]?
You can take any two consecutive and have to minimize.
Fast editorials are always great ! :) Thanks Tlatoani
Thanks!
The answer for H can even be simplified to $$$\left(\frac{n}{m+1}+1\right)\cdot\left(m\cdot H_n+1\right)$$$ where $$$H_n = \frac11+\frac12+\dots+\frac1n$$$.
Is there any combinatorics proof for this? (I assume not but) or just algebra
My solution did not involve any algebra.
Call an iteration of the process to be drawing cards until we reshuffle. In each iteration, we draw each of the $$$n$$$ normal cards with probability $$$\frac1{m+1}$$$ and 1 joker. Thus in expectation every iteration takes $$$\left(\frac{n}{m+1}+1\right)$$$ seconds.
We now need to calculate the expected number of iterations (and we can ignore how many cards we draw during each iteration). Let's say there are $$$k$$$ remaining useful cards we need when we start an iteration. With probability $$$\frac{m}{m+k}$$$ the first {useful card or joker} is a joker, and we start a new iteration. The rest of the time, the situation has converted to the start of an iteration where there are $$$k-1$$$ useful cards we need. If we let $$$I_k$$$ be the number of iterations we need when there are $$$k$$$ things not in our set, so we note that if each iteration has probability $$$\frac{m}{m+k}$$$ of ending uselessly, and probability $$$\frac{k}{m+k}$$$ of converting down, then the recursive formula is $$$I_k = \frac{m}{k} + I_{k-1}$$$. Noting $$$I_1 = m + 1$$$ gives us $$$I_k = m \cdot H_k + 1$$$.
Multiplying these two numbers together gives us the answer.
Thank you so much for the explanation, amazing and clean answer.
Can you just multiply these two expected values together? These two values don't seem to be independent (1 iteration implies that you must have drawn n+1 cards).
Let $$$E$$$ denote expected value and $$$P$$$ denote probability.
We used the fact that the length of the $$$i$$$-th iteration given that the game didn't end after $$$i-1$$$ iterations is still $$$\frac{n}{m+1}+1$$$. However, this does not imply that
which is what you wrote above.
It's worth pointing out that having the type of independence you correctly note is absent would likely not even be useful. (Not that its absence is a poor reason to take caution!) Sure, if $$$N$$$, $$$X$$$ are two independent non-negative random variables, then $$$\operatorname{E}[\,N \cdot X\,] = \operatorname{E}[\,N\,] \cdot \operatorname{E}[\,X\,]$$$, but if $$$N$$$ is the number of iterations and $$$T = N \cdot X$$$ is the total time elapsed, then the necessary value $$$X = T / N$$$ is probably tricky to say anything useful about, and there is no better hope of multiplying the duration of any single iteration by something convenient and getting the total duration of all iterations.
Of course, thinking about when (and how often) each iteration duration $$$X_i$$$ in the infinite i.i.d. sequence $$$ \{X_i\}_{i=1}^\infty $$$ will contribute to the overall time leads directly to the argument Benq describes above, but may have the downside that it "doesn't feel like" multiplication as much as a kind of factorization.
Another way of approaching this, which uses more advanced concepts, but which might be more intuitive, is to note that $$$Y_k = \sum_{i=1}^k X_i - \left(\frac{n}{m+1}+1\right)$$$ defines a martingale, that $$$N$$$ is a stopping time with respect to its natural filtration, and that
It's then easy to verify that $$$ Y_N $$$ satisfies the conditions of the optional stopping theorem, so that
These abstractions might seem intimidating, but they really aren't doing much more here than capturing why Benq's argument works.
It seems that the result is known as Wald's equation in martingale theory.
Why is I_k = m/k + I_(k-1)?When there are k useful cards,the probability of converting down is k/(m+k).Why the expected number of iterations to k-1 useful cards is not the reciprocal of k/(m+k),and I_k = m/k + 1 + I_(k-1)?
$$$I_k=\frac{k}{m+k}\cdot I_{k-1}+\frac{m}{m+k}\cdot (I_k+1)$$$
Why is the expectation for the first part $$$\ (\frac{n}{m+1} + 1)$$$?
If you choose any card (aside from the jokers), the probability that it comes before all $$$m$$$ jokers is $$$\frac{1}{m+1}$$$. Sum this over all $$$n$$$ cards (by linearity of expectation).
why the probability is 1/(m+1)?
For any set of $$$x$$$ cards, each card comes first with probability $$$\frac{1}{x}$$$.
Hello sir conqueror_of_tourist, Why don't you open a YouTube channel, like you are one of the red coder which codes in python. It will be helpful for many of us. Please think about it. Thanks
I hacked tfg's solution for B.by test 1 1 1 -1.Its answer is actually 0 but tfg's solution got 1.
Don't you think that tfg code for problem B is incorrect. mx should be start from -1e9 because array value can be negative also
UPDATE: Now, it has been corrected.
Yes,actually it is.I hack 4 solutions with this test.THIS SOLUTION IS WRONG!!!
For D I would like to share my approach
You can split the array into segments which do not interact with each other. Each segment must either be - "RRLL" - "RL" - "RRL" - "RLL"
dp[i] records the minimum number of changes needed such that arr[:i] is made up of the above segments.
We can assume that the first element in the array do not interact with the last element of the array, by shifting the array four times and calculating the optimal changes required for each.
I did this too! I think you only need to shift it three times because the requirement is that the solution starts with R, and there are at most two Ls in a row, but I also happened to shift it four times just to be safe.
Hi! Can you please give the submission link to you solution? I am trying to find it , but unable to do so right now. Thanks.
You can have a look at 266445768
In the problem B tutorial (c++ one) max taken here is 0 and should be taken -INT_MAX most people got hacked for that only. (edit : its been corrected).
So tfg's solution is wrong
it's now been corrected.
I think the tutorial of Question C is wrong, or maybe I'm wrong, so if possible please solve my query. If the maximum element of the input slides occurs somewhere in between, then the next subsequent elements have to at least as big as this element. So taking max(arr[i]-arr[i+1],0) won't work. Consider this example.
1
16
17 15 12 16 25 15 12 18 19 16 15 11 14 16 17 17
Now if you go by the tutorial you will get the answer as 26. But look there's a 25 in between. Meaning all the subsequent supports have to increases to at least 25 to make it a non-decreasing array. In that the answer would more than 25.
Could you help qlf9
You don't know how to get 26 for this example? For every $$$a[i - 1] - a[i] > 0$$$ in decreasing order of $$$i$$$, perform $$$a[i - 1] - a[i]$$$ operations over the range $$$[i, n]$$$.
I know Nson. I get where that logic is coming from. But all I am saying is that this logic is wrong. I am even providing you with a counter example. Try the counter example and see it for yourself. If my counter example is wrong then please tell me. 26 is wrong for this example. As I said earlier, the 5th element is 2(which is also the maximum), meaning all the subsequent elements have to increased at least to 25 to make it a non-decreasing array. If i am misunderstanding something tell me
I just provide you the algorithm to build the correct answer.
I ran locally and got these
The first four elements can be smaller than 25. And I don’t really know what you want to prove.
Read the problem statement carefully before commenting.
it is right that all subsequent elements have to be at least 25 but it does not mean that to make them at least 25 we have to perform 25 or more operations.[12,13,25,12,20] here we need only 13 operations. Hope I got you right!!!
Thanks for helping me out. You guys are the best!!
Why doesn't the following work for H?
f(0) = 0 f(i) = 1 + i/(m+i) * f(i-1) + m/(m+i) * f(n)
My logic was that, at f(i), we must use a move and then there is a i/(m+i) chance the problem is reduced to f(i-1) and an m/(m+i) chance that we must restart (hence f(n)). Could someone help me understand the flaw in this approach?
You most likely misread the problem. There is replacement when a joker is drawn, and you should get a 2D recurrence of this form instead.
The deck is replaced for a joker
How to deal with overthinking, sometimes I end up making very complex logic even for easier problems like A and B ..
Do it for fun not for rating then you will be relaxed and automatically think simple.
Thanks for the great round and the fast editorial. I really loved the interactive problem.
can someone help me I am getting TLE on test 16 in E....
https://mirror.codeforces.com/contest/1392/submission/90165976
I got it don't bother.
You are using left shift to calculate power of (i+j).When (i+j)==31 it will give a negative number because if the number is shifted more than the size of integer, the behaviour is undefined. Try to calculate power of (i+j) with the help of dp and your solution will get accepted!
replacing 1 with 1LL worked.... thanks though.
For F, if you look at the list of height differences, then the problem is identical to Juggling Troupe from NWERC 2017, except jugglers are allowed to start with more than 2 balls.
It's probably easier to solve F if you haven't seen this problem ...
Actually there was also an old GCJ problem. It helped me a lot but yet another insight is needed for today's F, that's nice.
Ah, yes. F is easier because the heights start out strictly increasing (meaning each juggler starts with at least one ball in the transformed problem)... didn't notice this.
Explain D plz....i just changed LLL to LRL and RRR to RLR....couldnt find any other observations.
Probably, you forgot that beds are arranged in a circle and got wrong calculations on prefix/suffix
i checked on circles too. I still can't figure out where that observation fails.
Well, if you changed LLL to LRL too, but by just searching LLL and replacing them — this will fail at RLLLLLR (You will get RLRLRLR instead of RLLRLLR), so it is better to replace LLL to LLR.
Thanks. But, what will be the resultant string for LLLRRRLLL?
You're right, this replacement fails at this example :) But my solution counts answer without any replacements, so I just supposed this was your problem.
Can you briefly explain your solution, please?
Firstly, if there are both L and R in string I move the prefix that contain only L or only R to the end, if the last symbol is the same (like in your example LLLRRRLLL -> RRRLLLLLL). Then, I look at substrings containing only one symbol — if length of this substring is L, you need to add (L + 1) / 3 to answer — it is not hard to prove. And if the whole string is "LL...LL" or "RR...RR" answer is (n + 2) / 3, it is easy to prove, too.
Could the tutorial be any faster ? :D Amazing contest. Thanks a lot.
Can anyone please provide test case where my code would't give correct answer for problem A? 90106564
If biggest number comes in first position.
It looks like any decreasing sequence (e.g. 6 5 4) should fail your solution, because this check: long.Parse(s)>firstMax will be false and you'll never assign anything to secondMax.
I think the tutorial of Question C is wrong, or maybe I'm wrong, so if possible please solve my query. If the maximum element of the input slides occurs somewhere in between, then the next subsequent elements have to at least as big as this element. So taking max(arr[i]-arr[i+1],0) won't work. Consider this example.
1
16
17 15 12 16 25 15 12 18 19 16 15 11 14 16 17 17
Now if you go by the tutorial you will get the answer as 26. But look there's a 25 in between. Meaning all the subsequent supports have to increases to at least 25 to make it a non-decreasing array. In that the answer would more than 25.
Could you help qlf9 Tlatoani
17 15 12 16 25 15 12 18 19 16 15 11 14 16 17 17
after 4 moves
17 15 12 16 25 15 12 18 19 16 15 15 18 20 21 21
after 1 more move
17 15 12 16 25 15 12 18 19 16 16 16 19 21 22 22
after 3 more moves
17 15 12 16 25 15 12 18 19 19 19 19 22 24 25 25
Do the rest on your own.
Thanks for the fast editorial!
Request: Can the written explanations be hidden inside spoilers?
CONTEST WAS EXCELLENT! gg.
I solved 'D' with dynamic programming by changing the string so it is comprised of four available good options:
I then tried 4 (the longest good sequence) different string shifts to account for circular nature of the problem.
Submission: https://mirror.codeforces.com/contest/1392/submission/90138778
I did something similar. DP with 4 cases.
https://mirror.codeforces.com/contest/1392/submission/90124447
Cool!
It would probably be enough to only call solve() once, but initialize dp for all four cases:
Hey, do you know some easy equivalent problem without circular arrays? The code is very difficult to understand with circular arrays. I was unable to find a problem like given a 1D boolean array, find the minimum number of operations so that there are no 'k' consecutive characters... or any other, which can be solved using dp. TIA
I don't know non-circular equivalent, but although you need to put some thinking into circular nature of the problem, the code to account for it is quite short. In my submission (https://mirror.codeforces.com/contest/1392/submission/90138778) it's just shifting the string 4 times. In the editorial it's these lines:
I solved D in different way. I used a deque and a 3 element window. When I am getting LLL or RRR in the window I changed the 3rd element of that window to tht opposite one. But it failed on TC2.
Link for submission. https://mirror.codeforces.com/contest/1392/submission/90165043
I want to know is the approach totally wrong or something corner is missing.
LLLRR
Here it is obviously better to change the second L.
On my first attempt I changed the middle one ..it failed Then changed the last one...still failing
Can You Explain Why Are You Shifting the String ?
Good "group" may start at the end of the string.
Example: LLRRLR — it can't be separated into four seqeunces above,
but if you shift it: RLLRRL = RLL+RRL
Because the longest group length is 4 (RRLL), I need to try 4 different shifts
Your code is very clean...Thanks!
Glad you liked it
I was thinking the same logic but dp[1]=0 stands always or not? I am getting an error in it;
dp[0] = 0
How many characters do you need to change in first 0 characters to get a correct string? Because empty string is correct (in this problem) then it's 0
why tle in test case 9 in problem B? code
Because:
You search max element 'n' times. So it will need n*n operations.
oh thanks
wow I feel like an idiot for doing this too
I feel like an idiot for asking
How did everyone get hacked on B?
Mine failed system tests btw.
Many have initialized variable to 0 for finding max in array
Thanks for the round! I liked H. Kudos to simple solutions in the comments...
I came to the similar recurrence as in the editorial, while I simplified the computation part. When we have $$$\lvert S \rvert = x$$$, we can remove the cards with a number in $$$S$$$ and set the operation time to $$$1 + \frac{x}{m+(n-x)+1}$$$ seconds instead of $$$1$$$ second.
I am unable to understand why my solution for problem C does not work, what is the possible error. Someone's help with an example test case in which my solution gives wrong answer is highly appreciated.
Code link https://mirror.codeforces.com/contest/1392/submission/90159907
Use long long, not int
Clearly C wasn't rejected enough. Explains why it's the weakest problem of the contest.
I didn't understand the Editorial of C clearly.Can you explain C?
I had a different fucked up idea for task E using meet in the middle. Give random numbers to the array and find the path by using meet in the middle. Still don't know why I thought that the complexity would be O(T*2^n/2) when it was O(T*2^n). So yeah it failed on test 18. The probability to get a unique path is very high. I thought about the correct approach but this seemed way easier and I still can't understand why
Bear in mind that if the sum on your path is k, but your path is different from the actual hidden path, then your solution is still wrong!
There can be different paths with same K. Thus if the system selects one of the paths and output other, then its basically wrong. It just meant all path weights should be unique.
1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n ...
I did this for 1392E - Omkar and Duck. Is it wrong ?
what
any idea of the interactor of problem E. i mean , to prove my solution wrong you have to find at least 2 path with same sum. My question is how can i check this ? cz the sum might be very large.
Looks like I overcomplicated C a little bit using RMQ.
Used a well-known approach though.
How did you do it? I tried to do it during contest, but kept getting TLE. I tried updating all the elements from $$$i$$$ to $$$n - 1$$$ but kept getting TLE. Help please. Thanks! I tried using the approach from this.
let $$$b_i$$$ be the minimum number we have to add to $$$a_i$$$ to make the array $$$a$$$ sorted. Now the answer is the minimum number of operations to make all $$$b_i$$$ equal to $$$0$$$.
We can find the answer using this recursive function:
Initial call is $$$f(1,n,0)$$$.
My submission
Thank You!
Problem C should have dp tag.
Sheldon approves the rejection count 73.
Big Bang Theory fans will get this.
Also, press F to display your condolences for the problem setters.
Can any one help me figure a counter test case that fails my solution for D? in this code, I look for sub-strings of length 3 that are either LLL or RRR and if found, I increase the answer by 1 and moves the i to the next triplet of characters.
Thank you!
That was a mistake. I updated the case, check now.
Here's my approach for problem E (Much less intuitive: I dont know how one thinks of a solution like given in the editorial).
Idea is same: All paths should have different sums.
Set row_1 and col_n to 0. Now we fill elements starting from col_n-1 to col_1 and row_2 to row_n
Current max sum path through (i,j) is [(1,1)->(1,j)->(i,j)->(i,j+1)->(n,j+1)->(n,n)]
Minimum sum path through (i,j) is [(1,1)->(1,j)->(i,j)->(i,n)->(n,n)]
Value(i,j) should be such that minimum sum through (i,j) should be greater than current maximum sum through (i-1,j). Subtract the sum in 2 paths and add 1 to get Value(i,j)
Now processing queries is easy. From (x,y) you go down if sum from [(x,y+1)..(n,n)] < required sum else you go right.
For example n=6
1392E - Omkar and Duck
My solution
A possible approach to come with that solution:
- it could be useful to use powers of 2 (since different sums of distinct powers of 2 correspond to different numbers)
- distinct powers of 2: this means that you could put a different power of 2 on each diagonal (since we visit each diagonal only once, the powers are distinct)
- but this doesn't work because, if you are on some cell, at the next move you can go to 2 cells with an equal value, so you obtain 2 equal sums (i. e. the cells $$$(i + 1, j)$$$ and $$$(i, j + 1)$$$ have equal sums)
- so, you need to "turn off" one of these two cells for each $$$i, j$$$
- after drawing some cases it's easy to realize that you can "turn off" cells with odd $$$x$$$
I came out with your solution (link to comment) because I thought that $$$2^{50} > 10^{16}$$$, so I tried to put prefix sums of Pascal's triangle in the grid instead, then I optimized that approach.
Completely forgot that distinct 2-power sums are unique. Thanks
Yeah your is exactly the same solution, extra 1 added. xd
Kudos for providing solutions in other languages than C++!!
PS. But please don't write C++ in Java xD
My solution for B was hacked. How to view which test case failed?
Resubmit your code, you will get to know about the WA Testcases...
On E, I wrote a WA program but returned TLE. Why? TLE on test 1(WA) AC
You output the wrong answer, but your program doesn't stop.
I think the problem description should remind participants of this.
I'm just curious about how the tests for problem E were made. I'm thinking of finding two paths with equal sum then asking for this sum. Is this how the tests were made or it's just random? I don't think it's random so if the testers can satisfy my curiosity I'd be glad.
I'm not the tester but I did write something like interacotor( which can generate data and test a program ) locally. It turns out that the data generated randomly is already strong enough for every wrong approach I know.
I had another approach for C:
This is based on the fact that to increase the lowest point in a valley (the value go down then go up), all nearby value would be increase. So you just need to calculate the difference between the lowest point of the valley and the previous peak.
Please explain why this idea will work?? thanks in advance!!
i explained it:
This is based on the fact that to increase the lowest point in a valley (the value go down then go up), all nearby value would be increase. So you just need to calculate the difference between the lowest point of the valley and the previous peak.
I couldn't understand the solution of F, before I read the problem statement once again and realized that the constraint was not $$$h_1\leq h_2\leq\cdots\leq h_n$$$ but $$$h_1<h_2<\cdots <h_n$$$. What the heck. I was solving the harder version.
https://mirror.codeforces.com/contest/1392/submission/90188584 why this code giving memory limit exceeded
you are declaring an unordered_map where key values in the range of 1e9.
You can reduce memory usage by erasing map entries with value==0. erase()
thank you
Hello, can someone help me with alternate explanation for C ?? I am not able to keep up with the explanation given in editorial
About the proof of F, why is it clear that the order does not matter?
I was also curious about that — it is plausible (a priori) there could be a way to get stuck depending on your order (or at least, it's not immediately clear why that's false).
I proved that there can only be one difference of 0 in the end in a different way — I showed by induction that any two points with a difference of 0 must have a point in between with a difference of 2 or more.
It took a long time though — if I knew that order didn't matter, the conclusion would be much faster.
Can you please elaborate your inductive proof?
Consider the sequence of differences a[i+1]-a[i]. Let's call that sequence b[i].
The claim is that if at any point i<j and b[i]=b[j]=0 then there must be a k, i<k<j, where b[k]>=2.
Suppose this claim is false, and consider the first moment where this property fails — that means that b[i]=b[j]=0, and for all k, i<k<j => b[k] <= 1.
That means that the last move must have been somewhere on the interval [i,j]. Recall that a move at k reduces b[k] by 2 and increases b[k-1] and b[k+1] by 1. Since b[k-1] and b[k+1] are <=1, b[k-1] and b[k+1] must have been 0 before the move, and b[k] was 2 or more. But that means that the property was false on the previous turn too! A contradiction.
With the claim, since the last moment has only 1s and 0s, we know there can't be 2 0s.
viewing those operations as operator(function on vector), we only need to prove that operators are communicative, that is to say we only need to verify that for all index $$$i,j$$$, the operating order on $$$(h_i,h_{i+1})$$$ and $$$(h_j, h_{j+1})$$$ does not matter, which can be seen clearly for both $$$|i-j|=1$$$ and $$$|i-j| \neq 1$$$ cases.
If h=[1,3,4], then the only order is [1,3,4]->[2,2,4]->[2,3,3]. The other order [1,3,4]->[1,4,3]->[2,3,3] contains an invalid operation.
It does not matter much as we only care the output after these operations, and do not care the validness of those operations (just do them formally).
Why do we not care the validness? If we swap two adjacent operations, one of them may become invalid and force the process to end. Tlatoani would you help explain why is it clear that the order does not matter? It is definitely true but i think it requires a (nontrivial) proof.
If I get it correct, what the editorial does is just rearranging those operations, and what we need to make sure is that the output after rearranged operations is identical to the one after operations mentioned in the statement. Therefore, we may formally define operations $$$op_i$$$ on all states instead of valid states and check the communicative property. Once we get that property, we can claim that rearrangement does not affect the final result, and the valid rearrangement is just a special case of this.
This turned out to be harder to prove than I thought, but I think you can do something like this:
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).
Thank you for pointing out how this is nontrivial, I will probably update the editorial with this proof.
Can you please explain what does "maximal operations" mean?
A sequence of operations such that you cannoy perform any additional operations at the end.
In problem
D. Omkar and Bed Wars.Can someone tell me how they come with this formulafloor(n/3)orceil(n/3). During contest i was very confused about this. Do we have to come up with this formula directly with intuition or their is some simple thinking strategy which can be used for other problems also.I assume you agree that the illogical strategy happens when there is $$$LLL$$$ or $$$RRR$$$.
So if the given string has all characters same, then you split it into, say, buckets of length 3 and flip the 3rd character, i.e. $$$RRR$$$ -> $$$RRL$$$. This way, if n is not divisible by 3, then there's at least one character left, and it wraps around to beginning where there are two same of them. In other words, the last, then first and second characters are the same so we need to deal with this. So it becomes $$$ceil(n/3)$$$ or $$$(n + 2) / 3$$$. This is the case when the string has all same characters.
If the string doesn't have all characters same, and has a maximal segment of length k of same characters. Then we do the same operation as we did above, however, this time, since both sides of the segment has different character and there'd be at most two characters at the end (and in the beginning), we don't have to deal with what's left at the end. Thus, the answer for this segment is $$$k / 3$$$.
okk !! now i understood how to think in a more better way. Thank you !
For F, I didn't realize the heights were strictly increasing, I just thought they were non-decreasing. I believe my solution works for those cases too, if anyone is curious (or can find a counterexample).
Slightly cleaned up submission: 90191364
(I break the array into subarrays and solve each subarray. When the heights are strictly increasing, as in the actual problem, it just ends up doing a single subarray, haha.)
Can anyone spare some time to figure out why my solution is not working in C. My solution can be easily understood. Here is my code. Thanks in advance to that great soul who helps me.
It is asked to find the minimum number of operations to make the sequnce non decreasing. You do not calculate that. Instead, you calculate the number of operations to make all elements equal.
Can someone explain why in D we are rounding up instead of down?
Here's my explanation.
Can anyone help me find error in my code for C problem thanks in advance here is the link https://ide.geeksforgeeks.org/M9zO7OyT2Z
Please validate the output for following test case: 13 1 2 3 5 6 3 2 1 3 4 5 0 6
I got 6 as the answer which i think is the correct ans
Thanks for fast Editorial,Explanation for problem F is too good.
Problem E when I tried to generate 2^50 with bit shift i.e. 1<<50, I got a negative value. Then I had to use the pow() fn.
I wanted to ask : 1) Can I do the same with bitshift? If yes, How? 2) Is there any limit of pow() fn also?
Yes, use 1LL << 50
Oh right! Makes sense. Thanks :)
Somehow in the problem B I though that the maximum element in the array minus 0 equal 0 :T
What is the idea behind this solution of F
90126141
For Problem E, the matrix can also be
\end{array} $$$
when $$$n=6$$$, since the duck is at $$$(x,y)$$$ $$$\forall x,y\in [1,n]$$$, we can know the direction the duck walk to next step from the lowest bit of the sum of left problems.(Submission:90156663)
It's a really interesting constructive problem, thanks for preparing this awesome round. =)
Upsolved it this way:
Just follow the bits of the path sum to find the path. It was a really interesting problem and I regret not spending enough time on it during the contest.
I solved it this way for lets say 4*4 matrix the matrix is
1 2 4 8
0 0 0 16
4 8 0 32
0 16 0 64
See paths diagonally!
For I, KLPP could you please explain furthuer what does
However, some faces are not interesting, namely the 2×2 square of adjacent cells.mean? Sorry for my bluntness, but I'm just sort of threw out the track right here QAQ. Thanks in advance.2x2 squares of cells that either all have temperature >=x or temperature <x are faces of the graph, however, they do not correspond to any connected component, so we have to subtract them from the number of faces.
Thanks, I think I'm kind of gettig it right :)
Consider a face in, for example, the graph with vertices with temperatures >=x. You can see that this face is an area enclosed by vertices, which means that inside it there is a bad connected component or nothing(in the case of the 2x2 square). Let, for example, H represent cells with temperatures >=x and C otherwise:
HHHHH
HCCCH
HC CH
HCCCH
HHHHH
Here you can see that the face enclosed by the 'H' correspond to a bad connected component in the 'C'. However, in this particular case:
HH
HH
There is nothing inside, and thus it is not an interesting face. Sorry for my poor editing skills.
Oh, I think I've just realized what you mean the moment before you started to provide further explanation. So sorry for my stupid problem on understanding that formula. Anyway, thanks a million for your help, and it is a really educational and inspiring problem!
what should be the answer for question d in the case 1 6 RRRRRR
I think it should be 3 but most accepted codes print the answer 2
2 — RLRRLR
Or one of the two other possible rotations: LRRLRR, RRLRRL
"Fun fact: This problem was originally proposed as B"
It might have had 5k+ ACs then....lol
Can someone tell me why this solution 90172327 is wrong in problem C ? I loop on the numbers from the smallest and merge the equal numbers using DSU, so that they can be increased at the same time, and for each number I see the number to the left (after merging equal elements) if it was larger, then I need to increase that number, if the difference between the current number and the number on the right is smaller that between it and the number to the left, so I increase it to be equal to the number to the right
"Clearly, the order in which we perform the slides (transfers of one square meter of dirt from $$$a_j+1$$$ to $$$a_j$$$ for some $$$j$$$) does not matter." Why ? Can someone explain ?
Tlatoani
Please don't reply "random people"
In Problem C Editorial "Now let's look at the pair $$$a_j,a_{j+1}$$$. If $$$a_j≤a_{j+1}$$$ (or if j=n), applying an operation would not change ans". Does the equality $$${a_j}=a_{j+1}$$$ holds here?
My blog discusses the solution to 1392F - Omkar and Landslide if the original heights are non-decreasing instead of strictly increasing.
1 6 RLLLRR
why does this give 1
I solved H by brute-forcing for small $$$n,m$$$ and I found this formula
$$$f(n,m)=\frac{(m A_n + n!)(m+n+1)}{n!(m+1)}$$$,
where $$$A_n$$$ is A000254
For problem I,whats meaning of C1 and C2?Can anyone help me?
I think the connected components of graph 1 and 2?
For the proof of Problem F, the editorial details an argument which requires the fact that "the order of operations does not matter". It is actually hard to prove this, and even with this lemma, it is a long and convoluted way to prove.
I have a much simpler and intuitive proof!
First, a lemma:
The proof of this lemma is simplicity itself and is left as an exercise to the reader (it is really easy, I am not tricking you).
Now, for the sake of contradiction, let's say that we have as the final array a situation with more than one pair of equal elements. Because of the lemma, we can't have more than two consecutive equal elements. Now if the equal elements are as such
$$$a$$$ | $$$a$$$ | $$$a+1$$$ | $$$a+2$$$ | $$$a+3$$$ | $$$a+4$$$ | $$$a+4$$$
then we by going backwards, we can reach an impossible state (where the array is not non-decreasing), hence the contradiction.
And yeah, I use the fact that the array is always non-decreasing. It is also very easy to prove. (just use induction on iteration number).
can anyone explain reason behind the working of logic in problem c(https://mirror.codeforces.com/contest/1392/problem/C) in more detail by taking an example,im not understanding the editorial?
Notice that the last element of the array will be the maximum element in the end of all operaions, so increment the array elements from right to left of array.
for example in this test case:
45 3 2 51- a[3]<a[4] do nothing.
2- a[2]>a[3] increment the segment[3:n] by(a[2]-a[3]) ,now array =[5,3,3,6]
3-a[1]>a[2] increment the segment[2:n] by(a[1]-a[2]) ,now array =[5,5,5,8]
now total operations =3.
Here is my code ,it's very easy to understand it.
can anyone explain me problem 1392D - Omkar and Bed Wars