Yandex.Algorithm 2016, third elimination round

8 years ago, # ^ |

← 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

→ Reply

unprost

8 years ago, # ^ |

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

→ Reply

aHsirG

8 years ago, # ^ |

← Rev. 2 →

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

→ Reply

xlwinner11

8 years ago, # ^ |

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

→ Reply

linjek

8 years ago, # ^ |

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

→ Reply

xlwinner11

8 years ago, # ^ |

← Rev. 3 →

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

UPD: Thank you all the guys below for explanation.

→ Reply

xennygrimmato

8 years ago, # ^ |

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.

→ Reply

balalaika

8 years ago, # ^ |

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.

→ Reply

Goldsmith94

8 years ago, # ^ |

← 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 ;)

→ Reply

flatline

8 years ago, # ^ |

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

→ Reply

xen

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # |

← Rev. 2 →

+41

any idea how to fix WA3 in C?

→ Reply

ikatanic

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+29

Thanks

Спойлер

→ Reply

8 years ago, # ^ |

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

→ Reply

bharsi

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

+24

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

<.spoiler summary="description">

.~~~~~

code is block, block is in spoiler

~~~~~

<./spoiler>

→ Reply

mmaxio

8 years ago, # ^ |

+15

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

→ Reply

rng_58

8 years ago, # ^ |

+44

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

→ Reply

Al.Cash

8 years ago, # ^ |

+11

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

→ Reply

fhlasek

8 years ago, # ^ |

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.

→ Reply

EvgeniSergeev

8 years ago, # ^ |

+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."

→ Reply

Beresta

8 years ago, # ^ |

← 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

→ Reply

NibNalin

8 years ago, # ^ |

← 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++;
	}
}

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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

→ Reply

8 years ago, # ^ |

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

→ Reply

Beresta

8 years ago, # ^ |

← Rev. 2 →

Oh, sorry, my bad.

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

→ Reply

determinism

8 years ago, # |

← Rev. 2 →

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

UPD: It's out!

→ Reply

8 years ago, # |

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

→ Reply

ajs97

8 years ago, # |

How to solve Problem D?

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

+18

X = 0 is just fine too

→ Reply

Um_nik

8 years ago, # ^ |

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

→ Reply

8 years ago, # |

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?

→ Reply

lperovskaya

8 years ago, # ^ |

← Rev. 2 →

+13

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

→ Reply

I_love_tigersugar

8 years ago, # |

+17

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

→ Reply

linjek

8 years ago, # |

+13

How to solve C?

→ Reply

balsa_knez

8 years ago, # |

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

→ Reply

8 years ago, # ^ |

+22

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

→ Reply

pkhaustov

8 years ago, # ^ |

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

→ Reply

Um_nik

8 years ago, # ^ |

+38

Better than year ago :)

→ Reply

8 years ago, # ^ |

+77

Even red still need to participate in competitions to win.

→ Reply

rng_58

8 years ago, # |

+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?

→ Reply

AomeII

8 years ago, # |

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

→ Reply

8 years ago, # ^ |

+20

he is cheater[2k])

→ Reply

8 years ago, # ^ |

+28

Sure. We'll send the T-shirt.

→ Reply

UncleGrandpa

8 years ago, # |

-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!

→ Reply

Swistakk

8 years ago, # |

-52

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

→ Reply

YouAreMine

8 years ago, # |

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

→ Reply

determinism

8 years ago, # ^ |

+11

I haven't received it yet either.

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

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.

→ Reply

lperovskaya

8 years ago, # ^ |

+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 =)

→ Reply

Ne0n

8 years ago, # ^ |

I've surprisingly found mine in a spam folder.

→ Reply

8 years ago, # ^ |

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

→ Reply

Ne0n

8 years ago, # ^ |

The same thing to me)

→ Reply

determinism

8 years ago, # ^ |

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

→ Reply