Codeforces Global Round 1

6 years ago, # ^ |

+42

They did surgery on GreenGrape

→ Reply

gold1103

6 years ago, # |

+18

I hope the difficulty gap between problems will be proper.

→ Reply

Peregrine_Falcon

6 years ago, # |

← Rev. 2 →

-71

Just love the unstable contests. GreenGrape is here so we can hope for hell of an unstable contest!I mean contest with weak pretests O_o

→ Reply

gold1103

6 years ago, # ^ |

maybe the purpose is to encourage us to hack others...

→ Reply

Peregrine_Falcon

6 years ago, # ^ |

← Rev. 2 →

+22

I don't understand why people give down vote in almost everything. Everyone can tell their opinion. Now a days, if someone is asking for help they also get down voted.

→ Reply

McDic

6 years ago, # ^ |

← Rev. 2 →

+14

There is no disadvantages(at least I think) for downvoted comments unless you are posting something spam, illegal, NSFW, or whatever. So don't keep those downvotes in your mind :)

→ Reply

M_H_H_7

6 years ago, # |

+56

how many problems will be there?

→ Reply

lessmeaning

6 years ago, # ^ |

eight

→ Reply

C137

6 years ago, # |

+11

What is the number of problems? And round duration???

→ Reply

Wesam

6 years ago, # ^ |

in the previous blog they said every global round will be 7-9 problem

→ Reply

laplace_3

6 years ago, # ^ |

Exactly!

→ Reply

DougNobrega

6 years ago, # |

← Rev. 2 →

+222

Me in this round.

→ Reply

cyand1317

6 years ago, # ^ |

+165

How I spent two hours on problem D...

→ Reply

Slow_But_Determined

6 years ago, # ^ |

Also, me using DSU for B.

→ Reply

Varun_Shah

6 years ago, # ^ |

Same

→ Reply

haleyk100198

6 years ago, # |

-22

It's not like I am going to get any GP score, but it seems a bit unreasonable to rank 4 out of 6 contests, especially with the fact that rounds are not announced weeks ahead of the schedule for participants to allocate time slot for the contest.

→ Reply

Errichto

6 years ago, # ^ |

+85

Ranking 4 out of 6 is a good idea because of the reason you wrote.

→ Reply

KieranHorgan

6 years ago, # ^ |

They clearly meant that 4 out of 6 is still unreasonable.

→ Reply

haleyk100198

6 years ago, # ^ |

← Rev. 3 →

-9

Not if they are announced only half a week beforehand IMO, at this point I can't even tell if the time slot is fixed. I'd imagine I can't participate 1 or 2 of them later into the year since they are midnight rounds for me, and another 1 or 2 of them because it clashes with other activities that I could have possibly adjusted my schedule for it had it announced earlier.

→ Reply

Errichto

6 years ago, # ^ |

+18

But "4 out of 6" only helps you, compared to "6 out of 6".

→ Reply

haleyk100198

6 years ago, # ^ |

I don't mean it's dragging me back, but it's just not good enough to be viable for everyone.

→ Reply

Errichto

6 years ago, # ^ |

What I agree with is that they should announce rounds earlier if we must compete for some total score.

→ Reply

Ace_02

6 years ago, # |

+10

Nice contest after chinese new year :D Good luck all !

→ Reply

restart_2.0

6 years ago, # |

← Rev. 2 →

-16

wishing ** Good luck** to everyone who is going to participate. - !NOOB :|

→ Reply

restart_2.0

6 years ago, # ^ |

Thanks, everyone who did devote me :)

→ Reply

johnny_bhaiya

6 years ago, # |

← Rev. 5 →

-9

Why am i getting negative contribution without doing anything.

→ Reply

hat

6 years ago, # ^ |

This is life.

→ Reply

RayPatterson

6 years ago, # ^ |

That's how codeforces comments works.

→ Reply

medk

6 years ago, # |

+28

I'm not so sure if this is just me or the case for others too, but I feel like weekends would be more convenient for such rounds, people might be more busy during weekdays. Just an opinion I might be wrong :) Best of luck to those participating in this one!

→ Reply

the_art_of_war

6 years ago, # ^ |

+36

On saturday there will be atcoder.

On sunday will be opencup.

So, it is quite reasonable why it is not on weekends.

→ Reply

medk

6 years ago, # ^ |

Oh true! Seems quite logical now. It's impossible to please everyone anyways so that's alright. Thanks!

→ Reply

Xellos

6 years ago, # ^ |

+54

Counterpoint: The Atcoder round isn't for reds and Opencup isn't public either.

→ Reply

lazyneuron

6 years ago, # |

← Rev. 3 →

-21

There used to be a time when questions at the level of C were thought-provoking. Now the contests are like type first 3 fast and sometimes the transition in difficulty is so drastic that as you move from 1 level to another, the difficulty increases manifold. I believe A should be solved by 80%, B should be solved by 60%, C by 20% and D by like 7-8%. And C level questions need to level up.

→ Reply

6 years ago, # ^ |

I thought today's C was quite challenging and B was not so straightforward to implement.

If you are able to solve C's easier than before, it's because you are getting better.

None of the first three problems were typing questions, because they all required some thought. (Easy or difficult, depending on your level).

A typing question is like this is the scenario — implement it.

All the first 3 questions required some deductions.

→ Reply

lazyneuron

6 years ago, # ^ |

This comment was made before the contest.

→ Reply

6 years ago, # ^ |

Ah I see.

→ Reply

LanceTheDragonTrainer

6 years ago, # ^ |

← Rev. 3 →

-12

None of the first three problems were typing questions

Lol. C was a typing challenge and you wrote so much code. No wonder you took so long to solve it.

Is that what you call "competitive" programming? LMAO.

See my submission here

→ Reply

6 years ago, # ^ |

Your solution is essentially the same.

I prefer writing code which is clean and makes the logic clear.

Get a life, man :)

Surely stalking what time I make code submissions and tracking down every single comment I make on here isn't the highlight of your life.

→ Reply

LanceTheDragonTrainer

6 years ago, # ^ |

← Rev. 2 →

-12

I prefer writing code which is clean and makes the logic clear.

Rewriting functionality that the STL already provides for you doesn't make your code cleaner. It makes it worse.

LMAO. Shame on you to call yourself a programmer.

→ Reply

6 years ago, # ^ |

Shame on you to call yourself a human being.

→ Reply

Xellos

6 years ago, # |

Well shit. I can't participate again because the time is too early.

→ Reply

Deathly_Hallows

6 years ago, # |

How many problems and duration ?

→ Reply

Bekh

6 years ago, # ^ |

-14

7-9 problems for 2-3 hours

→ Reply

curly_braces

6 years ago, # |

+10

Getting One T-shirt can make your motivation level rise to the moons! Best of luck everyone.

→ Reply

suncongbo

6 years ago, # |

+27

Will it be in ACM-rules? Or in CF rules?

→ Reply

WaterColor2037

6 years ago, # |

← Rev. 2 →

+15

There was(thanks for the correction!) a 'и' in the English post. Now that I learned Russian a little, I do know it means "and" in Russian, but for those who don't know Russian, it's a bit confusing (especially when it's in the problem statement -- which I've encountered long ago, though it was clear from the context that it means "and" ;)

→ Reply

cyand1317

6 years ago, # ^ |

+92

Codeforces has its own variant of the language. Its people can gradually learn extra words like «и» и «Разбор».

→ Reply

AceIn

6 years ago, # ^ |

+113

Great, I've finally learned something other than сука блять.

→ Reply

Nightmare05

6 years ago, # |

Should we expect an interactive problem?

→ Reply

DD_BOND

6 years ago, # |

seem difficult for practicer like me to compete t-shirt...

→ Reply

0442A403

6 years ago, # |

Feb 7, 2019: Day of emancipation div2 and div3....

→ Reply

6 years ago, # |

← Rev. 2 →

-122

Hi everyone!

I got my old PC fixed just in time to do the contest. Excited to do this contest and this is such a nostalgic feeling. Let us enjoy it together, everyone.

Also, 1 like for getting my main PC fixed. or my PC dies. Your upvotes are really needed. Who wants a poor PC that went through such a harsh life of having 50 chrome tabs open every moment to die? Your likes are needed people.

→ Reply

6 years ago, # ^ |

-36

Oh, at this rate you guys are gonna even kill my old computer and I won't be able to do the contest. Keep it up everyone, 100 downvotes and my battery will blow up.

→ Reply

6 years ago, # ^ |

Too late guys, I already finished the contest. There's no point in blowing up my battery anymore.

→ Reply

Xellos

6 years ago, # ^ |

Protip: you can put a whole persistent OS on a USB drive, and boot from it anywhere (except where BIOS is locked). You don't need your own PC at all.

→ Reply

6 years ago, # ^ |

-13

Oh that's actually really cool. If I had something like that, I could be using an updated Chrome with an updated IOS which I could really use for a VPN. I could also use my main vimrc. But I still needed a repaired PC to use at my home. If I didn't have one, I would either give up the contest, or try to use a smartphone which is kinda ridiculous (has anybody done that?), or do the contest at a place with a PC which would work actually, but I don't know of a place like that off the top of my mind.
tl dr; thank you for the protip.

→ Reply

RockyB

6 years ago, # |

Good luck everyone :D

→ Reply

johnny_bhaiya

6 years ago, # |

-7

Happy Rose day to all...

→ Reply

heyBossCanIGetAnACPlease

6 years ago, # ^ |

-23

Chup re, Majnu Kahin Ke!

→ Reply

osylai

6 years ago, # |

+15

Will the round be sorted by penalties or will points be awarded?

→ Reply

HalfFragment

6 years ago, # |

+35

10,000+ registration is now become common for codeforces ):

→ Reply

BogdanRazvan

6 years ago, # |

Are the problems sorted by ther difficulty ?

→ Reply

kostia244

6 years ago, # |

Wish you good pretests and high rating!

→ Reply

cdkrot

6 years ago, # |

+46

Traditional randomization scripts!

The second script is used to feed random places into the first script. Seed will be the score of the top1 contestant of today's contest, length is the number of people with ranks 31..500 (likely 470) and nwinners is 20.

get_ranklist.py

import requests

contests = [1110]

def is_eligible(contest, party_name, rank, points, problems, last_submission_time):
    return (31 <= rank <= 500)

def get_party_name(party):
    if 'teamName' in party:
        return party['teamName']
    else:
        return party['members'][0]['handle']

class Party:
    def __init__(self, contest, name, rank, points, last_submission_time):
        self.contest = contest
        self.name = name
        self.rank = rank
        self.points = points
        self.last_submission_time = last_submission_time
    
    def __lt__(self, other):
        if self.contest != other.contest:
            return self.contest < other.contest
        if self.rank != other.rank:
            return self.rank < other.rank
        if self.last_submission_time != other.last_submission_time:
            return self.last_submission_time < other.last_submission_time
        return False

eligible = []

for contest in contests:
    rows_to_fetch = 20000
    r = requests.get('https://mirror.codeforces.com/api/contest.standings?contestId=%d&from=1&count=%d&showUnofficial=false' % (contest, rows_to_fetch))
    if r.status_code != 200 or r.json()['status'] != 'OK':
        print('Error: failed to fetch results of contest %d.' % contest)
        exit()
    results = r.json()['result']['rows']
    if len(results) == rows_to_fetch:
        print('Error: results are too long in contest %d, increase limit.' % contest)
        exit()
    for row in results:
        party_name = get_party_name(row['party'])
        rank = row['rank']
        points = row['points']
        problems = 0
        last_submission_time = 0
        for problem in row['problemResults']:
            if problem['points'] > 0:
                problems += 1
                last_submission_time = max(last_submission_time, problem['bestSubmissionTimeSeconds'])
        if is_eligible(contest, party_name, rank, points, problems, last_submission_time):
            eligible.append(Party(contest, party_name, rank, points, last_submission_time))

eligible = sorted(eligible)

for i in range(1, len(eligible)):
    if not eligible[i - 1] < eligible[i]:
        print('Error: unable to sort eligible.')
        exit()

for idx, party in enumerate(eligible):
    print('{} {} {} {}'.format(idx + 1, party.contest, party.rank, party.name))

print('Total %d eligible.' % len(eligible))

exit() # comment to see winners

winners = list(map(int, input().split()))
print()
print('Winners are:')
for place in winners:
    print('{} {} {} {}'.format(place, eligible[place - 1].contest, eligible[place - 1].rank, eligible[place - 1].name))

print()
print('| List place | Contest | Rank | Name |')
print('|--|--|--|--|')
for place in winners:
    print('| {} | {} | {} | [user:{}] |'.format(place, eligible[place - 1].contest, eligible[place - 1].rank, eligible[place - 1].name))

randgen.cpp

#include "testlib.h"
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    if (argc < 4)
    {
        cout << "Command line arguments are: seed length nwinners" << endl;
        return 1;
    }
    int seed = atoi(argv[1]);
    int len = atoi(argv[2]);
    int nwinners = atoi(argv[3]);
    rnd.setSeed(seed);
    
    set<int> winners;
    while (winners.size() < nwinners)
        winners.insert(rnd.next(1, len));
    
    for (auto winner: winners)
        cout << winner << " ";
    cout << endl;
    
    return 0;
}

→ Reply

cdkrot

6 years ago, # ^ |

+45

Well, congratulations for the tourist for being the first one again ;) and deciding the seed today: 11806

./randgen 11806 470 20

So the random winners are:

List place	Contest	Rank	Name
9	1110	39	irkstepanov
41	1110	71	imalyd
71	1110	101	244mhq
77	1110	106	ecnerwala
113	1110	143	rainy_season
138	1110	168	rui-de
151	1110	180	huzzah
160	1110	190	TonySnark
180	1110	210	KostasKostil
184	1110	214	Martin53
199	1110	229	wcy1122
232	1110	262	henryrabbit
235	1110	265	staniewzki
257	1110	287	muratt
275	1110	305	RayPatterson
325	1110	354	Dembow
368	1110	398	mango_lassi
383	1110	413	littleming
440	1110	468	Hongzy
453	1110	483	Marco_L_T

And the non-random winners are:

List place	Contest	Rank	Name
1	1110	1	tourist
2	1110	2	Um_nik
3	1110	3	TLE
4	1110	4	mnbvmar
5	1110	5	sunset
6	1110	6	jqdai0815
7	1110	7	ksun48
8	1110	8	molamola.
9	1110	9	snuke
10	1110	10	fateice
11	1110	11	V--o_o--V
12	1110	12	LHiC
13	1110	13	visitWorld
14	1110	14	sigma425
15	1110	15	uwi
16	1110	16	dotorya
17	1110	17	kmjp
18	1110	18	lych_cys
19	1110	19	neal
20	1110	20	zemen
21	1110	21	ania
22	1110	22	riadwaw
23	1110	23	yutaka1999
24	1110	24	calabash_grandfather
25	1110	25	voover
26	1110	26	whzzt
27	1110	27	yosupo
28	1110	28	supy
29	1110	29	kdh9949
30	1110	30	SpyCheese

Congratulations!

→ Reply

Teamforces

6 years ago, # |

I think wery0 liked this round wery much. Thanks, problemsetters (especially Mr GreenGrape) for good tasks and fast editorial. Also, I want to say thanks to MikeMirzayanov for great(grape) platforms: Codeforces and Polygon!!!!

→ Reply

GreenGrape

6 years ago, # ^ |

+34

grapeforces?

→ Reply

Brankonymous

6 years ago, # |

How to solve E

→ Reply

mbrc

6 years ago, # ^ |

+25

Look at what happens to a_j - a_j - 1 (i.e., the difference array) after an operation.

→ Reply

Brankonymous

6 years ago, # ^ |

Can you elaborate more, I did similar approach but obviously wrong since I got WA :D

→ Reply

adhoc_king

6 years ago, # ^ |

I think sum of squares of difference array remains constant

→ Reply

theodor.moroianu

6 years ago, # ^ |

+21

when you make an operation, you actually make a swap in the difference array so you just have to check if the two arrays are the same

→ Reply

adhoc_king

6 years ago, # ^ |

Oh yeah, so that would be wrong. The correct approach would be to sort the difference arrays and check if both are same.

→ Reply

theodor.moroianu

6 years ago, # ^ |

by "the two arrays are the same" i meant the two difference arrays. You obviously have to sort them because if not any good test would have two identical vectors ;)

→ Reply

adhoc_king

6 years ago, # ^ |

Sorry, I was not saying that your approach is wrong. I was pointing out the mistake in my approach where I said that the sum of squares of difference array remains constant

→ Reply

TheOneYouWant

6 years ago, # ^ |

Seems to me that you can shift the difference array arbitrarily around, since you can swap any two positions. Also, the first and last position of c and t must be the same anyhow. Hence, you just need to check if t can be made.

→ Reply

sdnr1

6 years ago, # ^ |

← Rev. 2 →

Did we just have to check if there exists c_j - c_j - 1 = t_i - c_i - 1 such that j ≥ i?

→ Reply

DespondentGeek

6 years ago, # ^ |

Actually we just need to sort the difference arrays and check if they are same.

→ Reply

JT1123

6 years ago, # ^ |

← Rev. 2 →

Wow! That's a great observation.

How did you notice that? :)

→ Reply

striver_79

6 years ago, # |

← Rev. 2 →

Many people used pow function in A which will overflow but those ran fine. Can someone provide a test case on which these overflow solutions will be wrong if any?

→ Reply

Brankonymous

6 years ago, # ^ |

← Rev. 2 →

-9

[deleted]

→ Reply

gfonn

6 years ago, # ^ |

99 ^ 100.000 it's 200.000 digits long, no way it will fit

→ Reply

aboAdnan

6 years ago, # ^ |

← Rev. 2 →

+15

100⁹⁹⁹⁹⁹ is not equal to 10¹⁰.

→ Reply

Jakube

6 years ago, # ^ |

+16

That's wrong. 1e2^1e5 = 1e200000.

→ Reply

striver_79

6 years ago, # ^ |

+10

Its not multiplication, hence do-not add powers

→ Reply

imposter_syndrome

6 years ago, # ^ |

+10

it's 1e(2*1e5) not 1e10. ((a^x)^y) = (a^(x*y))

→ Reply

Noam527

6 years ago, # ^ |

I guess everybody is doing their part...

sir, (10²)^10⁵ is not equal to 10¹⁰.

→ Reply

AghaTizi

6 years ago, # ^ |

+15

my part: 100^10⁵ isn't equal to 10¹⁰ sir

→ Reply

parth

6 years ago, # ^ |

91 11 1 1 1 1 1 1 1 1 1 1 1

→ Reply

Jakube

6 years ago, # ^ |

+11

I hacked two solutions with pow using 99 99 1 0 0 0 ... 0.

→ Reply

natofp

6 years ago, # ^ |

Is overflow treated as error? Values mod2 will be fine even after overflow, right?

→ Reply

Jakube

6 years ago, # ^ |

pow doesn't operate on integer. You will get a floating point number, that is very unprecise and converting it to an integer will return something bad.

→ Reply

natofp

6 years ago, # ^ |

Feelsbad then, bcs i saw 3 people using this :(

→ Reply

aboAdnan

6 years ago, # ^ |

← Rev. 2 →

Is this for just the precision problems with the function pow?

If yes, so what about the result being not fitting in long long? how to hack it, please?

→ Reply

praveenojha33

6 years ago, # ^ |

← Rev. 4 →

When pow(x,y) is very large then it will become inf which will make result inf.In C++ inf%2 is 0 which means they have defined it as even.So using any big number for which answer is odd will break the normal solution.

→ Reply

Slow_But_Determined

6 years ago, # ^ |

Luckily overflow results in values modulo 2^31 or 2^63 so it doesn't change the parity.

→ Reply

6 years ago, # ^ |

Overflow solution will not be wrong because overflow will preserve parity.

(Because it happens in cycles of 2^{32} or 2^{64})

→ Reply

6 years ago, # |

+20

A was more interesting than usual. :)

→ Reply

WYJ20154348

6 years ago, # |

+30

How to solve D?

→ Reply

natofp

6 years ago, # ^ |

Did not solve it, but if im not mistaken you can decrease each value to ={1,2,3}. And then apply DP.

→ Reply

Roundgod

6 years ago, # ^ |

+57

Nope. You should set that value to {1,2,3,4}. Consider the following testcase: 12 4 1 2 3 1 2 3 2 3 4 2 3 4.

→ Reply

pajenegod

6 years ago, # ^ |

← Rev. 3 →

+27

Just note that you don't need to remove the same consecutive triplet more than 2 times, because otherwise you could have just gotten the same result by removing each number separately.

This in turn allows for a DP solution. Just go through the numbers in sorted order and keep track of how many consecutive triplets the previous number and the previous previous number have been a part of.

EDIT: Some clarifications. The dp state is how many you have left of the previous number and how many you have left of the previous previous number. And because you only want to remove the same consecutive triplet at most twice you can assume that you have at most 2 of the previous previous number.

→ Reply

sevlll777

6 years ago, # |

+15

Very nice problem C!

→ Reply

josen

6 years ago, # ^ |

how to solve it?

→ Reply

6 years ago, # ^ |

Hint: Brute force f(a) for small values of a and look for a pattern.

→ Reply

josen

6 years ago, # ^ |

i don't know how to deal 2^even-1

→ Reply

enoone

6 years ago, # ^ |

just brute force it for all the 2^even-1

→ Reply

TheOneYouWant

6 years ago, # ^ |

I guess you can prove that the largest divisor is always the answer

→ Reply

6 years ago, # ^ |

+16

After I brute forced them, I hard coded them into my solution.

→ Reply

josen

6 years ago, # ^ |

where i can see the all solutions

→ Reply

nantf

6 years ago, # ^ |

+54

For a = 2^k - 1,the binary form is 11111....Consider a 1 ≤ b < a,we will find that $\text{[math]}$ ,so the gcd is $\text{[math]}$ .Its greatest value is a's largest divisor(not including a itself).Iterating divisor can be done in $\text{[math]}$ .

→ Reply

jiteshrao

6 years ago, # |

how to solve B?

→ Reply

6 years ago, # ^ |

Note that if we are allowed n pieces of tape (when k = n), we can end up using a minimum total length of n cm. (We would use 1 cm for each broken segment).

Consider the case where k = n-1. Then we need one piece of tape to cover (at least) 2 broken segments. We want to minimize the total length, so we want this piece of tape to cover the two adjacent segments that are closest.

In general, if we have k pieces of tape, then we will have to merge (n-k) adjacent segments.

Let's define the adjacent difference of segments i and (i+1) as (b[i+1] — b[i] — 1).

So for b[i] = 3 and b[i+1] = 4, the adjacent difference would be 0 and we can tape over both with 1 piece of tape of length 2.

We can generalize this by sorting all adjacent differences then taking the sum of the (n-k) smallest ones and adding n to that sum to get our final answer.

→ Reply

nantf

6 years ago, # |

+87

Best problem C I've ever seen~

→ Reply

MikeMirzayanov

6 years ago, # ^ |

+156

Guess, who is the writer!

→ Reply

soul_voyage

6 years ago, # ^ |

+12

GreenGrape

→ Reply

r_pi

6 years ago, # ^ |

-7

what about d ,e ,f , g, h . they are not good ?

→ Reply

nantf

6 years ago, # ^ |

Well I meant among all the contests I've ever seen this is the best C problem.All the problems are good!

→ Reply

Prakash11

6 years ago, # ^ |

← Rev. 2 →

deleted

→ Reply

vivace1

6 years ago, # |

Can someone explain why binary searching for the answer (minimum length) with a greedy function wrong in case of B problem? I kept on getting WA on pretest 7. A hint would suffice.

→ Reply

6 years ago, # ^ |

What is your greedy function?

→ Reply

vivace1

6 years ago, # ^ |

← Rev. 2 →

For a fixed length, i did a sliding window, starting from a broken point and covering as many points as I can until the total used length is <= maximum length in current call to the greedy function. Then I would start from the next index and do the same until either all points are covered or can't be covered.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

How do you decide whether to start a new piece of tape at the next broken point vs extending the current piece of tape to cover the next broken segment?

I added the description of my solution to B here.

→ Reply

vivace1

6 years ago, # ^ |

Understood the mistake. Thanks.

→ Reply

Not-Afraid

6 years ago, # ^ |

Can you please give some test case where the binary search approach will fail... I also wrote solution using Binary Search but WA on pretest 7

→ Reply

rasalghul

6 years ago, # ^ |

← Rev. 2 →

10 500000 4

1 30003 61255 101250 141246 171244 202492 242483 282475 305289

Correct Ans: 185309 with these indices forming groups [1,2,3][4][5,6,7,8][9,10]

→ Reply

slappy

6 years ago, # |

B was harder than C for me. LOL

→ Reply

atgpah

6 years ago, # |

how to solve B?no idea :(

→ Reply

sevlll777

6 years ago, # ^ |

you need to find k minimum difference pairs from neighbourhoods

→ Reply

atlasworld

6 years ago, # ^ |

the problem is almost similar to atcoder beginner contest 117 problem C which i solved just today .

find the maxx sum = arr[last] — arr[first] you need to find the gap between each array elemets , sort them , and then start sweeping them k times . subtract difference[i] each time from maxx sum .

→ Reply

Trisolaris

6 years ago, # |

+12

Well...I think the pretest of problem A is too weak because I passed the pretest while writing x&1 wrong as x^1...

→ Reply

xuanquang1999

6 years ago, # |

+46

E is one of the best problem E ever on Codeforces, until I realized that one can fail system test because they forget to check if c[1] ≠ t[1] or c[n] ≠ t[n].

→ Reply

AkiLotus

6 years ago, # ^ |

+27

GreenGrape influence is always real.

→ Reply

adamant

6 years ago, # ^ |

+64

Hmm, you don't really have to check c[n] ≠ t[n]

→ Reply

rick99y

6 years ago, # |

-34

Does this count as cheating? I saw a submission for C where the user created a map of all the possible input a's to the answer. Probably these answers were brute forced earlier and logged?

→ Reply

juanigsrz

6 years ago, # ^ |

← Rev. 2 →

+14

Nope, in some problems that's the actual intended solution

→ Reply

longhuenchan

6 years ago, # ^ |

+16

If you say this then tourist is cheating.

→ Reply

atlasworld

6 years ago, # ^ |

haha , why ?

→ Reply

longhuenchan

6 years ago, # ^ |

As what a considerable amount of people have done, he also hardcoded the answer for input in form 2ⁿ - 1.

→ Reply

6 years ago, # ^ |

Almost everyone did this

→ Reply

Kognition

6 years ago, # ^ |

+11

Precomputation is a very legitimate strategy. ICPC World Finals 2018 Problem J solution used precomputation.

→ Reply

letonge

6 years ago, # ^ |

Spoiled >:(

→ Reply

6 years ago, # |

+15

What is test case 35 in D? Many people including me are failing on that

→ Reply

aid

6 years ago, # |

+98

Problem E was on AtCoder: link.

→ Reply

NoLongerRed

6 years ago, # ^ |

That's how I solve pE within 5 minutes lol

→ Reply

Jhin

6 years ago, # |

even the submission that i didnt have time to submit is WA .. now I can rest in peace

→ Reply

JT1123

6 years ago, # |

+37

I love this contest, where the difficulty is in ideas not just complex code.

→ Reply

studymademehappy

6 years ago, # |

When can we konw the final result ?

→ Reply

manybirds

6 years ago, # |

Just for curiosity, why are there no hacking session for this contes_- _t? The contests I participated since were rated for Div2 so... just curious.

→ Reply

AkiLotus

6 years ago, # ^ |

Hacking sessions are only available for Educational Rounds and Div.3 contests. ;)

→ Reply

manybirds

6 years ago, # ^ |

thanks :) glad to check ACs right after!

→ Reply

Majka

6 years ago, # |

So I was using ideone for this contest since I'm not home and I didn't want to install codeblocks on this pc and I got a message that bruce_knight copied my code for B. The message said I could be getting banned for this ? What are my options ?

→ Reply

SugA

6 years ago, # |

← Rev. 2 →

-29

Even tourist couldn't solve H ?
There must be something wrong with tourist or that question...

→ Reply

IIIIIIIIIIIIIIIIIIIII

6 years ago, # ^ |

-8

There must be something wrong with tourist...

→ Reply

cxkno1

6 years ago, # ^ |

You should know that the author might prepare it for more than 2 hours. But tourist just have less than 1.5 hours

→ Reply

RainAir

6 years ago, # |

← Rev. 2 →

+41

I think there are some problems that have appeared in another place. For example: E: BZOJ5071 I'm sorry that the language for this problem is Chinese, but this problem is similar to Problem E （My English is not good）

→ Reply

Zenkai

6 years ago, # |

Can someone explain the logic behind E?

→ Reply

Roundgod

6 years ago, # ^ |

+88

Consider the difference array d, i.e, d_i = a_i + 1 - a_i, then any operation is swapping two elements in the difference array.

→ Reply

vrutik_halani

6 years ago, # |

In api expected rating change shows +34 but in rating changes it shows -4

→ Reply

nonamefour0210

6 years ago, # |

I had almost solved problem G but there was not enough time.... It's an interesting problem to me though.

→ Reply

gaurav172

6 years ago, # |

+13

Can F be done with centroid decomposition ?

For each leaf ,go up to root via centroids storing in each centroid ,distance of leaf from it and its index. For each centroid we keep this list sorted on the basis of indices. While answering a query, we go up to root from vertex v via centroids, at each centroid, we need to query min dist of leaf from this centroid whose index lies in L to R(simple RMQ).Take this minimum across all centroids in my path to root .

Is this approach correct ? will it fit the TL ?

→ Reply

kefaa

6 years ago, # ^ |

Correct, but I guess too slow: 49601147

→ Reply

tfg

6 years ago, # ^ |

+10

It is correct and my solution passed. https://mirror.codeforces.com/contest/1110/submission/49592451

→ Reply

All_hail_TOURIST

6 years ago, # |

I think the rating changes for today's contest were not correct. As the "CF Predictor" extension showed something else and the rating changes were different.

Kindly look into the matter.

→ Reply