We hope you liked the problems! If you’re curious about the two different problem formats, initially Tlatoani, golions, qlf9 and I were working on Omkar 3 with antontrygubO_o while MagentaCobra was working on a separate round with isaf27. We eventually decided to join forces and combine the rounds, resulting in the current Omkar 3.
1536A - Omkar and Bad Story
Idea: rabaiBomkarBittalBang
Preparation: rabaiBomkarBittalBang, Tlatoani, qlf9
Consider what happens when $$$a$$$ contains a negative number.
We first claim that if any negative number exists in $$$a$$$, then no solution exists. Denote $$$p$$$ as the smallest number in $$$a$$$ and $$$q$$$ as another arbitrary number in the array (as $$$n \geq 2$$$, $$$q$$$ always exists). Clearly, $$$|q - p| = q - p > 0$$$. However, because $$$p$$$ is negative, $$$q - p > q$$$. As such, adding $$$q - p$$$ to the output array would create the pair $$$(q - p, p)$$$ with difference $$$q - 2p > q - p$$$. We have the same problem as before; thus, it is impossible to create a nice array if there exists a negative number in $$$a$$$.
After we deal with this case, we now claim that $$$b = [0, 1, 2, ..., 100]$$$ is a valid nice array for any $$$a$$$ that contains no negative numbers. It is easy to verify that this is a valid nice array. And since in this case, every element of $$$a$$$ is nonnegative and distinct, it is always possible to rearrange and add elements to $$$a$$$ to obtain $$$b$$$.
//DecimalFormat f = new DecimalFormat("##.00");
import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class OmkarAndBadStory {
public static void main(String[] omkar) throws Exception
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
StringBuilder sb = new StringBuilder();
int cases = Integer.parseInt(st.nextToken());
for(int i = 0; i < cases; i++)
{
solve(in, st, sb);
}
System.out.print(sb);
}
public static void solve(BufferedReader in, StringTokenizer st, StringBuilder sb) throws Exception
{
int k = Integer.parseInt(in.readLine());
String s = in.readLine();
st = new StringTokenizer(s);
boolean hasneg = false;
int max = 0;
int x;
int[] arr = new int[k];
for(int i = 0; i < k; i++)
{
x = Integer.parseInt(st.nextToken());
arr[i] = x;
if(x < 0)
{
hasneg = true;
}
else
{
max = Math.max(max, x);
}
}
if(hasneg)
{
sb.append("NO\n");
}
else
{
sb.append("YES\n");
sb.append((max+1)+"\n");
for(int i = 0; i < max; i++)
{
sb.append(i + " ");
}
sb.append(max+"");
sb.append("\n");
}
}
}
fun main() {
for (c in 1..readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val numberballs = readLine()!!.split(" ").map { it.toInt() }
if (numberballs.min()!! < 0) {
println("nO")
} else {
println("yEs")
println(numberballs.max()!! + 1)
println((0..numberballs.max()!!).joinToString(" "))
}
}
}
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("input.txt", "r", stdin);
int tst;
cin >> tst;
while (tst--) {
int n;
cin >> n;
bool f = false;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x < 0) f = true;
}
if (f) {
cout << "NO\n";
}
else {
cout << "YES\n";
cout << 101 << '\n';
for (int i = 0; i <= 100; i++) cout << i << " ";
cout << '\n';
}
}
return 0;
}
import Data.List (intercalate)
import Control.Monad (replicateM)
main = do t <- read <$> getLine
replicateM t solve
solve = do getLine
xs <- (map read . words) <$> getLine
putStrLn (if any (< 0) xs then "nO" else ("yEs\n101\n" ++ intercalate " " (map show [0..100])))
1536B - Prinzessin der Verurteilung
Idea: MagentaCobra
Preparation: MagentaCobra
Pigeonhole principle
What is the longest the answer can be?
Let’s brute force check all substrings of length <= 3 and print the lexicographically smallest one that doesn’t appear as a substring in the input. We can guarantee that we will come across the answer due to the pigeonhole principle. There are at most $$$n+n-1+n-2 = 3n-3$$$ possible substrings of length 3 or shorter in the input. There exist $$$26+26^2+26^3 = 18278$$$ total substrings of length 3 or shorter. It is impossible for the input to contain all $$$18278$$$ substrings, as $$$3n-3 < 18278$$$ for $$$n \leq 1000$$$.
Final runtime looks something like $$$O(18278n)$$$ or $$$O(n)$$$ depending on how you implement substring checking.
//stan hu tao
//come to K-expo!!!
//watch me get carried in nct ridin
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;
public class FischlPog
{
public static void main(String hi[]) throws Exception
{
ArrayList<String> ls = new ArrayList<String>();
for(int a=0; a < 26; a++)
ls.add(get(a)+"");
for(int a=0; a < 26; a++)
for(int b=0; b < 26; b++)
ls.add(get(a)+""+get(b));
for(int a=0; a < 26; a++)
for(int b=0; b < 26; b++)
for(int c=0; c < 26; c++)
ls.add(get(a)+""+get(b)+""+get(c));
Collections.sort(ls, (x,y) -> {
int len1 = x.length();
int len2 = y.length();
if(len1 != len2)
return len1-len2;
return x.compareTo(y);
});
//assume multitests exist
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());
String input = infile.readLine();
HashSet<String> substrings = new HashSet<String>();
for(int len=1; len <= 3; len++)
for(int i=0; i < N-len+1; i++)
substrings.add(input.substring(i, i+len));
for(int i=0; i < ls.size(); i++)
if(!substrings.contains(ls.get(i)))
{
sb.append(ls.get(i)+"\n");
break;
}
}
System.out.print(sb);
}
public static char get(int a)
{
return (char)(a+'a');
}
}
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val s = readLine()!!
for (length in 1..n) {
var mex = ""
var answer: String? = null
fun recur() {
if (mex.length == length) {
if (mex !in s) {
answer = mex
}
} else {
for (chara in 'a'..'z') {
mex += chara
recur()
if (answer != null) {
return
}
mex = mex.substring(0 until mex.lastIndex)
}
}
}
recur()
if (answer != null) {
println(answer)
break
}
}
}
}
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
void solve() {
int n;
string s;
cin >> n >> s;
set<string> se;
rep(i, 0, n) {
string ss;
for(int k = 0; k < 5 && i + k < n; k++) {
ss.push_back(s[i + k]);
se.insert(ss);
}
}
rep(len, 1, 6) {
string t(len, 'a');
while(true) {
if(se.count(t) == 0) {
cout << t << '\n';
return;
}
int idx = len - 1;
while(idx >= 0 && t[idx] == 'z') {
t[idx] = 'a';
idx--;
}
if(idx < 0) break;
t[idx]++;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
while(te--) solve();
}
import Data.List (intercalate, tails, isPrefixOf, head)
import Control.Monad (replicateM)
import Data.Maybe (fromJust, listToMaybe, catMaybes)
main = do t <- read <$> getLine
replicateM t solve
solve = do getLine
s <- getLine
putStrLn (leastNonSubstring s)
leastNonSubstring s = head $ catMaybes [leastOfLength l | l <- [1..]]
where leastOfLength l = helper "" l
helper prefix 0 | isSubstring prefix s = Nothing
| otherwise = Just prefix
helper prefix l = listToMaybe $ catMaybes [helper (prefix ++ [letter]) (l - 1) | letter <- ['a'..'z']]
isSubstring s t = any id (map (isPrefixOf s) (tails t))
1536C - Diluc and Kaeya
Idea: MagentaCobra
Preparation: MagentaCobra
Turn into geometry problem
Represent every prefix as $$$(x, y)$$$ point in cartesian plane where $$$x$$$ = frequency of ‘D’ and $$$y$$$ = frequency of ‘K’. Draw a polyline connecting these points in order of increasing length of prefix.
Draw a line from origin to point. What can we say about intersections of poly-line with this line?
For each prefix, label it with a pair $$$(a, b)$$$ where $$$a$$$ = frequency of ‘D’ in this prefix and $$$b$$$ = frequency of ‘K’ in this prefix. Divide $$$a$$$ and $$$b$$$ by $$$gcd(a, b)$$$. If we iterate over all prefixes from to left, we can notice that the answer for the prefix equals the # of occurrences of this pair we have seen so far! This can be visualized by drawing a poly-line as mentioned in the hints.
As for implementation, you can use a map in C++ or a HashMap in Java to achieve $$$O(n \log n)$$$ or $$$O(n)$$$ runtime.
//stan hu tao
//come to K-expo!!!
//watch me get carried in nct ridin
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;
public class DilucKaeyaModel
{
public static void main(String hi[]) 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)
{
st = new StringTokenizer(infile.readLine());
int N = Integer.parseInt(st.nextToken());
char[] arr = infile.readLine().toCharArray();
HashMap<String, Integer> map = new HashMap<String, Integer>();
int dc = 0;
int kc = 0;
for(char c: arr)
{
if(c == 'D')
dc++;
else
kc++;
int a = dc;
int b = kc;
if(a == 0)
b = 1;
else if(b == 0)
a = 1;
else
{
int gcd = gcd(a, b);
a /= gcd; b /= gcd;
}
String key = a+":"+b;
push(map, key);
sb.append(map.get(key)+" ");
}
sb.append("\n");
}
System.out.print(sb);
}
public static int gcd(int a, int b)
{
if(a > b)
{
int t = a;
a = b;
b = t;
}
if(a == 0)
return b;
return gcd(b%a, a);
}
public static void push(HashMap<String, Integer> map, String k)
{
if(!map.containsKey(k))
map.put(k, 1);
else
map.put(k, map.get(k)+1);
}
}
import java.util.*
fun main() {
repeat(readLine()!!.toInt()) {
readLine()
val freq = mutableMapOf<Pair<Int, Int>, Int>()
var d = 0
var k = 0
val joiner = StringJoiner(" ")
for (chara in readLine()!!) {
when (chara) {
'D' -> d++
'K' -> k++
}
val g = gcd(d, k)
val r = Pair(d / g, k / g)
freq[r] = (freq[r] ?: 0) + 1
joiner.add(freq[r]!!.toString())
}
println(joiner)
}
}
fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define DEBUG(...) 6
#endif
template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << s.substr(0, i) << " = " << x << " | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
pair<int, int> getRatio(int a, int b) {
int g = __gcd(a, b);
a /= g;
b /= g;
return {a, b};
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
int n;
string s;
cin >> n >> s;
int d = 0, k = 0;
map<pair<int, int>, int> mp;
for (char c : s) {
if (c == 'D') d++;
else k++;
cout << ++mp[getRatio(d, k)] << " ";
}
cout << "\n";
}
return 0;
}
import Data.List (intercalate)
import Control.Monad (mapM, replicateM)
import Data.Ratio ((%))
import Data.Map (empty, findWithDefault, insert)
main = do t <- read <$> getLine
replicateM t solve
solve = do getLine
s <- getLine
putStrLn (intercalate " " (map show (maxBlocks s)))
maxBlocks s = helper s empty 0 0
where helper "" _ _ _ = []
helper (c:s) prev d k = x : helper s prev' d' k'
where (d', k') | c == 'D' = (d + 1, k)
| c == 'K' = (d, k + 1)
r | k' == 0 = 69000000 % 1
| otherwise = d' % k'
x = (findWithDefault 0 r prev) + 1
prev' = insert r x prev
1536D - Omkar and Medians
Idea: rabaiBomkarBittalBang
Preparation: rabaiBomkarBittalBang, Tlatoani
For some $$$k<n$$$, assume $$$b_1, b_2, \cdots, b_{k}$$$ is the OmkArray of some $$$a_1, a_2, \cdots, a_{2k-1}$$$, and we want to see what values of $$$a_{2k}, a_{2k+1}$$$ we can add so that $$$b_1, b_2, \cdots, b_{k+1}$$$ is the OmkArray of $$$a_1, a_2, \cdots, a_{2k+1}$$$. Let $$$c_1, c_2, \cdots, c_{2k-1}$$$ be $$$a_1, a_2, \cdots, a_{2k-1}$$$ sorted in ascending order.
If $$$b_{k+1} \geq b_k$$$, note that $$$b_{k} = c_k$$$ and there are $$$k-2$$$ elements of $$$a$$$ $$$\geq c_{k+1}$$$, so no matter how large $$$a_{2k}, a_{2k+1}$$$ are there will be at most $$$k$$$ elements larger than $$$c_{k+1}$$$ in $$$a_1, a_2, \cdots, a_{2k+1}$$$. This gives $$$b_{k+1} \leq c_{k+1}$$$. We can use a similar argument to show $$$b_{k+1} \geq c_{k-1}$$$. Now we want to bound $$$c_{k+1}$$$ and $$$c_{k-1}$$$. Note that each distinct value among $$$b_1, b_2, \cdots, b_k$$$ must appear at least once in $$$a_1, a_2, \cdots, a_{2k-1}$$$. Therefore, if $$$i$$$, $$$j$$$ satisfy that $$$b_i$$$ is the largest value of $$$b_i\leq b_k$$$ and $$$i \neq k$$$, and $$$b_j$$$ is the smallest value of $$$b_j \geq b_k$$$, $$$j \neq k$$$, then we have $$$c_{k+1} \leq b_j$$$, $$$c_{k-1} \geq b_i$$$, and so $$$b_i \leq b_{k+1} \leq b_j$$$. If no such largest/smallest values exist, then we can assume $$$b_{k+1}$$$ is not bounded above/below.
Therefore, if $$$b$$$ has an OmkArray, it is necessary that for all $$$i$$$, there does not exist a $$$j\leq i$$$ such that $$$b_j$$$ is between $$$b_i$$$ and $$$b_{i+1}$$$, exclusive. I claim this is also sufficient. We can construct such an array $$$a$$$ using the following algorithm:
Let $$$a_1 = b_1$$$.
If $$$b_{i+1}=b_j$$$ for some $$$b_j<b_i$$$ with $$$j<i$$$, let $$$a_{2k-2}, a_{2k-1} = -\infty$$$ (we can replace $$$-\infty$$$ with some sufficiently small constant at the end of our array creation process).
Otherwise, if $$$b_{i+1}<b_i$$$ then let $$$a_{2k-2} = -\infty$$$, $$$a_{2k-1} = b_{i+1}$$$.
If $$$b_{i+1}=b_j$$$ for some $$$b_j>b_i$$$ with $$$j<i$$$, let $$$a_{2k-2}, a_{2k-1} = \infty$$$ (we can replace $$$\infty$$$ with some sufficiently large constant at the end of our array creation process).
Otherwise, if $$$b_{i+1}>b_i$$$ then let $$$a_{2k-2} = \infty$$$, $$$a_{2k-1} = b_{i+1}$$$.
Finally, if $$$b_{i+1} = b_i$$$, let $$$a_{2k-2} = -\infty$$$, $$$a_{2k-1} = \infty$$$.
This means that an equivalent condition to having an OmkArray is for all $$$i$$$, there does not exist a $$$j\leq i$$$ such that $$$b_j$$$ is between $$$b_i$$$ and $$$b_{i+1}$$$, exclusive. There are multiple ways to check this for an array $$$b$$$, but one clean way would be to keep some TreeSet $$$s$$$, and check if $$$b_{i+1}$$$ is between \t{s.ceil($$$b_i$$$)} and \t{s.floor($$$b_i$$$)} for all $$$i$$$, and then adding $$$b_{i+1}$$$ to $$$s$$$ if it is not already added.
//Praise our lord and saviour qlf9
import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class C{
public static void main(String[] omkar) throws Exception
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
StringBuilder sb = new StringBuilder();
int cases = Integer.parseInt(st.nextToken());
for(int i = 0; i < cases; i++)
{
solve(in, st, sb);
}
System.out.print(sb);
}
public static void solve(BufferedReader in, StringTokenizer st, StringBuilder sb) throws Exception
{
int n = Integer.parseInt(in.readLine());
int[] arr = readArr(n, in, st);
Node currNode = new Node(arr[0]);
int currVal;
Node temp;
for(int i = 1; i < n; i++)
{
currVal = arr[i];
if(currVal < currNode.value)
{
if(currNode.prev != null && currVal < currNode.prev.value)
{
sb.append("NO\n");
return;
}
if(currNode.prev == null || currNode.prev.value < currVal)
{
temp = new Node(currVal);
temp.prev = currNode.prev;
temp.next = currNode;
if(currNode.prev != null)
{
currNode.prev.next = temp;
}
currNode.prev = temp;
currNode = temp;
}
else
{
currNode = currNode.prev;
}
}
else if(currVal > currNode.value)
{
if(currNode.next != null && currVal > currNode.next.value)
{
sb.append("NO\n");
return;
}
if(currNode.next == null || currNode.next.value > currVal)
{
temp = new Node(currVal);
temp.next = currNode.next;
temp.prev = currNode;
if(currNode.next != null)
{
currNode.next.prev = temp;
}
currNode.next = temp;
currNode = temp;
}
else
{
currNode = currNode.next;
}
}
}
sb.append("YES\n");
}
public static int[] readArr(int N, BufferedReader in, StringTokenizer st) throws Exception
{
int[] arr = new int[N];
st = new StringTokenizer(in.readLine());
for(int i=0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
return arr;
}
static class Node
{
int value;
Node prev;
Node next;
public Node(int v)
{
value = v;
prev = null;
next = null;
}
}
}
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() {
val jin = BufferedReader(InputStreamReader(System.`in`))
val out = StringBuilder()
for (c in 1..jin.readLine().toInt()) {
val n = jin.readLine().toInt()
val tokenizer = StringTokenizer(jin.readLine())
var mid = tokenizer.nextToken().toInt()
val treeSet = TreeSet<Int>()
treeSet.add(Int.MIN_VALUE)
treeSet.add(mid)
treeSet.add(Int.MAX_VALUE)
var answer = true
for (j in 2..n) {
val next = tokenizer.nextToken().toInt()
if (next < treeSet.lower(mid)!! || next > treeSet.higher(mid)!!) {
answer = false
break
}
mid = next
treeSet.add(mid)
}
out.appendln(if (answer) "yEs" else "nO")
}
print(out)
}
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
const int maxN = 2e5 + 10;
int a[maxN];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("input.txt", "r", stdin);
int tst;
cin >> tst;
while (tst--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
set<int> s;
s.insert(a[1]);
bool ok = true;
for (int i = 2; i <= n; i++) {
int prv = a[i - 1];
if (prv != a[i]) {
if (prv < a[i]) {
auto it = s.upper_bound(prv);
if (it != s.end() && (*it < a[i])) {
ok = false;
break;
}
}
if (prv > a[i]) {
auto it = s.lower_bound(prv);
if (it != s.begin() && (*(--it) > a[i])) {
ok = false;
break;
}
}
}
s.insert(a[i]);
}
if (ok) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
import Data.List (intercalate)
import Data.Set (singleton, lookupLT, lookupGT, insert)
import Control.Monad (mapM, replicateM)
main = do t <- read <$> getLine
replicateM t solve
solve = do getLine
xs <- (map read . words) <$> getLine
putStrLn (if isOmkArray xs then "yEs" else "nO")
isOmkArray :: [Int] -> Bool
isOmkArray (x:xs) = helper xs x (singleton x)
where helper [] _ _ = True
helper (x:xs) prev allPrev | maybe False (x <) (lookupLT prev allPrev) || maybe False (x >) (lookupGT prev allPrev) = False
| otherwise = helper xs x (insert x allPrev)
1536E - Omkar and Forest
Idea: MagentaCobra
Preparation: MagentaCobra
Consider forcing some set of ‘#’ positions to be $$$0$$$ and the rest to be positive integers.
Multisource BFS
Imagine picking some subset of ‘#’ and making them $$$0$$$. Then there is exactly one way to make all the remaining ‘#’ positive integers. To see why, imagine multisource BFS with all $$$0$$$ as the sources. After the BFS, each ‘#’ will be equal to the minimum distance from itself to any $$$0$$$ cell. Difference between adjacent cells will be at most $$$1$$$. Proof can be shown by contradiction: if two cells with difference $$$\geq 2$$$ existed, then the larger of these cells is not labeled with the shortest distance to a source (since the distance from the smaller cell $$$+ 1$$$ will be a better choice). Because of the nature of BFS, we can also ensure the second condition is also satisfied, since the only cells that have no neighbor strictly smaller will be the source cells. This is the only valid assignment because if we make any number larger, there will exist a pair of cells with difference $$$\geq 2$$$. If we try to make any number smaller, there will exist a cell with positive karma that has no strictly smaller neighbor.
If we let $$$k$$$ equal to the frequency of ‘#’ in the input, then the answer is $$$2^k$$$. Keep in mind of the special case where the input is all ‘#’, in which case you have to subtract $$$1$$$. This is because a possible arrangement must contain at least one cell with karma of $$$0$$$.
Obviously the solution runs in $$$O(nm)$$$ time.
//Model Solution 2, uses fast expo
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.System.out;
import java.util.*;
import java.io.*;
import java.math.*;
public class OmkarAndForestModel2
{
static final long MOD = 1000000007L;
public static void main(String hi[]) 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)
{
st = new StringTokenizer(infile.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int cnt = 0;
for(int i=0; i < N; i++)
{
String row = infile.readLine();
for(char c: row.toCharArray())
if(c == '#')
cnt++;
}
long res = power(2, cnt, MOD);
if(cnt == N*M)
res = (res-1+MOD)%MOD;
sb.append(res+"\n");
}
System.out.print(sb);
}
public static long power(long x, long y, long p)
{
//0^0 = 1
long res = 1L;
x = x%p;
while(y > 0)
{
if((y&1)==1)
res = (res*x)%p;
y >>= 1;
x = (x*x)%p;
}
return res;
}
}
const val MOD = 1000000007L
fun main() {
for (c in 1..readLine()!!.toInt()) {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
var zeros = (1..n).sumBy{ readLine()!!.count { it == '0' } }
var answer = 1L
for (j in 1..(n * m) - zeros) {
answer *= 2L
answer %= MOD
}
if (zeros == 0) {
answer--
}
println(answer)
}
}
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int mod = (int)1e9 + 7;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("input.txt", "r", stdin);
int tst;
cin >> tst;
while (tst--) {
int n, m;
cin >> n >> m;
int ans = 1;
bool has =false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
cin >> c;
if (c == '0') {
has = true;
}
else {
ans = (2LL * ans) % mod;
}
}
}
if (has) {
cout << ans << '\n';
}
else {
cout << (ans - 1) << '\n';
}
}
return 0;
}
import Data.List (intercalate)
import Control.Monad (replicateM)
md x = mod x 1000000007
main = do t <- read <$> getLine
replicateM t solve
solve = do n:m:[] <- (map read . words) <$> getLine
free <- (sum . map (sum . map (\chara -> if chara == '#' then 1 else 0))) <$> replicateM n getLine
putStrLn $ show (if free == n * m then pow 2 free - 1 else pow 2 free)
pow :: (Integral a) => Integer -> a -> Integer
pow _ 0 = 1
pow x y = md $ x * (pow x (y - 1))
1536F - Omkar and Akmar
Idea: golions
Preparation: golions
Solve a simpler version of the problem, where you just need to print who would win if both players play optimally.
Consider the possible ending states of the board.
The 2nd player, Omkar, always wins no matter what either player does. The easiest way to see this is by considering ending states of the board. An ending state with an even number of letters means that the 2nd player wins (because the first player is the next player and there are no more moves), and an ending state with an odd number of letters means that the 1st player wins.
An ending state must be in the form ABABA... or BABA..., where there are 0 or 1 empty cells in between each letter and the letters form an alternating pattern. If there is more than 1 empty cell in between two cells, then a player will be able to play a letter, thus it is not a valid ending state.
If an ending state has two of the same letters next to each other, then it is not a valid ending state. Either they are next to each other, which is illegal, or there is at least one empty cell in between them, which means that a player can play the other letter in between.
Since the ending state must form an alternating pattern, there must be an even number of states. Thus, the 2nd player, Omkar, always wins.
Find the implication of the 2nd player always winning on the number of optimal games.
Because the 2nd player always wins no matter what, the number of optimal games basically means the total number of possible games.
Because of Hint 1 and Hint 2, we want to find the total number of possible games. This can be done by iterating over the number of moves and counting the number of ways to play a game with that number of moves.
We want to find the number of games that end in $$$x$$$ moves on a board of size $$$n$$$.
The first step is to calculate the total number of ending states. If $$$x=n$$$, the total number of ending states is just $$$2$$$ because you can either have ABABA... or BABAB...
Otherwise, a game that ends in $$$x$$$ moves will consist of $$$x$$$ letters, for example A|B|A|B|... where a | is a possible location of a single empty cell (there cannot be multiple empty cells next to each other or else it would not be a valid ending state). There are $$$x$$$ possible places where there can be an empty cell, and $$$n-x$$$ empty cells, so there are $$$\binom x {n-x}$$$ ways to choose places to put empty cells. Due to the circular nature of the board, you need to account for the case where the first cell on the board is an empty cell (the previous formula only works if the first cell is not empty). If you set the first cell to be empty, there are not $$$x-1$$$ possible places to put an empty cell and $$$n-x-1$$$ remaining empty cells, so you have to add $$$\binom {x-1} {n-x-1}$$$. Multiply the answer by $$$2$$$ to account for starting with an A or B.
Finally, multiply by $$$x!$$$ to account for all the ways you can reach each ending configuration.
Thus, if $$$x=n$$$, there are $$$2 \cdot x!$$$ optimal games, otherwise there are $$$2 \cdot (\binom x {n-x} + \binom {x-1} {n-x-1} ) \cdot x!$$$ optimal games.
Add up the number of games that end in $$$x$$$ moves for all even $$$x$$$ from $$$\lceil \frac{n}{2} \rceil$$$ to $$$n$$$, inclusive. Thus, the solution is $$$O(n)$$$.
//make sure to make new file!
import java.io.*;
import java.util.*;
public class OmkarAndAkmarSolution{
public static int MAXN = 1000005;
public static long MOD = 1000000007L;
public static long[] fac;
public static long[] ifac;
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());
fac = new long[MAXN];
ifac = new long[MAXN];
fac[0] = 1L;
ifac[0] = 1L;
for(int k = 1; k < MAXN; k++){
fac[k] = (fac[k-1] * (long)k + MOD)%MOD;
ifac[k] = modInverse(fac[k],MOD);
}
/*
ifac[MAXN-1] = modInverse(fac[MAXN-1],MOD);
for(int k = MAXN-2; k >= 0; k--){
ifac[k] = (ifac[k+1]*(long)(k+1) + MOD)%MOD;
}*/
int start = (n+1)/2;
if(start % 2 == 1) start++;
long answer = 0L;
for(int k = start; k <= n; k+=2){
long prod1 = 1L;
if(n-k>=1){
//doesn't do first skip
prod1 = choose(k,n-k);
//does first skip
prod1 = (prod1 + choose(k-1,n-k-1) + MOD)%MOD;
}
long prod2 = (prod1*2L + MOD)%MOD;
long prod3 = (prod2*fac[k] + MOD)%MOD;
answer = (answer + prod3 + MOD)%MOD;
}
out.println(answer);
out.close();
}
//a choose b, a!/(b!(a-b)!)
public static long choose(int a, int b){
long prod = (fac[a]*ifac[b] + MOD)%MOD;
long prod2 = (prod*ifac[a-b] + MOD)%MOD;
return prod2;
}
public static long modInverse(long a, long m)
{
long m0 = m;
long y = 0;
long x = 1;
if (m == 1)
return 0;
while (a > 1) {
// q is quotient
long q = a / m;
long t = m;
// m is remainder now, process
// same as Euclid's algo
m = a % m;
a = t;
t = y;
// Update x and y
y = x - q * y;
x = t;
}
// Make x positive
if (x < 0)
x += m0;
return x;
}
}
const val MOD = 1000000007L
fun main() {
val n = readLine()!!.toInt()
val factorial = LongArray(n + 1)
factorial[0] = 1L
for (j in 1..n) {
factorial[j] = (j.toLong() * factorial[j - 1]) % MOD
}
val invFactorial = LongArray(n + 1)
invFactorial[n] = factorial[n] pow -1
for (j in n - 1 downTo 0) {
invFactorial[j] = ((j + 1).toLong() * invFactorial[j + 1]) % MOD
}
fun choose(a: Int, b: Int) = if (b in 0..a) ((factorial[a] * ((invFactorial[b] * invFactorial[a - b]) % MOD)) % MOD) else 0L
var answer = 0L
for (k in 0..n step 2) {
answer += factorial[k] * (choose(k, n - k) + choose(k - 1, n - k - 1))
answer %= MOD
}
answer *= 2L
answer %= MOD
println(answer)
}
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
}
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int mod = (int)1e9 + 7;
int mult(int a, int b) {
return (1LL * a * b) % mod;
}
int sum(int a, int b) {
int s = a + b;
if (s >= mod) s -= mod;
return s;
}
const int maxN = 2e6 + 10;
int inv[maxN], fact[maxN], invfact[maxN];
int cnk(int n, int k) {
if (n < k || k < 0) return 0;
return mult(fact[n], mult(invfact[k], invfact[n - k]));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("input.txt", "r", stdin);
inv[1] = 1;
fact[0] = invfact[0] = fact[1] = invfact[1] = 1;
for (int i = 2; i < maxN; i++) {
inv[i] = mult(inv[mod % i], mod - mod / i);
fact[i] = mult(fact[i - 1], i);
invfact[i] = mult(invfact[i - 1], inv[i]);
}
int ans = 0;
int n;
cin >> n;
for (int moves = 0; moves <= n - 1; moves++) {
int spaces = n - 1 - moves;
int coef = cnk(moves + 1, spaces);
if (moves % 2 == 0) continue;
int fi = (moves + 1) / 2;
coef = mult(coef, fact[moves]);
// cout << coef << endl;
ans = sum(ans, coef);
}
ans = mult(ans, 2 * n);
cout << ans;
return 0;
}
import Data.List (reverse)
import Data.Array (listArray, (!))
chara = 1000000007
md x = mod x chara
main = do n <- read <$> getLine
putStrLn $ show (solve n)
solve n = md $ 2 * (sum (map (\k -> md (factorials!k * (choose k (n - k) + choose (k - 1) (n - k - 1)))) [0,2..n]))
where factorials = listArray (0, n) (reverse (helper n))
where helper 0 = 1:[]
helper n' = md (n' * f):fs
where fs@(f:_) = helper (n' - 1)
invFactorials = listArray (0, n) (helper 0)
where helper n' | n' == n = inv (factorials!n):[]
| otherwise = md ((n' + 1) * f):fs
where fs@(f:_) = helper (n' + 1)
choose a b | 0 <= b && b <= a = md $ factorials!a * (md (invFactorials!b * invFactorials!(a - b)))
| otherwise = 0
modPow :: (Integral a) => Integer -> a -> Integer
modPow _ 0 = 1
modPow x y = md $ (if even y then 1 else x) * modPow (md (x * x)) (div y 2)
inv x = modPow x (chara - 2)
Auto comment: topic has been updated by Tlatoani (previous revision, new revision, compare).
Problem E is very similar to 2013 USAJMO Problem 2.
Great contest,thanks.Especially love idea of C
I love the idea of C, too! It takes me many time to think of the solution, even longer than D.
Problem B
"*fanfare* You're been pranked." — Hu Tao
There should be a Bugaboo named "Omkar and hard contest"
The "editorial" for C is horrible, It doesn't explain anything
Maybe video is better but the text version sucks
main observatin is : lets say you want to cut a prefix in some parts, and lets say the ratio of each part is a : b, then if you sum up each part (and hence get the current prefix) then still the ratio of 'D' : 'K' remains same (a : b). So you just count the values from left to write and just count how many ratio so far you have equal to the current value, cuz the current ratio is the only ratio that is possible for each cut.
That's something I expected from the editorial
"Draw a line and notice" doesn't seem like a legit editorial to me. Editorial is supposed to give some intution. Don't know why I'm getting downvoted
Well thats the beauty of the community, many times downvoting/upvoting is random.
This helped me to develop the logic https://www.geeksforgeeks.org/split-the-binary-string-into-substrings-with-equal-number-of-0s-and-1s/
The above editorial Haskell implementation of Problem A : 1536A - Omkar and Bad Story — Omkar and Bad Story by Tlatoani is giving compilation error.
Hi, it seems like the spacing got messed up while putting it in the editorial. Haskell is very whitespace dependent. I'll try to fix it, but you can make it compile yourself by realigning the spacing.
It should be fixed now, thanks for letting me know.
Thanks.
Problem B solution with linear substring search can be easily optimized (and kotlin implementation has already done it) from $$$O(\Sigma^3\cdot n)$$$ to $$$O(n^2)$$$. The key idea is to generate all the strings (of lengths 1, 2, 3) in lexicographic order and check each of them immediately. The number of strings we have to check doesn't exceed $$$n$$$, therefore, time complexity is $$$O(n^2)$$$.
I'm sorry I didn't do CP in a while. Wouldn't your solution be O(t*n*n) which is O(10^9)? With the solution on the editorial you can get O(t*18000)
If I am not completely mistaken, my solution is $$$O(n^2)$$$ per testcase, $$$O(\sum\limits_{i = 1}^{t}n_i^2) \le O((\sum\limits_{i = 1}^{t}n_i)^2)$$$, so it would pretty fit in the time limit due to ($$$\sum\limits_{i = 1}^{t}n_i \le 1000$$$)
And editorial solution is $$$O(\sum\limits_{i = 1}^{t}n_i \cdot \Sigma^3)$$$, where $$$\Sigma = 26$$$ — the alphabet size. It isn't much worse than mine, but I decided to write about my trick here.
Ah right, I didn't see that part: "The sum of n over all test cases will not exceed 1000". Thanks.
I still think the solution in the editorial is better and is O(n), the one in C++ for example, but maybe I'm missing something
UPD: actually with that constraint on n I guess it actually doesn't matter
Ah, yes, C++ solution has better time complexity, you are right. The update about editorial complexity is wrong, so my initial comment is only about linear string search (whenever we want to check, whether one string is substring for another or not, we use simple search without any precalculations).
Thanks For
HintsandVideo Editorialsorz"If a is already nice, you don't have to add any elements." So if we print all the elements from 0 to 100 where did we check if the array given is already nice or not.
I used the concept of GCD to solve this and tell if it's already nice or not and then make changes if it isn't nice. Pls, tell is my approach incorrect or did I miss on something in the question?
You don't have to doesn't mean you can't.
Could you please elaborate on this? I am new to CP so I thought that this line meant that we had to check if the array is nice or not.
That line was given to confuse some people .That line means that its not necessary to always add some number. If you print all number between 0-100 then it does not matter whether your array was nice or not ,printed array will always be nice.
Alright, thanks for the explanation.
my solution of 'b' failed in the system test case just bcoz of a 'typo', now I and the person who didn't attempt the b is on the same page, nyc :(
hey apple
For problem C, there is a property of ratio: if a1/b1 = a2/b2
then a1/b1 = a2/b2 = (a1 + a2)/(b1 + b2).
Using this, for each prefix i just maintain the total occurrences of 'D' and 'K', and we get the only possible ratio in which we should partition the prefix. To the answer, add the occurrences of this particular ratio till i.
You didn't mention how it helps. It helps in following way. Suppose you want to have answer for prefix p. Then you have $$$(D_p, K_p)$$$ ratio. For any set of splits, for any cut at position $$$i$$$ using fact above you have $$$(D_i, K_i)$$$ same ratio. But it's easy to notice that if you didn't cut at any other place with same ratio, you can do it, because ratio to closest cuts is still $$$(D_p, K_p)$$$ using fact above, but rephrase it a bit: $$$a_1/b_1 = a_2/b_2 \rightarrow (a_1-a_2)/(b_1-b_2) = a_1/b_1$$$
What does it mean There are at most n+n−1+n−2=3n−3 possible substrings of length 3 or shorter in the input. in the editorial of problem B ?
There are $$$n$$$ substrings of length 1, $$$n-1$$$ substrings of length 2, and $$$n-2$$$ substrings of length 3.
In problem B, can you help why I got TLE ? Here is my submission: https://codeforces.net/contest/1536/submission/118685076
My basic idea : I created three sets (names are as follows one, two, three) each storing all possible strings of length (1,2 and 3) lexicographically. Then from the given string str I generated all strings of length 1,2 and 3 and stored all of them in another set called th
Then I iterated trough all elements of set th and if any of these strings stored in th, if found in set one, two or three, I deleted that element from that set (this means that such string is already there in the given string str thus I deleted from the set which contains it besides set th)
Lastly I checked if one isn't empty, the set of strings of size 1, then print
*one.begin().Else if two isn't empty, the set of strings of size 2, then print its
*two.begin().Else print
*three.begin().Although the solution contains the right ideas, I think the way it's implemented (using a set) is just too slow. The generation of all possible substrings using a set is 26 log 26 + 26^2 log 26^2 + 26^3 log 26^3, which is roughly 250,000. And you do this for every test case, regardless of how large/small n is, giving roughly 2.5 * 10^8 operations on initialization code alone.
Despite being suboptimal, admittedly, I might have guessed this would still pass. The timing might be close or I might also be missing something.
Tangentially: it would be helpful if the formatting was more consistent, specifically tabs/spaces, which render differently. Also, when iterating through the alphabet, it's helpful to use the character's literal value rather than memorizing magic numbers e.g.
for (char c = 'a'; c <= 'z'; c++).For problem F, you say there will be choose(x, n)-x ways to place the empty cells but I think it should be choose(x, n-x). Could you please check it out?
Thanks for the great round :D
Yes you are right, the error is fixed — thank you for letting us know!
Great to see one of my favorite YouTubers (MagentaCobra) help make some of these problems!
Glad to hear it! Hope you enjoyed the problems
I just noticed that many people forgot to print the value of k in the first bugaboo which made for a lot of
Wrong answer on pretest 1. I thought I was the only one :)Where does it say problem E must have at least one zero? (why do we need to subtract 1 if the grid only contains # ?)
There are no valid grids with no zeros.
Assume there is a valid grid with no zero. Then there exists a smallest number $$$x$$$ on this grid, with $$$x>0$$$. The problem states, that for each $$$x>0$$$ there has to be a neighbour strictly smaller than $$$x$$$. Contradiction, $$$x$$$ is already the smallest value!
Thanks, now I understand!
D looks kind of unsolveable to me. I don't see how I could ever get into a state in which I would be able to solve something like that.
What is the key point to find a solution? Randomly let the mind flow...somehow?
Idea: just check if $$$b_i$$$ is a valid median for each $$$i$$$ (by using information from the previous indices, like in dp). How does the array $$$a$$$ look like? You know that
Put this information together: $$$b_i$$$ should be close to the median of $$$a_1, \dots, a_{2i-3}$$$. More specifically, if $$$c$$$ is a sorted copy of $$$a$$$, $$$c_{i-2} \leq b_i \leq c_i$$$. This means that it's impossible to have $$$b_j$$$ between $$$b_{i-1}$$$ and $$$b_i$$$ ($$$j < i-1$$$).
I got to the solution after trying out all the samples and coming to these key observations.
Now consider the sorted array $$$a_1, .. , a_i, .. ,a_n$$$ and $$$a_i$$$ is the median and we can need the new median to be $$$x$$$. Once we add x (and something else) to a, $$$x$$$ is placed at right if $$$x>a_i$$$ or left if $$$x<a_i$$$ in sorted array.
Now from the observations it should be fairly obvious that for x to be median, it has to be immediately left or right of $$$a_i$$$ in the sorted array, and for that to happen there should be NO element that occurs in between $$$a_i$$$ and $$$x$$$ and this is exactly the solution.
Is it always necessary, when we add a new element of
bwhich isx, to be a new element? Can'txbe an old element ofa?Yes, it can. If you consider the case where $$$x>a_i$$$ and x already occurs previously, it just means that there is already an element x immediately to the right of median $$$a_i$$$, in this case adding any 2 elements $$$>=x$$$ would make x the new median.
Just to make sure that I've understood well, it's a MUST to remove the duplicates from array
aright? Otherwise those duplicates would block some other new x to be median..I didn't get you. We dont remove anything anytime. for each element of b we pass, we add 2 elements to a
I mean like if,
b = 2,2,...... so onrather than
a = [. . 2 2 . . .],this would be better right?
a = [. . . 2 . . .]*Supposing dot to the left as negative infinity and dot to the right as positive infinity
Using the previous occurrence of median if available rather than again adding same value in the array a.
So my question now is, are there any edge cases where it would fail if we don't do this..
Yes, using the previous value would be better if it exists. And yes if we add the same value again, there might be cases it fails because median can only move one spot. So while building array a, it might be a good idea to add (x,+-inf) if x doesnt exist or else (+-inf,+-inf) if x already exists.
But in the problem, we dont care about the construction of array a itself.
Yeah! Thank you very much. Your answer made the problem seem so much simpler!
congrats for reaching Expert..you are quite active in comments, so I know you
Luckily , the people who did A in brute force has passed the system tests.If test 32 was added before the main tests i am sure that many people have got TLE. Great luck for the people:))
Bruteforce solution is working: 118671903. 1) You should use unordered_* structures (default map/set will fail 118656942). 2) Your code of bruteforce solution is not optimal: at each iteration you create new array newV and copy it (you can modify one vector, which you have read), do not use endl (use '\n' -- it works faster), freq[t]++ -> frec.insert({t, 1}) (we have distinct integers), freq[absdiff]++ -> frec.insert({absdiff, 1}) (we don't have absdiff in map), if (freq[absdiff] == 0) -> if (freq.find(absdiff) == freq.end()), use int instead of long long where you can (int works faster), use [] instead of at ([] works faster)...
Unordered Structures have the complexity of O(n) in the worst case.
thank you for the video editorial. would be great if this was present for all contests
Can anyone tell what is the best method to generate strings like a,b,c.....z,aa,ab,ab.....az,ba,bb..... and so on in problem B and store in a vector? What is the easiest method? Please share your piece of code
You can check this 118663531. Here, complexity of convert_int2string(int n) is log_26(n).
I did iterate the length of the string, then foreach len I start with a new "aa..".
Then use an increment method with virtually O(1) like this:
Submission
For B, can anyone please tell why I'm getting wrong output in codeforces but correct in other IDEs? (Lang: Java)
Ideone: https://ideone.com/UZYIEW
Codeforces: 118692722
You assume Unix-style line-endings. In Unix there is only
\nin line ending. But in codeforces for some reason\r\n. Thus, when you read number it stops at\rand when you read string you get empty string because it read\nstraight ahead.golions can you please link this tutorial to the actual contest page materials ?
I think B ratings has to be 1000 Or less not 1200 because simple brute force O(n^3) was also working so i dont see a reason it is of 1200 rating
I used BFS for problem B :)))
The problems are full of some cool observations and thinking, and I enjoy it a lot. Especially pD though I couldn't figure it out in the round :D
BTW the video explanation is easy to understand compared to only texture explanation, I love it!
I think implementation of D using coordinate compression and sum segtree is more elegant.
If we have
arr[i] = a, anda[i+1] = b, thensegtree.sum(a+1, b-1)should be zero. If its false then answer is"NO", otherwise we dosegtree.add(a, 1).-10^9, 10^9, its big range for segtree, but we can simply compress it.
Can someone share any tips on how to understand editorials?
I think a difficult thing about editorials is that you're required to give a formal proof which might not give insight about how to solve the problem. For example, for D and E the proofs probably take longer than the problems themselves, since there are some nontrivial steps in the proofs that aren't really required to solve the problem (I had no idea how to prove my solution for E was correct when I solved it, as my thought process had to do with visualizing what grids looked like and I "felt" my solution was correct rather than having 100% confidence). I think a better way to get an idea of what motivation actually goes into solving a problem is by watching video solutions, as people good at explaining problems typically also explain their thought process. I wasn't involved with making the video solutions for this contest so I'm not sure how much they speak about motivation, but you could try those out, and then if you still don't understand there are countless others on Youtube.
Thank you for your advice!
If you don't understand something, at least ask questions.
C video Editorial is very nice
In Problem B, I mindlessly used the below piece of code to store all the substrings in a set which I think is O(n^3), right? Then why didn't my submission got TLE?
s is the input string!!
It is n^3, but I assume the constant is relatively small
If you count all the characters in all the substrings, that's on the order of (n^3 / 6). Given that n <= 1000, we have some very feasible number of operations, at least for c++
I'm more curious whether it is possible to hack it with MLE. It should be I believe
Why my solution for D is Giving Time limit Exceeded.I guess it taking linear time only. Please help https://codeforces.net/contest/1536/submission/118686508
vector<int>is not some kind of magic. If you insert into beginning it will take time of order of vector size, if you insert in the middle, it will take size/2. Just because it needs to move ahead every element from place where new element will be inserted.Problem A is lame tbh
Why? Very decent problem
I think for 1536C - Diluc and Kaeya complexity should be $$$O(n \log n)$$$ in both cases. Otherwise how do we get gcd(a,b) in $$$O(1)$$$?
AC Submission, I did it without using
gcd, instead I useddouble(except x/0) for ratio, and on top of it I useddoubleas key forunordered_map. I did this for the first time and to my surprise got AC! Using double can cause some computation error, right? And can we even use double as key for hashmap?I don't know what kind of comparison it use under hood, but I guess two double is treated equal if their binary representation is identical. And, looks like there is no n/m, n'/m' which is close enough (around 1e-14) to make them round to same double. (double can't store number precise so it has to be rounded) From top of my head I can guess only pair (1e5-1)/1e5 and (1e5-2)/(1e5-1) with difference around 1e-10, not even mention that this ratio is not allowed within problem restrictions.
Oh sorry, it's actually allowed. I had wrong restriction on $$$n$$$ in my mind.
Please check these two Submissions for Problem 'C' :-
1.) https://codeforces.net/contest/1536/submission/118643260
2.) https://codeforces.net/contest/1536/submission/118699081
Logic is same in both but in 1st submission, I used ratio (in double) as key and in 2nd, I used pair as key of unordered map.
1st one got accepted but 2nd one is giving TLE.
Please Check them ...
In Problem C, I am getting wrong answer on the 9th number for the first 9 character prefix of the string
the substring is KKKDDKDKK
It contains 3 Ds and 6 Ks. Jury's answer says 2.
How can it be divided into 2 partitions??
KKKDDKDKKThis contest's sytle is so strange than others.Almost every problem I had to find the law behind the title ,it's very easy if we find the law ,but if we cann't find the law ,it's very puzzling!...
in problem 2 substring of length two is sufficient right?? since 26*26> 1000
lol.. 26*26 < 1000 ..
damn math ;)
C question approach was damm good
Maybe something wrong has happened to Problem tags of Problem F...
chinese remainder theorem combinatorics constructive algorithms fft games geometry math meet-in-the-middle string suffix structures *2600
Consider the line
re = *(upper_bound(vals.begin(), vals.end(), cur));and the line usingre = *vals.upper_bound(cur);wherevalsis astd::set. The first one TLEs and the second one passes well under the TL. The submission links are : AC submission and the TLE submissionThe "1536C — Diluc and Kaeya", I have tried solving using GoLang and getting TLE but the same solution in CPP succeed. Is the recommendation is to not use CPP or have I missed something in this GOLang code.