Here is the editorial. Please provide your feedback on each problem so that we can improve upon them the next time.
1670A - Профессор Слим
Tutorial
Tutorial is loading...
Solution
import java.io.*;
import java.util.StringTokenizer;
public class A {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
int tc = sc.nextInt();
for (int test = 1; test <= tc; test++) {
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt();
int i = 0, j = 0;
while (i < n) {
if (arr[i] < 0) {
arr[j++] *= -1;
arr[i] *= -1;
}
i++;
}
if (isSorted(arr)) {
pw.println("YES");
} else
pw.println("NO");
}
pw.flush();
}
private static boolean isSorted(int[] arr) {
for (int i = 1; i < arr.length; i++)
if (arr[i] < arr[i - 1])
return false;
return true;
}
static class Scanner {
BufferedReader br;
StringTokenizer st;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(FileReader f) {
br = new BufferedReader(f);
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public int[] nextIntArr(int n) throws IOException {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(next());
}
return arr;
}
}
}
1670B - Общажные войны
Tutorial
Tutorial is loading...
Solution
import java.io.*;
import java.util.StringTokenizer;
public class B{
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
int tests = sc.nextInt();
for (int test = 0; test < tests; test++) {
int n = sc.nextInt();
char[] arr = sc.next().toCharArray();
int k = sc.nextInt();
boolean[] special = new boolean[26];
for (int i = 0; i < k; i++)
special[sc.next().charAt(0) - 'a'] = true;
int idx = -1;
for (int i = 0; i < n; i++)
if (special[arr[i] - 'a'])
idx = i;
int max=0;
for(int i=idx-1;i>=0;i--){
int j=i;
while (j>0&&!special[arr[j]-'a'])
j--;
max=Math.max(max,i+1-j);
i=j;
}
pw.println(max);
}
pw.flush();
}
public static class Scanner {
StringTokenizer st;
BufferedReader br;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(String s) throws FileNotFoundException {
br = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
}
}
1670C - Где пицца?
Tutorial
Tutorial is loading...
Solution
import java.io.*;
import java.util.HashSet;
import java.util.StringTokenizer;
public class C{
static int mod = (int) 1e9 + 7;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
int tests = sc.nextInt();
for (int test = 0; test < tests; test++) {
int n = sc.nextInt();
int[] first = new int[n];
int[] second = new int[n];
int[] third=new int[n];
for (int i = 0; i < n; i++)
first[i] = sc.nextInt() - 1;
for (int i = 0; i < n; i++)
second[i] = sc.nextInt() - 1;
for(int i=0;i<n;i++)
third[i]= sc.nextInt()-1;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++)
uf.unionSet(first[i], second[i]);
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < n; i++)
set.add(uf.findSet(i));
for(int i=0;i<n;i++){
if(third[i]==-1)
continue;
set.remove(uf.findSet(third[i]));
}
int pow = 0;
for (int x : set)
if (uf.sizeOfSet(x) > 1)
pow++;
int ans = 1;
for (int i = 0; i < pow; i++)
ans = (int) ((2L * ans) % mod);
pw.println(ans);
}
pw.flush();
}
public static class UnionFind {
int[] p, rank, setSize;
int numSets;
public UnionFind(int N) {
p = new int[numSets = N];
rank = new int[N];
setSize = new int[N];
for (int i = 0; i < N; i++) {
p[i] = i;
setSize[i] = 1;
}
}
public int findSet(int i) {
return p[i] == i ? i : (p[i] = findSet(p[i]));
}
public boolean isSameSet(int i, int j) {
return findSet(i) == findSet(j);
}
public void unionSet(int i, int j) {
if (isSameSet(i, j))
return;
numSets--;
int x = findSet(i), y = findSet(j);
if (rank[x] > rank[y]) {
p[y] = x;
setSize[x] += setSize[y];
} else {
p[x] = y;
setSize[y] += setSize[x];
if (rank[x] == rank[y]) rank[y]++;
}
}
public int numDisjointSets() {
return numSets;
}
public int sizeOfSet(int i) {
return setSize[findSet(i)];
}
}
public static class Scanner {
StringTokenizer st;
BufferedReader br;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(String s) throws FileNotFoundException {
br = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
}
}
1670D - Очень подозрительно
Tutorial
Tutorial is loading...
Solution
import java.util.*;
import java.io.*;
public class D{
public static void main(String[] args) throws Exception {
int t=sc.nextInt();
while(t-->0) {
pw.println(sol(sc.nextInt()));
}
pw.close();
}
public static int sol(int n) {
int low=0;
int high=(int)1e9;
int mid=(low+high)/2;
while(low<=high) {
if(calc(mid)<n) {
low=mid+1;
}else {
high=mid-1;
}
mid=(low+high)/2;
}
return low;
}
public static long calc(long n) {
n--;
long ans=0;
ans=(n/3)*(n/3)*3;
for (int i = 0; i <= n % 3; i++)
ans += (n / 3) * 2 + i;
return ans*2;
}
static class Scanner {
StringTokenizer st;
BufferedReader br;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(FileReader r) {
br = new BufferedReader(r);
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public String nextLine() throws IOException {
return br.readLine();
}
public double nextDouble() throws IOException {
String x = next();
StringBuilder sb = new StringBuilder("0");
double res = 0, f = 1;
boolean dec = false, neg = false;
int start = 0;
if (x.charAt(0) == '-') {
neg = true;
start++;
}
for (int i = start; i < x.length(); i++)
if (x.charAt(i) == '.') {
res = Long.parseLong(sb.toString());
sb = new StringBuilder("0");
dec = true;
} else {
sb.append(x.charAt(i));
if (dec)
f *= 10;
}
res += Long.parseLong(sb.toString()) / f;
return res * (neg ? -1 : 1);
}
public long[] nextlongArray(int n) throws IOException {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
public Long[] nextLongArray(int n) throws IOException {
Long[] a = new Long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
public int[] nextIntArray(int n) throws IOException {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
public Integer[] nextIntegerArray(int n) throws IOException {
Integer[] a = new Integer[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
public boolean ready() throws IOException {
return br.ready();
}
}
static Scanner sc = new Scanner(System.in);
static PrintWriter pw = new PrintWriter(System.out);
}
1670E - Хемос на дереве
Tutorial
Tutorial is loading...
Solution
import java.util.*;
import java.io.*;
public class E{
static ArrayList<int[]>[] adj;
static int[] nodeval, edgeval;
static int count, N;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
N = 1 << n;
adj = new ArrayList[N];
for (int i = 0; i < N; i++)
adj[i] = new ArrayList<>();
for (int i = 0; i < N - 1; i++) {
int u = sc.nextInt() - 1;
int v = sc.nextInt() - 1;
adj[u].add(new int[]{v, i});
adj[v].add(new int[]{u, i});
}
nodeval = new int[N];
edgeval = new int[N];
nodeval[0] = N;
count =0;
dfs(0, -1);
pw.println(1);
for (int i = 0; i < N; i++)
pw.print(nodeval[i] + " ");
pw.println();
for (int i = 0; i < N - 1; i++)
pw.print(edgeval[i] + " ");
pw.println();
}
pw.close();
}
private static void dfs(int u, int p) {
for (int[] nxt : adj[u]) {
int v = nxt[0];
int idx = nxt[1];
if (v == p)
continue;
count++;
edgeval[idx] = count + ((nodeval[u] & N) != 0 ? N : 0);
nodeval[v] = count + ((nodeval[u] & N) != 0 ? 0 : N);
dfs(v, u);
}
}
static class Scanner {
BufferedReader br;
StringTokenizer st;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(FileReader f) {
br = new BufferedReader(f);
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public int[] nextIntArr(int n) throws IOException {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(next());
}
return arr;
}
}
}
1670F - Джи, видишь?
Tutorial
Tutorial is loading...
Solution
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class F {
static final int mod = (int) 1e9 + 7;
static int n;
static long l, r, z;
static long[][] memo;
static long[][] memo2;
public static long nCr(int n, int r) {
if (r == 0)
return 1;
if (n == 0)
return 0;
if (memo[n][r] != -1)
return memo[n][r];
return memo[n][r] = (nCr(n - 1, r) + nCr(n - 1, r - 1)) % mod;
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
PrintWriter pw = new PrintWriter(System.out);
int tests = 1;
memo = new long[1001][1001];
for (long[] x : memo)
Arrays.fill(x, -1);
for (int test = 0; test < tests; test++) {
n = sc.nextInt();
l = sc.nextLong();
r = sc.nextLong();
z = sc.nextLong();
long ans = (compute(r) - compute(l - 1) + mod) % mod;
pw.println(ans);
}
pw.flush();
}
private static long compute(long val) {
memo2 = new long[61][2001];
for (long[] x : memo2)
Arrays.fill(x, -1);
return dp(60, 0, val);
}
private static long dp(int idx, int rem, long val) {
if (rem > 2000)
rem = 2000;
if (rem < 0)
return 0;
if (idx == -1)
return 1;
if (memo2[idx][rem] != -1)
return memo2[idx][rem];
long ans = 0;
int currentBitXor = (z & 1L << idx)== 0 ? 0 : 1;
for (int i = currentBitXor == 1 ? 1 : 0; i <= n; i += 2) {
int currentBitSum = (val & 1L << idx) == 0 ? 0 : 1;
int nextRem = 2 * (rem + currentBitSum - i);
long toAdd = (nCr(n, i) * dp(idx - 1, nextRem, val)) % mod;
ans = (ans + toAdd) % mod;
}
return memo2[idx][rem] = ans;
}
public static class Scanner {
StringTokenizer st;
BufferedReader br;
public Scanner(InputStream s) {
br = new BufferedReader(new InputStreamReader(s));
}
public Scanner(String s) throws FileNotFoundException {
br = new BufferedReader(new InputStreamReader(new FileInputStream(s)));
}
public String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
}
}
Feed back for C: While giving problems which require answer modulo p. Its good to provide 1 sample test where answer is greater than p so that we can understand that mod was wrong.
In this particular problem the size of the array should have been at least 30 in order to have an answer that exceeds 1e9 + 7, this seems too large for samples.
can you provide c++ solutions?
Yeah they should provide code in atleast in 2 languages , just saying . Btw they have explained the editorial very clearly ... Thanks a lot guys.
My solution for Problem C shouldn't this give TLE because of memset, if t = 1e5?
Hacked :)
I won't lose rating right? :'(
Yeah
My feedback on each problem
A simple solution for D problem without binary search, exploiting the fact that for 3 types of lines the numbers should be as close as possible (+-1 difference)
Can someone please explain to me that why my solution is getting "time limit exceeded"? 156095877
I was facing the exact same issue. TLE on pretest 3. In fact, changing lookup to O(1) didn't fix it either.
This problem has quite a huge input (3e5 lines) and output (1e5 lines) and output (1e5 lines)
It seems it won't pass without optimizing on this level
Lookup fast io in python or pypy
For D somehow this works
I was lucky to have found a similar formula and submit during contest.
I am surprised this is not the solution used in the editorial.
Video Solutions for C,D,E
Watched your previous videos, they are really good
Thanks :) I really appreciate the feedback.
A great contest, thanks to the writers :)
I was really close to solving problem E during the contest. At first, I tried several approaches to choosing the root node, for instance, I have considered the node which is on the diameter of the tree, or the one which has the largest degree. But neither of them work.
I completely fell into the trap of this problem, since it asks to select one node as the root, and I believe that the root node must have some special properties, which should be the "key" to the final solution.
It is like 10 minutes before the end, I realized that we could always construct the tree to obtain "n" as the answer. I noticed that, except for "100..00", the other values could be divided into (n-1) pairs, (1xxx,0xxx), (1yyy,0yyy), and so on. We could always make the prefix XOR be less than or equal to "10000".
It is a pity that I didn't finish the codes before the end, but this problem is really exciting, especially that "trap". Hope that next time I could do better.
In editorial of D: In second para "Number of intersections" should be "number of intersections at center of some hexagon" as intersection on some vertex won't create any triangle
yes it is number of intersections in the middle of hexagon.
You're right, fixed.
My solution for C without using dsu https://codeforces.me/contest/1670/submission/156098315
C++ solution for C (also without DSU): 156119537
Could you pls explain your soln?
Can someone pls explain F a bit more (last line of third para "we only have to know the difference between the previous bits of X (add 1 if the current bit is on) and the sum of the generated bits.") I am unable to get it from the editorial.
thanks in advance.
I still don't get it now. Could anyone please explain it?
I don't like the editorial for A
First it gives a claim without proof Then it has a solution that doesn't directly use this claim at all
"So let's say the number of negative elements is k. Then we must check that the first k elements are non-increasing and the remaining elements are non-decreasing." Why is it true? How does the solution use this fact?
Notice that applying the operations doesn't change number of negative elements. When sorted all the negative elements should be before all the positive elements. So if there are k negatives then we need to make the first k elements negative. For negative numbers to be sorted the absolute values must be non increasing. For positive numbers it should be non decreasing.
can anyone explain why the code for the C question is getting WA on test case 8?
https://codeforces.me/contest/1670/submission/156185766
approach: if c[i] != 0 then c[i] = a[i] or b[i], but in front, we should not count a cycle that has a[i] or b[i], because we don't have any option, for this I am storing the values that cannot count in cycles in a set container.if(a[i] == b[i]) then also I inserted a[i] in the set. and while checking for no. of connected components I am checking whether the parent of i from 1 to n does not belong in the set.
Yes I know, I made my approach messy using a set, I can use a visited array instead, but in the contest, this approach got stuck in my mind, and cannot able to change it...but I wanted to know the reason why my approach is wrong...
You're only checking the root is not in s. You need to make sure none of the children are in s as well.
what's wrong with my solution for (B). It says time limit exceeded on test 35.
include <bits/stdc++.h>
using namespace std; int main() { long long t; cin>>t; while(t--) { char ch; long long arr[26]={0},n,val,max=0,ind,k,i,flg=0; cin>>n; string s; cin>>s>>k; while(k--){ cin>>ch; arr[ch-'a']=1; } for(i=0;i<n;i++) { if(arr[s[i]-'a']==1) { if(flg==0) {max=i;flg=1;} else if(i-ind>max) max=(i-ind); ind=i; } } cout<<max<<"\n"; } }
https://codeforces.me/blog/entry/102579?#comment-909927
Can someone explain how https://codeforces.me/contest/1670/submission/156198034 this solution can not pass ?
Reading input is taking lot of time. Add these lines at beginning of main.
For understanding what this actually does, see -is-this-fft-'s comment.
Again, such claims have to be proven
NVM. Figured it out
You can’t use the parent array directly, use the find function instead.
Yeah, just figured it out. Thanks :)
can any one explain solution of problem d ?? i didn't understand the editorial!
Which part you did not understand?
Instead of using pen and paper, You can download a hexagonal graph paper and use sketch.io for better clarity
can someone check my solution for problem B? Im getting a TLE at 35th test case.
here is your accepted code just add this line ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); it make your io operations fast as in this problem t<=10**5 which is large.
can someone help me with my solution to problem C, I'm getting TLE 156607712
here is your accepted code the modifications are the following:
max size of arrays vis and adj should be 10**5+1 not 10**5 only since you use 1-based index
don't print pow(2,k) without modulus ,instead do this
3.the cause of TLE is that you clear adj at every test case which is very time consuming so clear only n size portion from adj
Now I see, thank you, I really appreciate
In D, the triangle counts when more lines are added optimally result in the series $$$0+0+2+4+4+6+8+8+10+12+12+14+...$$$ Which includes all non-negative even numbers, where every other even number appears twice.
With $$$n-1$$$ as the number of lines and $$$k = \lfloor{\frac{n}{3}}\rfloor$$$, the triangle count from optimal placements can be represented using the formula:
$$$\frac{k\times (2 + 4k - 2)}{2} + 4k(1 + k) - 4k(2-n\% 3)$$$
Which can be simplified into:
$$$6k^2 + 4k(n\% 3 - 1)$$$
This expression can then be binary searched to find the first evaluation greater than the input.
For problem F, there is a slightly different way to implement that I think is conceptually easier and less error prone.
If $$$r$$$ was smaller, then we could always have a $$$dp[bit][x]$$$, where $$$dp[bit][x]$$$ represents the number of ways to ensure the bitwise xor is the first $$$bit$$$ bits of $$$z$$$ and our sum is $$$\le x$$$. As for transitions,
where $$$b$$$ is our bit in the $$$bit$$$ th position.
Now the problem is that $$$r$$$ states is just way too much. So what we can do is notice that $$$x \gt 2^{bit + 1} \cdot n$$$, then we set it to be $$$2^{bit + 1} \cdot n$$$.
In problem D there is an O(1) solution: for each n, the solution is
Put the hexagon map into Oxy plane. Let a, b, c respectively be the numbers of lines that are parallel to Ox; creating a $$$60$$$ degree angle with Ox; and creating a $$$-60$$$ degree angle with Ox, for a total of $$$(a + b + c)$$$ lines. It is easy to see that the maximum number of triangles that can be created is $$$2 \cdot (ab+bc+ca).$$$ It asks us to find $$$ min (a + b + c).$$$
Because we can create $$$2 \cdot (ab+bc+ca)$$$ triangles,
must suffices. By Cauchy inequality, we also have
It follows that
Because a+b+c is an interger, our solution is
Can you explain how you got $$$a+b+c≥\sqrt{\frac{n∗3}{2}}$$$ from the inequality before it?
Sorry I typoed a lot. My edit should clarify thing.