Codeforces Round #612 — Editorial

5 лет назад, # ^ |

My solution of 1287D is just recursion:

find all answers for subtrees for childs
concatenate them to have nice 1,2,3...n form (all nodes except current node)
insert current node at exact position, and increment all numbers above.

68267302 Why it works? Well, because childs are independent, and parent value is selected to cut all child nodes at exact position.

→ Ответить

bhasky_06

5 лет назад, # ^ |

could you explain the second and third point more clearly,i saw your code it was quite simple so could you help it more?

→ Ответить

5 лет назад, # ^ |

Let answer of subtree would be what: what you should output if only the subtree is given. Then define function that will give answer for any subtree, and assume that our function will always work. Then, if this function got task to give answer about certain subtree, we can feed it with all subtrees of childs. All of them has answer in the form 1,2,3...n. Also, keep along with it original indices of vertices.

Second point is to concatenate them in similar form. For example, if we have three answers: (1,2,3,4), (1,2), (1,2,3,4,5,6), then we can get (1,2,3,4),(5,6),(7,8,9,10,11,12). Correspoding parts to each child is enclosed into brackets.

Last point is: we should place our 'root' (parent of childs) of the subtree in the answer. We just insert it at place we need to satisfy restriction about number of vertices in subtree. So, if it needs to have 5 childs less than number, then we give it value 6, so it should be inserted like this: (1,2,3,4),(5,*6*,7),(8,9,10,11,12,13). Corresponding childs are enclosed in brackets again.

→ Ответить

towrist

5 лет назад, # ^ |

WOW! Thanks for the pretty solution!

→ Ответить

pedastrian57

5 лет назад, # |

Please someone answer why my code for div2 B 68280267 is getting TLE , though my complexity is O(n^2(k+log(n))

→ Ответить

5 лет назад, # ^ |

For this task, even PyPy doesn't help. You also using some set things that are not superfast. To pass the limit, you need to use some magic, like bitwise operations or other tricky things. Just look how other people solved it using python.

→ Ответить

ISuckAtLife

5 лет назад, # ^ |

I did the same in c++ i.e using set to get the third character. set has an biggest constant that's why it is giving TLE (at least in c++ not sure in python). So u should try to change set to 3 if conditions.

for reference see this thread

→ Ответить

pedastrian57

5 лет назад, # ^ |

But I used a set of only 3 elements :(

→ Ответить

ISuckAtLife

5 лет назад, # ^ |

ya but still due to a huge constant associated with set, this makes your code slow.

→ Ответить

coding_panda

5 лет назад, # |

https://codeforces.me/contest/1287/submission/68316351 this is O(k(n^2)log(n)) solution.But still getting TLE. please help me with this. thanks in advance.

→ Ответить

5 лет назад, # ^ |

I guess your solution fails because of sort in your next function. Replace it with simple if's and your solution should pass.

→ Ответить

coding_panda

5 лет назад, # ^ |

I changed it still getting TLE. https://codeforces.me/contest/1287/submission/68316468

→ Ответить

5 лет назад, # ^ |

Additional problem is that you performing temp=temp+symbol. You should do just temp+=symbol. Because temp=temp+symbol performs copying of string.

→ Ответить

Nabeel_Ghallawenji

5 лет назад, # ^ |

use (temp +=) instead of temp = temp + newchar when appending a char to a string

→ Ответить

pedastrian57

5 лет назад, # ^ |

Hey can you look into my code too please

→ Ответить

coding_panda

5 лет назад, # ^ |

thank you so much.

→ Ответить

hasib_hossain

5 лет назад, # ^ |

← Rev. 3 →

-18

Gcbn

→ Ответить

heyBossCanIGetAnACPlease

5 лет назад, # ^ |

Try hardcoding instead of the function nex, might help

→ Ответить

NoDesire

5 лет назад, # ^ |

← Rev. 3 →

Never try to access a value from map by operator[] if you're not sure it exists there. You should do

auto it = m.find(temp);
if (it != m.end() && it->second > j)
...

Otherwise not existing value will be inserted with default constructor of int i.e. 0, which doesn't break the correctness but increases the time for the following tries to find a value

→ Ответить

person123

5 лет назад, # ^ |

Why to use m.find(temp) if same can be done by using m.count() function and it doesn't even return pointer it just return boolean value.

if(m.count(temp)==1)
...

→ Ответить

NoDesire

5 лет назад, # ^ |

That's because you need not only existence of the key, but its value as well. So in my case you do searching only once, in yours — twice at least

→ Ответить

Extraordinary_

5 лет назад, # |

← Rev. 2 →

Wtf with the tags Div2A/Div2C???

→ Ответить

Nizil

5 лет назад, # |

1286 A — Garland (C of Div-2) could be solved in $$$O(n)$$$ if we use radix sort.

→ Ответить

5 лет назад, # |

+13

My "solution" for div 1C:

Query left and right half of string. Use basic backtracking to find all strings matching the answer, generate all candidates as concatenation of any possible string for left an right half. Calculate for each subsegment hash of answer for each string on this subsegment (can be done in O(n^2)) and find a subsegment giving distinct answers on all possible strings and query it. It takes two queries of length $$$n / 2$$$ and one of at most $$$n$$$ which is enough.

I managed to find 8 different strings with same answer, namely: abaabbabaabaabbabbabaabbab abaabbabbabaabbabaabaabbab abbabaabaabbabaabbabbabaab abbabaabbabbabaabaabbabaab baababbaabaababbabbaababba baababbabbaababbaabaababba babbaabaababbaababbabbaaba babbaababbabbaabaababbaaba But in the official testcases my solution never encountered more than two candidates for each half.

Any idea how do defeat it? 68322452

→ Ответить

KrisjanisP

5 лет назад, # |

← Rev. 2 →

Could you replace the "1286B — Numbers on Tree" editorial's "Rightarrow" and "leq" with symbols. That would be appreciated. It appears only when the language is set to english.

→ Ответить

AjaySabarish

5 лет назад, # |

+13

Could you please attach the solution too?

→ Ответить

ioigod289

5 лет назад, # |

← Rev. 3 →

Can anyone please explain why the first code gets TLE on test 43 while the second one doesn't 68329420 68263645 DIV 2 Que B

→ Ответить

blinkshot

5 лет назад, # |

Do yourself a favour and go see problem tags of div 2 C.

→ Ответить

mango_lassi

5 лет назад, # |

Could you give code for F? I get TLE with both fast zeta-transform 68330755 ($$$\mathcal{O}(2^{n} n^{2} \log n)$$$) and the $$$3^{n}$$$ approach 68330966, and AC only with fast randomised binary zeta-transform 68331478 ($$$\mathcal{O}(2^{n} nk \log n)$$$ where probability of success is polynomial in $$$(1 - 2^{-k})$$$).

→ Ответить

Jatana

5 лет назад, # ^ |

+20

(1 + sqrt(2))^n + n^3 * 2^n

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <ostream>
#include <istream>
#include <typeinfo>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <limits>
#include <fstream>
#include <array>
#include <list>
#include <bitset>
#include <functional>
#include <random>
#include <cstring>
#include <chrono>
#define endl '\n'
#define all(a) (a).begin(), (a).end()
#define len(a) (int) (a).size()
#define forn(i, n) for (int (i) = 0; (i) < (n); ++(i))
using namespace std;
void solve();
mt19937 rnd(2007);
signed main(){
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	swap(rng, rnd);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();
} // Code

const int maxn = 8000;
long long a[maxn], b[maxn];
long long AAll[maxn], BAll[maxn];
long long A[2][maxn], B[2][maxn];
long long szA[2], szB[2];
const int nn = 21;

int FFT_A[nn + 1][(1 << nn) + 7];
int FFT_B[nn + 1][(1 << nn) + 7];
int FFT_C[nn + 1][(1 << nn) + 7];
int F[(1 << nn) + 7];
int BASE[(1 << nn) + 7];

void convolute(int *a, int N) {
	for (int k = N / 2; k >= 1; k /= 2) 
		for (int i = 0; i < N; i += 2 * k) 
			for (int j = 0; j < k; j++) 
				a[i + j + k] += a[i + j];
}

void convolute(vector<int> &a) {
	convolute(a.data(), len(a));
}

void reconvol(int *a, int N) {
	for (int k = 1; k < N; k *= 2)
		for (int i = 0; i < N; i += 2 * k) 
			for (int j = 0; j < k; j++)
				a[i + j + k] -= a[i + j];
}

void reconvol(vector<int> &a) {
	reconvol(a.data(), len(a));
}

int al(long long base[], int basesz, long long cur[]) {
	cur[0] = 0; int szcur = 1;
	for (int ii = 0; ii < basesz; ++ii) {
		long long x = base[ii];
		for (int i = 0; i < szcur; i++) {
			a[i] = cur[i] - x;
			b[i] = cur[i] + x;
		}
		merge(a, a + szcur, b, b + szcur, cur);
		szcur *= 2;
	}
	return szcur;
}
long long base[50];
bool tree[(1 << 22) + 7];

void solve(){
	int n;
	cin >> n;
	vector<long long> v(n);
	forn (i, n) cin >> v[i];

	for (int mask = 0; mask < (1 << n); mask++) {
		int base_sz = 0;
		for (int i = 0; i < n; i++)
			if ((1 << i) & mask)
				base[base_sz++] = v[i];
		int m = base_sz / 2;

		int szAAll = al(base, m, AAll);
		int szBAll = al(base + m, base_sz - m, BAll);
		long long AS = accumulate(base, base + m, 0LL);
		long long BS = accumulate(base + m, base + base_sz, 0LL);
		bool checkF = true, checkS = true;
		if (count(AAll, AAll + szAAll, AS) > 1)
			checkF = false;
		if (count(BAll, BAll + szBAll, BS) > 1)
			checkF = false;
		if (count(AAll, AAll + szAAll, -AS) > 1)
			checkS = false;
		if (count(BAll, BAll + szBAll, -BS) > 1)
			checkS = false;

		szA[0] = szA[1] = szB[0] = szB[1] = 0;
		for (int i = 0; i < szAAll; ++i) {
			long long x = AAll[i];
			A[x&1][szA[x&1]++] = x;
		}
		for (int i = 0; i < szBAll; ++i) {
			long long x = BAll[i];
			B[x&1][szB[x&1]++] = x;
		}
		int c = __builtin_popcount(mask) - 1;
		int s = (((c) & 1));
		for (int _a = 0; _a < 2; _a++) {
			int _b = (s ^ _a);
			int r = szB[_b] - 1;
			for (int cura = 0; cura < szA[_a]; ++cura) {
				long long x = A[_a][cura];
				while (r >= 0 && x + B[_b][r] > c)
					r--;
				if (r == -1) break;
				int nr = r;
				if ((AS == x && BS == B[_b][r] && checkF)
					|| (-AS == x && -BS == B[_b][r] && checkS)) {
					nr = r - 1;
				}
				if (0 <= nr && x + B[_b][nr] >= -c) {
					tree[mask] = true;
					break;
				}
			}
			if (tree[mask]) break;
		}
	}
	for (int i = 0; i < (1 << n); i++) {
		BASE[i] = tree[i];
	}
	memcpy(F, BASE, sizeof F);
	convolute(BASE, 1 << n);
	int rez = 0;
	int step = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < (1 << n); j++)
			if (__builtin_popcount(j) == i)
				FFT_A[i][j] = F[j];
		convolute(FFT_A[i], 1 << n);
	}
	memcpy(FFT_B, FFT_A, sizeof FFT_A);

	while (accumulate(F, F + (1 << n), 0LL)) {
	// for (int test = 0; test < n / 2; test++) {
		rez++;
		for (int i = 1; i <= n; i++)
			for (int j = 1; i + j <= n; j++)
				for (int k = 0; k < (1 << n); k++)
					if (FFT_A[i][k] && FFT_B[j][k])
						FFT_C[i + j][k] += FFT_A[i][k] * FFT_B[j][k];
		memcpy(FFT_A, FFT_C, sizeof FFT_C);
		memset(F, 0, sizeof F);
		for (int i = 1; i <= n; i++) {
			reconvol(FFT_C[i], 1 << n);
			for (int j = 0; j < (1 << n); j++)
				if (__builtin_popcount(j) == i){
					F[j] += FFT_C[i][j];
					
				}
			if (accumulate(F, F+(1<<n),0LL))break;
		}
		memset(FFT_C, 0, sizeof FFT_C);
	}
	cout << n - rez;
}

→ Ответить

mahadi97

5 лет назад, # |

+15

Anything else missing in the Div2 C taglist?

→ Ответить

AjaySabarish

5 лет назад, # |

My O(nlogn) solution for Div2D/DIV1B Insert all numbers from 1 to n in a order-statistics tree. perform a dfs,every time you newly enter a node s,assign ans[s]=value at position c[s] in the order-statistics tree,and erase that element from order-statistics tree 68342107

→ Ответить

Tzak

5 лет назад, # ^ |

+11

It's actually not necessary to use an order-statistics tree here, my submission with $$$O(n^2)$$$ passes quite easily in 30 ms.

→ Ответить

ghoshsai5000

5 лет назад, # |

Can someone please help me with the editorial of LCC ? I have a few doubts.

How to calculate the probability that the $$$i$$$ th collision occurs first ? Why ? Can someone explain this ?

The editorial says that the answer for the mask is the probability that none of the $$$X$$$ collisions do not occur and the extremes move in the direction of the mask. What is $$$X$$$ here ?

Also, what do the leaves of the segment tree hold ? What is the meaning of adding a ban ?

Please help me.

→ Ответить

5 лет назад, # ^ |

Even though I solved just now LCC and just checked isn't there better solution in editorial, I couldn't understand it in the first place. But, it turns out, it's describing same approach. So, not surprising that you didn't understand it.

Now, what I want to clarify is following. it says first i. It means first i collisions in list sorted by time. To make things clear, if there are n particles, then potentially you may have 3*n elements in this list. Each element of list is: which pair of two neighboring particles would collide in what configuration (three configuration described).

Now, from where insight is comming. It's comming from neat fact that you may concatenate two segments using masks described. All you need to know, is probability to have ends of segment facing in certain directions, then you may concatenate them, and have new four values.

So, you represent whole array of particles as array of unit segments with 4 masks, and using segmented tree you may find probability of whole segment. The trick is, that you may change single unit segment to ban some of combinations, and recalculate probability of whole segment in log(n).

Finally, fact about occurance. When I realized it on my own, I was thinking in following way: lets calculate probability that nothing collide. It's just ban all collisions. Now, if we allow highest time of collision: there are two cases: nothing collide, or one or more collide at the same time the highest time of collision. So, probability that you have highest time collision is: probability of highest time of collision allowed minus probability of no collision allowed. Similarly, probability of second highest time is probability that it's allowed (and above) minus probability of highest time collision allowed (and above).

→ Ответить

ghoshsai5000

5 лет назад, # ^ |

Thank you for your reply. If it is okay with you, can you please clarify some of my doubts ? Here is what I understood so far.

The first collision is always between consecutive particles.
We will calculate the time it takes for each of the $$$(n - 1)$$$ pairs of consecutive particles.
We want to calculate the probability that the $$$i$$$-th of these collisions occur first. In order for this to happen, we need to change the directions of some particles to ensure that none of the $$$(i - 1)$$$ particles which come before have a collission.

What I did not understand is how we use a segment tree to do this. Can you please help me ? :)

→ Ответить

5 лет назад, # ^ |

(1), (2) is right. (3) we don't change any directions of particles. We ban pairs of consecutive particles to collide in exact configuration. So, for particles 5,6 we can do at once: LL — allow to collide, RR — ban, RL — allow for example (I don't care here about possibility of this case, but we can ban RR only). Segment tree is need to calculate probability of all this happen. If you have trouble with probability understanding, for n particles there is $$$100^n$$$ variations, and particle $$$i$$$ fly to the right in $$$p_i$$$ cases and to the left in $$$100-p_i$$$ cases, then you may count how many of configurations among $$$100^n$$$ is correct (taking bans into consideration), then divide the number by $$$100^n$$$ and it is probability. Then, apply expectation value formula by definition and you'll get answer.

→ Ответить

ghoshsai5000

5 лет назад, # ^ |

If you are free, can you please work out a small example $$$(n = 3)$$$ by hand and show how to do it on paper ? :)

→ Ответить

5 лет назад, # ^ |

Try to solve different problem. Statement is following: you're given $$$n,\;m,\; 0 \leq p_i \leq 10,\;0\leq t_i\leq 2,\;0\leq x_i\leq n-1$$$, it is number of particles, number of bans, probability 0 to 10, type of ban, and position of ban. You need to calculate number of arrays $$$a$$$ of length $$$n$$$ of numbers 0 to 9 such that some configurations banned.

if $$$t_i = 0$$$ then condition $$$a_{x_i} < p_{x_i}\;and\; a_{x_i+1} < p_{x_i+1}$$$ should be false. (anology to RR)
if $$$t_i = 1$$$ then condition $$$a_{x_i} \geq p_{x_i}\;and\; a_{x_i+1} \geq p_{x_i+1}$$$ should be false. (anology to LL)
if $$$t_i = 2$$$ then condition $$$a_{x_i} < p_{x_i}\;and\; a_{x_i+1} \geq p_{x_i+1}$$$ should be false. (anology to RL)

Then, when you'll write this thing, find out how to add ban online and update answer fast.

→ Ответить

keep_trying

5 лет назад, # |

Why is time limit getting exceeded on test case 10? I cannot understand. My submission https://codeforces.me/problemset/submission/1287/68273741

→ Ответить

coreproject.yaking

5 лет назад, # ^ |

You can use combination and use map for count the same string. Here is my code

→ Ответить

5 лет назад, # ^ |

As it was mentioned in comment above, you should perform appending char to a string with S+=symbol, not S=S+symbol.

→ Ответить

tr4rex

5 лет назад, # |

← Rev. 2 →

+11

it's interesting that the vast majority of div1 folks just decided to use dp in div1_a. i bet they knew about the solution the author presented here, but still they prefered dp. so the rule of thumb — avoid greedy approach if you are unsure about some parts of it?

→ Ответить

Tzak

5 лет назад, # ^ |

I think it's more so that the DP solution is much cleaner to implement. With the greedy solution you also have to consider special cases (ie. intervals on the bounds of the array, $$$n=1$$$, all zeroes).

→ Ответить

Manan_shah

5 лет назад, # |

for problem B, why does 68349376 give TLE inspite of being n^2logn?

→ Ответить

5 лет назад, # ^ |

Your problem is in check function. Using set to get needed char increases complexity. And also you missed that fact that your algorithm is k*n^2*logn.

→ Ответить

Manan_shah

5 лет назад, # ^ |

yeah,sorry for the complexity,but what should i do to optimise then?should i write using ifs?

→ Ответить

5 лет назад, # ^ |

yep, here's my submition of your algorithm with ifs that is AC https://codeforces.me/contest/1287/submission/68353515

→ Ответить

Spheniscine

5 лет назад, # ^ |

← Rev. 2 →

Another approach is to note that it's possible to write a perfect hash function mapping a card to a 64-bit integer, since $$$3^k < 2^{64}$$$

Example: 68357302

→ Ответить

5 лет назад, # ^ |

Even more $$$4^k < 2^{64}$$$. So you can evaluate all symbols in parallel using bitwise operations. Add on top of that open hash table with square steps and you're blazing fast 68356690

→ Ответить

BOGDAN_

5 лет назад, # |

I can't get it. Can somebody explain it please?

→ Ответить

BOGDAN_

5 лет назад, # |

Could you please show the solutions connected to these approaches?

→ Ответить

Swistakk

5 лет назад, # |

Wow, I have completely different solution to D. Mine is in fact much more complicated and fact that time of collision when both particles go facing each other is strictly less than time of collision when they go in the same direction is in fact crucial to my solution, while model solution just don't care. But I'm too lazy to describe it cause it's long x_0.

→ Ответить

ngfam

5 лет назад, # |

← Rev. 2 →

+36

My (maybe simpler) solution for 1286D - LCC:

The main idea is still sorting all the collisions and calculate the probability that first $$$i$$$-th and $$$(i + 1)$$$-th will occur. When it comes to calculating these probability at some certain time, I have some following observations.

Lets first denotes the types of two protons colliding: $$$0$$$ — moving toward each other, $$$1$$$ — both moving to the left and $$$2$$$ — both moving to the right

Observations:

If we only take collisions of type $$$0$$$ into account, a consecutive segments where every protons have collisions with its neighbors, can only accept patterns like this: $$$«««...»»»$$$. Which means, we can always find a position which its left part will only move to the left and vice versa. Let's also denote this as special positions.
Events of type $$$1$$$ and $$$2$$$ will narrow the set of possible candidates for such positions in observation 1, but they still lie in a consecutive segment. It's easy to see that if some pair of $$$i$$$-th and $$$(i + 1)$$$-th protons can not both move to the left, we can not put such position anywhere in the right of them. So each reduction of these events is equal to banning a prefix or a suffix of possible candidates.

For a consecutive segment with the range of special positions, we can easily calculate the sum of probability that this segment will obey the mentioned pattern with prefix product array for moving to the left, suffix product for the right, and prefix sum of product of them (just some easy work on paper).

When we connect two components with some event of type $$$0$$$, it's a few casework to figure out the resulting component's range of special positions. And since events of type $$$1$$$ and $$$2$$$ always occur later than corresponding events of type $$$0$$$, two protons of these events always lie in the same components. So we just need to narrow the range and recalculate the probability.

My code: 68383975.

→ Ответить

ktaranov

5 лет назад, # ^ |

← Rev. 2 →

Hey,

I have some problems with understanding of the LCC problem.

Could you, please, briefly explain why in the third example the correct answer is 150902884?

To be honest, when I read the problem description I expected the solution to be a real number.

→ Ответить

ngfam

5 лет назад, # ^ |

+10

Well it's already stated in the statement that you need to print the answer as $$$P . Q^{-1}$$$ where $$$P/Q$$$ is the real number you mentioned.

→ Ответить

ktaranov

5 лет назад, # ^ |

← Rev. 2 →

+10

Thanks for the reply.

But I am still confused. I was always taught that integers don't have an multiplicative inverse (besides -1 and 1). In addition, it is mentioned that $$$Q$$$ is a natural number, which does not have additive inverse as well. What does $$$Q^{-1}$$$ mean then?

Could you give an example? For instance, if the answer is 99/123, what should I output?

→ Ответить

ngfam

5 лет назад, # ^ |

Here's how $$$123^{-1}$$$ modulo $$$998244353$$$ looks.

For $$$99/123$$$, just multiply them together and mod the result by $$$998244353$$$.

→ Ответить

ktaranov

5 лет назад, # ^ |

← Rev. 2 →

Thanks a lot! Now it makes sense!

Basically, ($$$123^{-1}$$$ mod 998244353) is 32463231, since 32463231*123 mod 998244353 equals to 1.

→ Ответить

indian_luftwaffe

5 лет назад, # |

I still have no idea why 1st submission got accepted while 2nd one was not accepted.
1st solution
2nd solution
Can someone help me, I only changed s = s + s[i] to s+=s[i]

→ Ответить

5 лет назад, # ^ |

s = s + k creates a new string equal to s + k which takes $$$O(|s| + |k|)$$$ time and memory and then assigns it to s

s += k works in $$$O(|k|)$$$ (according to c++ standard might also work in $$$O(|s| + |k|)$$$, but that would be ridiculous to implement it this way)

→ Ответить

indian_luftwaffe

5 лет назад, # ^ |

Great, just learnt a better way of doing. Thanks.

→ Ответить

5 лет назад, # ^ |

Just notice you have Luftwaffe in your username. You still can change it for two days.

→ Ответить

indian_luftwaffe

5 лет назад, # ^ |

-28

The Iran had bombed US bases and I have to prepare for word war 3.

→ Ответить

5 лет назад, # ^ |

So you can at least change it to 303 Squadron

→ Ответить

Amritanshu_7

5 лет назад, # |

Can someone point out what's wrong in my DP approach to C-Garlands? https://codeforces.me/contest/1287/submission/68427357

→ Ответить

atlasworld

5 лет назад, # ^ |

u need to keep track to previous element to. dp[i][o][e][flag] will be the right dp state.

→ Ответить

Amritanshu_7

5 лет назад, # ^ |

Why? Can you please elaborate?

→ Ответить

lcs2019061

5 лет назад, # |

plz anyone tell me what is wrong in my approach of question B Hyperset 68457311

→ Ответить

5 лет назад, # ^ |

← Rev. 2 →

First: O(n^3k) has no chance of passing a maxtest

Second:

for (int i=0;i<a-2;i++)
    {
        for (int j=i+1;j<a-1;j++)
        {
            for (int k=i+2;k<a;k++)

These three loops will run over some unordered triplets more than once.

→ Ответить