Yandex.Алгоритм 2016, третий отборочный раунд

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

← Rev. 2 →

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

→ Ответить

unprost

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

I've got WA 11 using this approach, and all the contest spent testing :(

→ Ответить

aHsirG

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

← Rev. 2 →

2^(k-1)%m != ((2^k)%m)/2. It my WA 11. Very stupid bug :(

→ Ответить

xlwinner11

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

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

→ Ответить

linjek

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

fix '1' in the left suffix : full segments : (n-k+1) * 2^(k-1) not full segments: sum from 0 to (k — 2) 2 ^i and just zeroes — it's 1 more, not full segments and just zeroes gave 2^(k-1).

→ Ответить

xlwinner11

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

← Rev. 3 →

Wow, that's pretty clear. Thank you so much.

UPD: Thank you all the guys below for explanation.

→ Ответить

xennygrimmato

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

Well, I first thought it would be like (n - k) * 2^k, that is, (n - k) positions to fix a window of size k and 2^k possibilities for each window. However, this has over-counting.

But, we can fix ones at the end of each window padded with zeroes on left and right of the window, and then place anything in between. Dunno how to put that in a formula though.

→ Ответить

balalaika

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

fix any segment and set leftmost and rightmost lamp. If set has length l, then count of possible variants is 2^l - 2. For fixed l count of segments is n - l + 1. And then answer is sum for l = 2 to k of 2^l - 2 * (n - l + 1). And need to add n + 1 (for l = 0 and 1). Simplifiing formula gives us your formula.

→ Ответить

Goldsmith94

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

← Rev. 2 →

Say you fix the first K long segment at the beginning. Now you have 2^k possible ways. Every time you move your segment one along, you should not count all the combinations where the lamp that just left your segment was turned off, as they are also valid in the new segment, but already counted. That is 2^(k-1), so for the new segment that is one to the left we add (2^k)-(2^(k-1)) = 2^(k-1) to our answer. We do this n-k times, as this is how many times we can move the segment. So answer is, as you said, 2^k + (n-k)*2^(k-1) = (n-k+2)*2^(k-1)

EDIT: I guess I was the last of a million people to all post within 1 minute ;)

→ Ответить

flatline

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

-6

First add all possible for the first k lamps.

res = 2^k

Now say the right most turned on lamp is i > k. Iterate over all n >= i > k.

You will notice for each such i, answer is 2^(k-1), since you have fixed i-th lamp.

Hence formula is: 2^k + (n-k)2^(k-1)

→ Ответить

xen

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

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).

→ Ответить

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

← Rev. 3 →

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.

→ Ответить

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

← Rev. 2 →

+41

any idea how to fix WA3 in C?

→ Ответить

ikatanic

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

+10

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.

→ Ответить

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

← Rev. 2 →

+29

Thanks

Спойлер

→ Ответить

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

← Rev. 2 →

+1, what can be wrong?

my code


#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.

→ Ответить

bharsi

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

On a different note, how do you post collapsing blocks in comments? I tried the two options available (block, inline) both does not collapse the code.

→ Ответить

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

+24

Try spoiler. I used below (but without dots).

<.spoiler summary="description">

.~~~~~

code is block, block is in spoiler

~~~~~

<./spoiler>

→ Ответить

mmaxio

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

+15

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

→ Ответить

rng_58

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

+44

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

→ Ответить

Al.Cash

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

+11

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

→ Ответить

fhlasek

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.

→ Ответить

EvgeniSergeev

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

+10

And on the 13th day the forces of code went to their forum and said unto each other: "Why can't we solve a baby problem? What's wrong with us?" And they answered: "Behold, thine logic has given way to thine vanity."

→ Ответить

Beresta

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

← Rev. 3 →

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

→ Ответить

NibNalin

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

← Rev. 3 →

How to fix this case? I had a greedy-ish algorithm to go to max point where we can and then increase value to such that it greater than what is needed there. For finding max point where we can reach I used suffix minimum BIT. I am not sure how to fix my idea to accommodate for this case as it would keep on running in prefixes. Can it not be fixed using my current idea?

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long int lli;

const lli inf = 170705091707050917;

lli n, m;
vector<lli> A, B, C, BIT;

void upd(lli idx, lli v)
{
	while(idx <= n)
	{
		BIT[idx] = min(v, BIT[idx]);
		idx += (idx&-idx);
	}
}

lli qry(lli idx)
{
	lli res = inf;
	while(idx > 0)
	{
		res = min(res, BIT[idx]);
		idx -= (idx&-idx);
	}
	return res;
}

int main(void)
{
	scanf("%lld%lld", &n, &m);
	A.clear(); A.resize(n+1);
	B.clear(); B.resize(n+1);
	C.clear(); C.resize(n+1);
	BIT.clear(); BIT.resize(n+1, inf);

	for(lli i = 1;i <= n;i++) scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);

	for(lli i = 1;i <= n;i++) B[i] += B[i-1];
	vector<pair<lli, lli>> pref(n+1);
	for(lli i = 1;i <= n;i++)
	{
		if(!i) pref[i].first = A[i]+B[i-1];
		pref[i].second = i;
	}

	sort(pref.begin(), pref.end());
	for(lli i = n;i > 0;i--)
	{
		upd(n-i+1, pref[i].second);
		//cout << pref[i].second << "n";
	}
	//cout << "startn";
	lli cur, add, ptval, res = 0, iter = 0;
	while(true)
	{
		cur = qry(n-lli(lower_bound(pref.begin(), pref.end(), pair<lli, lli>(m, 0))-pref.begin())+2);
		//cout << cur << "n";
		if(cur == n && m > A[n]-B[n-1])
		{
			printf("%lldn", res);
			return 0;
		}

		add = B[cur-1]-C[cur];
		if(iter > 1e7)
		{
			printf("-1n");
			return 0;
		}
		else
		{
			ptval = A[cur];
			res += cur*(ceil(double(ptval+1-m)/add));
			m += (ceil(double(ptval+1-m)/add));
			m = max(m, 0ll);
		}
		//cout << m << " " << cur << " " << add << " " << ptval << "n";
		iter++;
	}
}

→ Ответить

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

← Rev. 2 →

are you sure it's 8? I got AC now but my solution still thinks it's -1

→ Ответить

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

Correct answer is -1. When we lose the third battle the strength become 0, and we can not win first battle.

→ Ответить

Beresta

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

← Rev. 2 →

Oh, sorry, my bad.

Correct one should be: 3 2 0 7 0 8 0 0 10 0 8

→ Ответить

determinism

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

← Rev. 2 →

When will the final standings (three rounds combined) be released?

UPD: It's out!

→ Ответить

KAN

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

+47

Ээ, серьезно? то есть я отправляю решение вслепую, мне говорят, что оно прошло тест из примера, а на самом деле нет? Для интерактивной задачи это очень важно, вообще-то.

→ Ответить

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

+15

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

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

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

→ Ответить

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

+88

Yandex rounds have really good quality. C, D and E were nice problems, thanks Endagorion.

Though, D was much easier than C and E.

→ Ответить

ajs97

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

How to solve Problem D?

→ Ответить

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

+10

Check what is in $\text{[math]}$ . 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.

→ Ответить

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

+18

X = 0 is just fine too

→ Ответить

Um_nik

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

+21

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 $\text{[math]}$ queries (and complexity).

→ Ответить

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

from Provision: final round — July 28-29, 2016

from Schedule: 28-29 Jun 2016

Could someone clarify? Also, will there be someone from Yandex willing to help with visas?

→ Ответить

lperovskaya

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

← Rev. 2 →

+13

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

→ Ответить

I_love_tigersugar

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

+17

A common reason for blind submissions: Submit near the end of the contest and no time to debug if the code is wrong.

→ Ответить

linjek

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

+13

How to solve C?

→ Ответить

balsa_knez

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

Does anybody know where I should write my address on yandex? I am in first 500 competitors, but I can't find field for address and they can't send me a t-shirt :D. Thanks

→ Ответить

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

+22

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

→ Ответить

pkhaustov

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

-108

This is not a TOP-512. This is the list of 512 people who can afford themselves to take part at least in two rounds.

→ Ответить

Um_nik

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

+38

Better than year ago :)

→ Ответить

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

+77

Even red still need to participate in competitions to win.

→ Ответить

rng_58

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

+34

Some important information for non-Russian-speaking people:

"The Organiser shall not reimburse the Finalists’ costs of transfer from the place of residence of the Finalist to the final round" "Finalists can participate in the final round at the final round venue or online."

Are you planning to attend the onsite finals?

→ Ответить

AomeII

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

What about #513 who has the same penalty with #512 :) ? Can he receive T-shirt ?

→ Ответить

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

+20

he is cheater[2k])

→ Ответить

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

+28

Sure. We'll send the T-shirt.

→ Ответить

gultai4ukr

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

Внимание, вопрос знатокам.

Почему этот код к задаче A ловит RE, а этот — нет? (Разница только в наличии функции сравнения для сортировки в 1 образце)

То, что функция сравнения лишняя (оно таким же образом сортируеться по дефолту) я узнал во время тура, когда разбирался с проблемой. Но ведь по-хорошему надо сдавать, перестраховавшись, что оно все правильно сортирует, а не надеясь на поведение по умолчанию. Очень интересно узнать, в чем всё-таки проблема, чтобы больше не наступать на те же грабли.

→ Ответить

dalex

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

+23

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

→ Ответить

gultai4ukr

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

Большое спасибо, не знал об этом.

→ Ответить

UncleGrandpa

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

-17

Love the blind submissions. Encourage people to code more carefully and not to depend on the testing system to check their codes. And the reward for the brave people is very worthy — Much fewer penalties time!

→ Ответить

Swistakk

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

-52

Let's settle this once and for all. Amazing World of Gumball >> Adventure Time :))).

→ Ответить

YouAreMine

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

Have everyone received the notification mail about the T-shirt? My friends received it yesterday, but I haven't yet. So I am really worried that they lost my email...

→ Ответить

determinism

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

+11

I haven't received it yet either.

→ Ответить

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

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

→ Ответить

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

Please give me advice on T-shirt.

I will be in Russia in August, so thinking to put Russian address in the form instead of Cayman Islands. Do you think it is realistic to receive T-Shirt to address in St. Petersburg by August 26th? Otherwise I'll stick with Cayman Islands address.

→ Ответить

lperovskaya

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

+10

August 26'th is perfectly realistic date for St.Petersburg. Fill in Yandex office address and my name, if you want a personal office tour with your shirt =)

→ Ответить

Ne0n

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

I've surprisingly found mine in a spam folder.

→ Ответить

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

Mine too, but I provided @mail.ru address, so I can understand why :)

→ Ответить

Ne0n

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

The same thing to me)

→ Ответить

determinism

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

Where did you provide your email? I can't remember if I did that.

→ Ответить