Разбор Технокубок 2021 — Отборочный Раунд 2 (Codeforces Round 687 Div.1, Div.2)

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
20:57:02
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

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

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Разбор Технокубок 2021 — Отборочный Раунд 2 (Codeforces Round 687 Div.1, Div.2)

Автор KAN, 4 года назад, По-русски

Tutorial is loading...

Разбор задач Технокубок 2021 - Отборочный Раунд 2

Разбор задач Codeforces Round 687 (Div. 1, основан на Отборочном раунде 2 Технокубка 2021)

Разбор задач Codeforces Round 687 (Div. 2, основан на Отборочном раунде 2 Технокубка 2021)

technocup, технокубок, технокубок 20201

+182

KAN
4 года назад
76

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

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

ezir

4 года назад, # |

+26

Good!

→ Ответить

ThoughtNerd

4 года назад, # ^ |

-6

Why?

→ Ответить

heath_cliff

4 года назад, # |

For problem Div2 E, 99886275 is just so cool.

→ Ответить

Priyanshu14_

4 года назад, # |

Thank You.

Nice Problemset — problems were to the point and good.

I really liked it.

→ Ответить

Feng

4 года назад, # |

I used dictionary tree to passed the div2 D, I can guarantee its correctness, but I can't guarantee its time complexity,can anyone hack my solutions? https://codeforces.me/contest/1457/submission/99900717

→ Ответить

notAnAltAccount

4 года назад, # |

In Div2D, why is n<=60 if the given condition is true?

→ Ответить

epsilon_573

4 года назад, # ^ |

Because if n>60 , We can always find a contiguous triplet (a,b,c) such that a > b^c.

→ Ответить

Kofta

4 года назад, # ^ |

Why we can always find that?

→ Ответить

C137

4 года назад, # ^ |

← Rev. 3 →

In case $$$n > 60$$$ There will be three numbers $$$(a, b, c)$$$ all having the same msb (Most Significant Bit) set to 1. You can do one operation with numbers $$$b, c$$$ this will turn off the msb therefore $$$ a > (b \oplus c)$$$.

→ Ответить

Kofta

4 года назад, # ^ |

Thanks

→ Ответить

EugeneJudo

4 года назад, # ^ |

← Rev. 2 →

Because a_i <= 10^9 ~ 2^30. So of numbers which are k digits long in binary, we can have at most 2 to not get a triplet. And there are only 30 different sizes before we hit the cap of 10^9.

edit: I may have answered the wrong question

→ Ответить

Kofta

4 года назад, # ^ |

Thanks

→ Ответить

JNU_dh_AK_WF

4 года назад, # ^ |

← Rev. 2 →

Because these three numbers share the same highest bit $$$1$$$. And $$$1 \oplus 1=0$$$. Let's consider these three numbers as $$$a,b,c$$$ where $$$a<b<c$$$ , then the highest bit will become $$$0$$$ after we do $$$b \oplus c$$$, so $$$a > b \oplus c$$$ holds. Then we can always find that.

→ Ответить

Kofta

4 года назад, # ^ |

Thanks

→ Ответить

minhcool

4 года назад, # |

+52

Me when doing normal rounds: So I will try to do problems in order, if I can't do A in 30 minutes then I will consider B...

Me when doing russian rounds:

→ Ответить

Newton_01

4 года назад, # |

For Problem B, n is <=10^5, test cases are <=10^4 and no. of colours are <=100. How is 10^11 (that's what I can interpret) solution works??

If some one has any explanation and would like to correct where I am wrong, it will be great :)

→ Ответить

naitikvarshney

4 года назад, # ^ |

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

So when value of n is 10^5 then no. of test cases will definitely be 1. When test cases are 10^4, then value of n in all test cases are such that their sum will be atmost 10^5.

→ Ответить

Enigma20

4 года назад, # ^ |

There is a statement, "Sum of $$$n$$$ over all test cases doesn't exeeds $$$10^5$$$". That basically means $$$t*n<=10^5$$$. So, overall operations doesn't exeed $$$100*10^5=10^7$$$ which is acceptable in the given time limit.

→ Ответить

huikang

4 года назад, # |

I did not see that B had only 100 colors :/

→ Ответить

AdHocMan

4 года назад, # |

I am still confused in Div 2D.

→ Ответить

ritesharma

4 года назад, # |

plzz anyone can explain div2 D. why n<=60

→ Ответить

ritik_patel05

4 года назад, # ^ |

For n <= 1e9, There can be atmost two numbers having same most significant bit. Therefore the bound will be atmost twice the number of bits i.e. 2 * log2(1e9) which is 60.

→ Ответить

ritesharma

4 года назад, # ^ |

thanx bro!

→ Ответить

ritik_patel05

4 года назад, # |

Thanks for detailed explanation of Div2E!

→ Ответить

devamg

4 года назад, # |

For Div 2 Problem A, this is my code

Code


#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	ll t;
	cin >> t;
 
	while(t--) {
		ll n, m, r, c;
		cin >> n >> m >> r >> c;
		ll v1 = abs((r + c) - 2);
		ll v2 = abs((r + c) - (1 + n));
		ll v3 = abs((r + c) - (1 + m));
		ll v4 = abs((r + c) - (m + n));
		cout << max(max(v1, v2), max(v3, v4)) << '\n';
		
	}
 
	return 0;
 
}

I have calculated the Manhattan Distance of the cell (r, c) from each of the corner cells, and printed the max distance. My code is giving wrong answer on test 2. Can anyone tell what's wrong in my code?

→ Ответить

munna_bhayia

4 года назад, # ^ |

abs(a — b) + abs(c — d) is not equal to abs((a+c) — (b+d)).They both are different.

→ Ответить

ritesharma

4 года назад, # ^ |

find abs of (row) and col seperate for all four corner

int ans=Math.max(row-1+col-1, Math.abs(n-row)+Math.abs(m-col));

       ans=Math.max(ans, row-1+Math.abs(m-col));
       ans=Math.max(ans, col-1+Math.abs(n-row));

→ Ответить

piddddgy

4 года назад, # |

← Rev. 4 →

for D, I brute forced subarrays of size <= 31, then brute forced again on the "split point". for example, if i have a subarray i...j and a split point of k, we xor the range from i...k and k+1..j. then, we check if the sequence we made decreases at any point. why does this work? I used the claim that there does not exist a construction where we have to make > 29 moves.

https://codeforces.me/contest/1457/submission/99871104

→ Ответить

Xellos

4 года назад, # |

+35

Nobody found the $$$O(N)$$$ for div1D?

→ Ответить

EmptySoulist

4 года назад, # ^ |

how to solve div1D in $$$O(N)$$$ ?

→ Ответить

Xellos

4 года назад, # ^ |

For each situation where you just took the $$$i$$$-th thing, find the set of positions of the clone. For each situation where the clone just took the $$$i$$$-th thing, find the set of your positions. In the first case, it's a contiguous range, which means it has to be up to 2 contiguous ranges in the second case. There's a lot of possible transitions from $$$i$$$ to $$$i+1$$$ but it's a constant number and each takes constant time.

→ Ответить

hoacrux

4 года назад, # |

Can anybody explain the prefix suffix method used in division 2 in D-problem?

→ Ответить

teja349

4 года назад, # |

Is it only me or Div1 E editorial is cryptic.

"Let call low bits that we don't need to care free bits." — can you maybe give an example.

What is A there?

→ Ответить

JettyOller

4 года назад, # ^ |

← Rev. 3 →

For example, assume you have segment $$$(10, 20)$$$ and you set your number $$$011??$$$, your number will be in the segment whatever you set two lowest bits, then they are free.

→ Ответить

Conata

4 года назад, # |

in div2C,why the answer of 2 2 1 10 11 1 is 11,if i make the 0 to 1,it just take 1 second

→ Ответить

NerfThis

4 года назад, # ^ |

This is your test case:

n = 2, p = 2, k = 1; s = "10"; x = 11, y = 1.

x is the cost of adding a platform, y is the cost of removing the first cell. In your case, there is only 1 option: that is to add a platform at position 2, giving 11 as your answer.

→ Ответить

NerfThis

4 года назад, # |

KAN For div2 D, the editorial states the following:

Indeed, there are no two integers with the same highest bit set. It is much easier to solve the problem in such constraints.

I think it should be stated as: there are at most two integers with the same highest bit set. Right? Because for input [1, 6, 7], the highest set bit of all numbers are different but 6 and 7 have the same highest set bit.

→ Ответить

Forrest_Gump

4 года назад, # ^ |

Ya! Exactly. I too think it's a typo.

→ Ответить

KAN

4 года назад, # ^ |

Thanks, corrected! I missed "more than".

→ Ответить

codinginveins

4 года назад, # |

How is the space complexity for div2B O(N) ?

→ Ответить

NerfThis

4 года назад, # ^ |

You are essentially keeping a separate index list for each possible color. The total houses is N, so the total entries in all index lists sum up to N.

→ Ответить

RajawatBanna

4 года назад, # |

It is good tutorial.

Kindly do mention the code also. Sometime explanation is not sufficient

→ Ответить

jagerknight

4 года назад, # |

Could someone please explain the dp approach to div2 C?

→ Ответить

X-O__O-X

4 года назад, # ^ |

← Rev. 3 →

https://codeforces.me/blog/entry/85081#comment-727466

Spoiler

I will explain more the 4 and 5 hints. - Given that the first cell on which the ball will land is cell i, we know it will visit cell i, i+k, i+2k, ... , i+xk<n, right! so we want to count how many index j in {i, i+k, i+2k, ..., i+xk<n} such that s[i] = '0'. In other words, we need to how many cell in the group of cells the ball will visit, does not have a platform. we will of course need to put a platform in each one of them. we have no choice.

Let cnt[i] denote the min number of platforms we must add if the ball starts the journey at index i.
Let's consider the bruteforce first. It's a simple for loop.

we simply iterate over indecies i, i+k, i+2k, ... and if no platform we increment a counter. right!

for (int i = p; i < n; ++i) {
  for (int j = i; j < n; j += k ) {
      if (s[j] == '0') cnt[i]++; 
  }
}

In the previous code, we calculated cnt[i] for every index we are interested in.
This code is O(n^2)
Now, we need to optimize this code using DP
to do that, you need to realize the recursive nature of cnt[i].
cnt[i] clearly depends of cnt[i+k]

cnt[i] = (s[i] == '0' ? 1 : 0 ) + cnt[i+k]
// it means that number of platforms to add if ball starts at i is equal to number of balls to add if ball starts at i+k, plus 1 if cell i also needs a platform.

Now, we can write a recursive code.

int cnt(int i) {
    if (i>=n) return 0; 
    if (s[i] == '0') return cnt[i+k] + 1;  
    else return cnt[i+k]; 
}
int mem[n] = {};
for (int l=p; l<n; ++l) 
   mem[l] = cnt(l);

Now, It should very clear how dp or memoization should be used. we are simply calling the function cnt(l) for n-p times and in each call, it will need about (n-l) / k call. but the function has only 1 parameter with at most n values. so, there must be repetitive calls. use memoization. I hope it's clear now.

int mem[n]; 
int cnt(int i) {
    if (i>=n) return 0; 
    int &ret = mem[i]; 
    if (~ret) return ret; 
    if (s[i] == '0') return ret = cnt[i+k] + 1;  
    else return ret = cnt[i+k]; 
}


for (int l=p; l<n; ++l) 
   cnt(l);

→ Ответить

jagerknight

4 года назад, # ^ |

Thank you!

→ Ответить

wasa855

4 года назад, # |

+18

It seems that the standard program to the Div.1 D has something wrong
https://codeforces.ml/contest/1456/hacks

→ Ответить

KAN

4 года назад, # ^ |

Fixed, some testers' solution got hacked too.

→ Ответить

Mridul323

4 года назад, # |

What would be the difficulty level of XOR gun?

→ Ответить

WitchOfTruth

4 года назад, # ^ |

I bet 1800

→ Ответить

charging

4 года назад, # |

Nice trick in problem Div2D =)

→ Ответить

EmptySoulist

4 года назад, # |

Sorry for my stupid, it's a little hard for me to understand Div1E solution, can someone explain it easily? thanks!

→ Ответить

SGrade

4 года назад, # |

1415B - Repainting Street

Can somebody explain why test case 3 in test 2 (below) says right answer is 2 days? If we choose any color (e.g. 1), there are only 6 houses, which are not this color. So, with capacity k=6 one day should be enough to paint. Looks I am missing something, but don't get what.