Iterate for left turned on lamp. add 2^(min(k - 1, len of suffix)) to answer

UPD: and also add 1 for case when there's no lamps at all

Formula: (n - k + 2) * 2^k - 1. But actually I have no idea how to prove it, just found it by bruteforcing.

Iterate l over range [0..k]. Consider all possilble segments of length l with leftmost and rightmost bits set to 1. For every position, there are 2^{max{0, l - 2}} possible segments, making (n - l + 1)·2^{max{0, l - 2}} possibilities for each possible l (except when l is 0 when there is only one possibility: a string consisting of all zeros).

Most intuitive for me was the following:

Imagine all numbers from 1 to n. For n equals 5 it is going to be:

00000

00001

00010

00011

....

11111

If k =3, then there are exactly 2^k numbers with three digits, we count them in. There are 2^k numbers with exactly four digits, but we are intersted only in those which end '0', like:

01010

01100

01110

So there are 2^k / 2 = 2^(k-1)

Then we look at numbers with exactly five digits, there are 2^(k+1) of them. But we are interested only in those which end by 00, there are 2^(k+1) / 2^2 = 2^(k-1) of them.

And so on. So the final calculation will be 2^k + 2^(k-1) + 2 ^ (k-1) + 2 ^ (k-1) + ... + 2 ^ (k-1) repeated (n-k) times.

I think the scenario in that case is that after losing to some vampire i, we will lose to a vampire j < i few times and build up the strength to beat i later.

+1, what can be wrong?

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(int i = (a); i >= (b); --i)
#define RI(i,n) FOR(i,1,(n))
#define REP(i,n) FOR(i,0,(n)-1)
#define mini(a,b) a=min(a,b)
#define maxi(a,b) a=max(a,b)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define sz(w) (int) w.size()
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf = 1e9 + 5;
const int nax = 1e6 + 5;



int main() {
	int n;
	ll start;
	scanf("%d%lld", &n, &start);
	ll so_far = 0;
	ll ans = n;
	RI(i, n) {
		ll str, gain, loss;
		scanf("%lld%lld%lld", &str, &gain, &loss);
		if(start + so_far > str) {
			so_far += gain;
		}
		else {
			if(so_far - loss <= 0) {
				puts("-1");
				return 0;
			}
			ll diff = so_far - loss;
			// start + so_far + x*diff > str
			ll tmp = str - so_far - start;
			assert(diff > 0);
			assert(tmp >= 0);
			// x * diff > tmp
			ll x = tmp / diff + 1;
			ans += x * i;
			start += x * diff;
			//so_far += x * diff;
			so_far += gain;
		}
	}
	printf("%lldn", ans);
	return 0;
}

EDIT: Yeah, I assumed that the defeated prefix never decreases.

I thought the number of fights in one "run" never decreases when I had WA 3.

Very tricky. It is possible that you return to the original position with fewer points and still the answer is not -1.

3 4 0 5 0 8 0 0 9 0 7 answer: 8

Spent 13 wrong submissions on this (which effectively disqualified me), but finally got it right.

The point is that sometimes it pays of decrease the starting value of M, while my original algorithm terminated when such a situation occurs.

My solutions failed on such case: 3 2 0 7 0 8 0 0 10 0 100

Answer should be 8.

UPD: Its wrong sample, correct one in comments below

Мы правили ситуацию, как могли. Когда исправили и перетестировали посылку, которая падает на первом тесте, сразу сообщили об этом.

Я продолжаю обещать, что многие моменты мы стараемся делать лучше, и в этот раз наступили сразу на двое граблей по Д (первый для меня интерактив): ошибка с семплами и ошибка с информацией о чтении из файла.

P.S. Николай, я рад, что эта ситуация не повлияла на выход в финал. Поздравляю!

Check what is in . Then, with binary search find on the right the first cell of different type. Then, the same on the left.

In binary search you should check X + 1, X + 2, X + 4, X + 8, ... till you find the first different type. Then standard algorithm.

Let's find minimal k such that cells 0 and 2^k have different colors (iterate k). I state that cells 0 and 2^k are in consecutive segments (ease to prove, try yourself). Using binary search find the leftmost cell in 2^k-s segment. Now repeat that starting from that cell instead of starting from 0. We have found starts of two consecutive segments. It is queries (and complexity).

It's JuLy, thanks for the note. We'll get in touch this week

We'll get in touch everyone in TOP-512 this week.

he is cheater[2k])

Sure. We'll send the T-shirt.

Для равных объектов надо возвращать false

I haven't received it yet either.

Please fill feedback form. You can find the link in the bottom left corner of the contest page.

I've surprisingly found mine in a spam folder.

T-shirts are coming. A courier delivered it to me today. What is strange, I had to fill in my passport number in his papers, he said it's required when the package is insured.