Tinkoff Challenge — Final Round (Div. 1 + Div. 2 Combined)

7 years ago, # |

Isn't timing unusual from normal codeforce rounds ? .... Do not want to miss it but have semester exam :(

→ Reply

Mr_Emrul

7 years ago, # ^ |

+20

probably the onsite contest will be held at the same time.

→ Reply

wineColoredDays

7 years ago, # ^ |

Try to do the paper in 1 hour :P

→ Reply

7 years ago, # ^ |

did :p

→ Reply

sina-ss

7 years ago, # |

← Rev. 2 →

-88

→ Reply

dodik2

7 years ago, # ^ |

+149

Spoiler

→ Reply

RockyB

7 years ago, # |

← Rev. 2 →

-32

Thank you)

→ Reply

rnsiehemt

7 years ago, # ^ |

+33

Like someone said it's probably held at the same time as the on-site contest, and different countries hold APIO at different times so it's hard to avoid anyway.

→ Reply

C137

7 years ago, # |

+41

zscoder Congratulations for becoming red :D

I remember last time you prepared a round you was purple

→ Reply

zscoder

7 years ago, # |

+11

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

→ Reply

7 years ago, # |

Are the finalists gonna be in one room?

→ Reply

shestimerk

7 years ago, # ^ |

+10

Yes

→ Reply

7 years ago, # ^ |

+44

You are talking about the codeforces room, in which people can hack each other, right? :)

→ Reply

shestimerk

7 years ago, # ^ |

+22

Yes

→ Reply

7 years ago, # ^ |

-6

And will finalists see the standings of the round, or only each other?

→ Reply

C137

7 years ago, # ^ |

-36

Yes for the third time :D

→ Reply

cheba

7 years ago, # ^ |

Are you a finalist?

→ Reply

Codeforces determining whether or not there will be a delay

7 years ago, # ^ |

← Rev. 2 →

No, I'm just curious, lol

P.S. You can switch to russian version to see finalists's list

→ Reply

Musta_Mohamed

7 years ago, # |

I have an exam, but I'll participate :"D

→ Reply

poomas

7 years ago, # ^ |

← Rev. 2 →

+12

You truly are living on the edge! I wish I could be as bold as you...

→ Reply

arbitrary_A

7 years ago, # |

-31

Hopefully,there could be data structures related problems in this challenge......

→ Reply

nima10khodaveisi

7 years ago, # |

+10

hopefully there will be short statements !!!

→ Reply

hmrockstar

7 years ago, # |

← Rev. 2 →

zscoder is this the round you mentioned here ?

→ Reply

zscoder

7 years ago, # ^ |

+18

Yes :)

→ Reply

Sharon

7 years ago, # |

→ Reply

Autoratch

7 years ago, # |

Hope there won't be delay before the contest.

→ Reply

Decayed

7 years ago, # |

-24

1 hour delaying would be better...

→ Reply

Robinson_828

7 years ago, # |

Hot Day and cool codeforces!

→ Reply

chintu

7 years ago, # |

I predict there will be a question on permutations.

→ Reply

akumar1503

7 years ago, # ^ |

i predict there will atleast be a question on dp.

→ Reply

Osama_Alkhodairy

7 years ago, # ^ |

← Rev. 2 →

+37

I predict D will be a Graph problem as the two previous contests that made by zscoder !

→ Reply

Autoratch

7 years ago, # ^ |

Your predict is correct !!!

→ Reply

rotavirus

7 years ago, # ^ |

I predict that problem A will be easy

→ Reply

amanbol

7 years ago, # |

← Rev. 2 →

I predict that problem C will be easier than previous contest.

→ Reply

amsen_

7 years ago, # |

I'm esemoooooo.

→ Reply

Yellue

7 years ago, # ^ |

Hi, esmoooooo.

→ Reply

Mr.Awesome

7 years ago, # |

+102

I just spotted this lucky cheater sepanta I hope that Mike will take care of him.

→ Reply

7 years ago, # ^ |

yeah i saw too -_-

i didnt know someone already posted it or i would not have posted it....

→ Reply

naksh9619_

7 years ago, # ^ |

+30

And sepanta is blue now :|

→ Reply

Osama_Alkhodairy

7 years ago, # ^ |

← Rev. 2 →

-15

I think he wants to avenge for his comments xD

→ Reply

DatVu

7 years ago, # |

+17

31 hacks on the same one!! What a cheater!!

→ Reply

Osama_Alkhodairy

7 years ago, # ^ |

He is too lucky to enter the same room with his another fake account !

→ Reply

E869120

7 years ago, # ^ |

→ Reply

vivek_reddy

7 years ago, # |

my solution for problem C is showing "running test case 5" for the past 10mins.

→ Reply

vivek_reddy

7 years ago, # ^ |

i got it now

→ Reply

7 years ago, # ^ |

I glare on the statement. It looks so easy. Then I see success ratio. It is about 1./2. What a nice confusing problem!

→ Reply

7 years ago, # |

I am waiting for explanation why it was not possible just to get Problem C AC at the first attempt.

→ Reply

spadiff

7 years ago, # ^ |

← Rev. 4 →

456
123
answer?

→ Reply

7 years ago, # ^ |

162

→ Reply

spadiff

7 years ago, # ^ |

first guy moves first

→ Reply

greenmoon55

7 years ago, # ^ |

Is it 435?

→ Reply

spadiff

7 years ago, # ^ |

← Rev. 3 →

-16

ohh.. unclear

→ Reply

greenmoon55

7 years ago, # ^ |

Thank you very much!

→ Reply

I_Love_Shristi

7 years ago, # ^ |

Nope, you're wrong. If the first guy plays 4 in the middle, then the second guy will play 3 at the last to get the longest lexicographic string. If that happens then first player has no choice but to play 5 which is clearly not the best case. Best case is 435.

→ Reply

im0qianqian

7 years ago, # ^ |

I agree with you, and then write it in this way, but i get a WA.

→ Reply

TimonKnigge

7 years ago, # ^ |

+14

It's 435

→ Reply

hotwater

7 years ago, # ^ |

← Rev. 4 →

435

→ Reply

7 years ago, # ^ |

← Rev. 3 →

Basically there will be 3 numbers in the string, so first player will use 4 and 5, and second player will use 3.

First player wants to minimize the result, so he will obviously put the 4 before the 5. Since it is better for him to have the 3 put in the front, and since the other player is going to put it at the end because 4 > 3 and 5 > 3, he puts 5 in the last spot.

Then the second player puts the 3 in the middle spot, and the 4 goes in the last remaining spot, at the beginning.

Therefore, answer is 435, according to me.

→ Reply

7 years ago, # ^ |

Isn't the output for testcase bcdef abbbc be bccbd ?

→ Reply

7 years ago, # ^ |

My code (which got Accepted) says bccdb.

→ Reply

7 years ago, # ^ |

how ? how much i got is first oleg will place b at first position then igor will place c at 2nd position . now, oleg can place d at last position , now igor will place b at fourth position and then oleg will place c at 3. so the resultant will be bccbd ?

→ Reply

7 years ago, # ^ |

sry got it my bad :(

→ Reply

IWannaBeTheVeryBest

7 years ago, # |

← Rev. 2 →

How to solve B?

P.S. I feel like either A or B is getting harder than C nowadays. Last contest, I solved C easily, but unable to solve A. Today, I solved C (not so easily), but don't have any idea at all to solve B. It feels just weird...

→ Reply

7 years ago, # ^ |

B was easier if you looked for which height should you cut, in order to find a triangle of area i/max_area

→ Reply

7 years ago, # ^ |

binary search, but I'm sure there is some equation to solve it in linear time

→ Reply

IWannaBeTheVeryBest

7 years ago, # ^ |

Binary search the height? But how to compute the area of such heights? Since we don't know the length of base of some heights

→ Reply

fmota

7 years ago, # ^ |

← Rev. 2 →

In similar triangles, we have that the ratio of base/height has to be the same, so you can find the base for a height doing, heightX/heightB, where heightX is the height that you wanna know the base, and heightB is the full base height(the value of the height of the complete triangle).

→ Reply

7 years ago, # ^ |

suppose that b1 is the base with height h1, b = 1

b1 / b = h1 / h

→ Reply

7 years ago, # ^ |

starting from apex if we join the pieces we get a isosceles triangle . then we get relation of base and height using tan(apex angle) Finally we get height of ith cut hi = sqrt(i/n)*h

→ Reply

IWannaBeTheVeryBest

7 years ago, # ^ |

So much geometrical insights... Thanks

→ Reply

egor.okhterov

7 years ago, # ^ |

← Rev. 2 →

double S = h / 2;
double s = S / n;

for (int k = 1; k <= n - 1; k++)
  cout << << sqrt(2 * k * s * h) << ' ';

→ Reply

7 years ago, # ^ |

+14

I guess B is a pure mathematical problem. The k-th answer (indexed from 1) should be sqrt(k/n) * h.

→ Reply

redocyz

7 years ago, # ^ |

I feel stupid using trapezium formula now...

→ Reply

Mr.Awesome

7 years ago, # ^ |

O(1) solution using some geometry properties.

→ Reply

Knight_of_Thirteen

7 years ago, # ^ |

You can determine a single height in O(1), but the total complexity will be O(n)

→ Reply

Mr.Awesome

7 years ago, # ^ |

Yeah sure I meant the single height ,ofCourse it's O(n) overall.

→ Reply

yfo

7 years ago, # ^ |

I think B was very easy math. You got lucky to solve C on first attempt, because it was little tricky — check the successful ratio — 659/1914. Anyway, nice problems, hope you agree.

→ Reply

im0qianqian

7 years ago, # ^ |

You can compute Tan (a) =h/0.5, and then x*x*tan (a) =i*area., where I represents the first I triangle, and X is half the base of each triangle.

→ Reply

animeshf

7 years ago, # |

+13

How to do F? I hope expected solution is not $\text{[math]}$

→ Reply

Sereja

7 years ago, # ^ |

I had N^1.5*10, didn't passed 16'th test. But I hope it can be optimized in the way to pass.

→ Reply

geniucos

7 years ago, # ^ |

← Rev. 3 →

I think NlogN*10 should pass. Just hold the information for lazy propagation as a permutation: all digits i became P[i]. Unfortunately, somehow, in an hour I've got 15 WAs, TLEs and runtime errors. However, it makes sense to work, it's just that I had a lot of bugs. You can propagate something like P[son][i] becomes P[node][P[son][i]]

LE: of course it got AC immediatly after the contest

→ Reply

animeshf

7 years ago, # ^ |

Implementation is rekt

→ Reply

geniucos

7 years ago, # ^ |

Neah, it was easy. I don't know what happened to me. I used to have 0 bugs till a week ago and now every source that I code has the stupidest bugs ever. I had the right idea just after half of the submission I made: initially I though that it's enough to hold all relevant moves on some node and then traverse them and push them to the sons, as I thought there are at most 10 relevant moves (through relevant I mean they change something). Ohh, and of course I spent about 10 minutes to find out that there could be operations that change digit x in x... I think this should've been mentioned. Anyway, the problems were nice but I hurried a lot and wasn't careful because I had a lot of WAs (even on C, I still have no idea what I'm doing wrong as I have a complete proof of my solution, even though I think I overcomplicated the problem)

→ Reply

parth

7 years ago, # ^ |

That was a joke

→ Reply

Sereja

7 years ago, # ^ |

Damn, my solution passes if I switch to size of block exactly sqrt(N) and submit on MS C++ instead of GNU. Such a pain.

→ Reply

7 years ago, # |

Can someone please explain C?

→ Reply

7 years ago, # ^ |

xyz abc => answer is xcy

→ Reply

7 years ago, # ^ |

Yeah I came up with a few cases in contest but couldn't figure out a way to make it consistent, could you elaborate?

→ Reply

7 years ago, # ^ |

The first guy will use only (n+1)/2 characters and second one will use n/2. So keep optimal character set for both of them. Now,

Think about four cases: In his turn,
1. Player 1, has bad set, what should he do?
2. Player 1, has good set, what should he do?
3. Player 2, has bad set, what should he do?
4. Player 2, has good set, what should he do?

→ Reply

7 years ago, # ^ |

Hints

→ Reply

Single_Ready_To_Mingle

7 years ago, # ^ |

How do you classify good or bad sets for both players ?

→ Reply

7 years ago, # ^ |

If you are trying to make the string smaller, than, you have a good set if you have at least one character which is smaller than all of your opponents. and The other way is true.

→ Reply

hotwater

7 years ago, # ^ |

thanks a lot

→ Reply

AshishYadav

7 years ago, # ^ |

I am really feeling bad on seeing how easily it can be solved !!! I am just too stupid :(

→ Reply

7 years ago, # ^ |

The 1750 points confused me in the first time. Maybe you have a bad day. Better luck next time.

→ Reply

BrainFreeze

7 years ago, # ^ |

Actually, wxyz abcd is more interesting. Answer is dwcx, while the most naive strategy will output wdxc.

→ Reply

7 years ago, # ^ |

It should be xyc,isn't it?

→ Reply

madwingis

7 years ago, # ^ |

No, it should be xcy as first guy replaces '?' such that new name would be ??y. Second person have to place 'c' in the middle. Thus we can get xcy as optimal answer.

→ Reply

7 years ago, # ^ |

thank you.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

So first observation is that you will only use the smallest (n+1)/2 elements of the first string and n/2 largest elemets from the second. If all chars from s1 are smaller then it would be easy, you would simply use a greedy to fill the word putting it at the leftmost position. Now, lets have the case where the elements from the first set are larger than the second. You would want to put your largest chars to the right most position, as that minimizes its penalty. So now in these case, you go from largest to smallest and put them in rightmost position. Same is true for the second player

→ Reply

7 years ago, # ^ |

I did something like that, but got WA, could you tell me what's wrong with this code?

Code

ArrayList<Character> o = new ArrayList<>(), i = new ArrayList<>();
		char[] in = scan.next().toCharArray();
		for(char c : in) o.add(c);
		in = scan.next().toCharArray();
		for(char c : in) i.add(c);
		int n = in.length;
		StringBuilder begin = new StringBuilder();
		StringBuilder end = new StringBuilder();
		Collections.sort(o);
		Collections.sort(i);
		for(int j = 0; j < n; j++) {
			if(j%2==0){
				if(o.get(0) < i.get(i.size()-1)) begin.append(o.remove(0));
				else end.append(o.remove(0));
			}
			else {
				if(i.get(i.size()-1) > o.get(0)) begin.append(i.remove(i.size()-1));
				else end.append(i.remove(i.size()-1));
			}
		}
		out.print(begin);
		out.print(end.reverse());

→ Reply

7 years ago, # ^ |

I'm not sure if I understood the code correctly but perhaps its this. So first observation is that you will only use the smallest (n+1)/2 elements of the first string and n/2 largest elemets from the second. So you should never add the last element from a set

→ Reply

7 years ago, # ^ |

← Rev. 2 →

I should't ever be adding the last element in the set, if it looks that way it is because I sorted the second set and am taking letters from the back

→ Reply

7 years ago, # ^ |

try this case
abcxyzzzz
zyxcbaaaa
Each turn the string should be
- a????????
- az???????
- azb??????
- azby?????
- azbyc????
- azbyc???c
- azbyc??yc
- azbyc?xyc
- azbycxxyc

→ Reply

7 years ago, # ^ |

Ok found the bug, when the letters from the first sit are larger than the second, you should put the largest letters at the back first, and not the smallest at the back

→ Reply

7 years ago, # ^ |

← Rev. 2 →

Oh wow that was stupid, thank you for the help!

→ Reply

chiragjn

7 years ago, # ^ |

← Rev. 3 →

I followed this strategy, this didn't work for me on testcase 5

reddit abcdef

This strategy gives dfdede but answer is dfdeed

Can someone explain why? is answer for (dexy, abde) is also deed ?

edit[2] : corrected the starting of the output

→ Reply

7 years ago, # ^ |

how can it give efdeed or efdede when there are only 2 e's
the answer should be
first person will use letters: dde second will use letters: fed d?????
df????
dfd???
dfde??
dfde?e
dfdede

→ Reply

chiragjn

7 years ago, # ^ |

My bad, it was dfdede but the answer is dfdeed!, corrected above

→ Reply

7 years ago, # ^ |

My bad, each turn should be
d?????
df????
dfd???
dfd??d
dfd?ed
dfdeed

→ Reply

LeCaRiBoU

7 years ago, # ^ |

← Rev. 2 →

My solution consisted in the following points :

First, you can know which letters will Egor play, because, as he wants to minimize lexographical order, it's not worth playing its «worst» letters, i.e. he only plays his (n+1)/2 lowest letters.
Same for Igor, who always plays his n/2 biggest letters.
Now, suppose it's Egor playing : his goal will be to minimize the lexicographical order, and thus he wants the lowest letter to be in front. If he has got at least one letter with lower rank than one of Igor's letters, he immediately puts it in front, because it will give him a better score than if Egor plays a largest place instead at the front. However, in the rare case where all his letters are bigger than Igor's one, he wants to play at the back of the string his biggest letter, by a similar argument.
Same for Igor : he will play his biggest letter at the front, except when all his letters are lower than Egor's, in which case he will play his lowest letter at the back.

Implementation isn't really hard, it's simply important not to forget to use sets to quickly retrieve lowest and biggest letters from each player.

→ Reply

Omar_Morsi

7 years ago, # |

How to solve Problem D?

→ Reply

akumar1503

7 years ago, # ^ |

← Rev. 7 →

-13

i think graph should be linear line of compressed cliques and vertices of degree 1 and 2. i.e if deg>2 it should form a clique in combination to other nodes. else -1. but not able to code in time.

Edit: i got the mistake. it need not be clique.

→ Reply

roberto_firmino

7 years ago, # |

How to solve B ? My geometry is weaker than the weakest's

→ Reply

7 years ago, # ^ |

B was easier if you looked for which height should you cut, in order to find a triangle of area i/max_area

→ Reply

jainadarsh

7 years ago, # |

when I will be able to view answers

→ Reply

7 years ago, # ^ |

After systems test is over for that particular solution I guess.

→ Reply

greenmoon55

7 years ago, # ^ |

How long is it normally?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

You can see the solutions now

→ Reply

ankububble

7 years ago, # |

← Rev. 3 →

+11

[Problem D] I needed just 5 more minutes to solve D. Anyway I solved it as follows:
1. For each city, add itself to its adjacency list.
2. Using hashing, we will use DSU to make clusters of cities with exactly same adjacency.
3. Nodes in a cluster will have the same label value.
4. For each city, modify its adjacency list by replacing all cities in it by their representative i.e for (int v: g[u]) replace v by rep(v).
5. Now if there are more than 2 cities in any adjanceny list, its impossible.
6. Do a dfs, and carefully assign values :)

I hope this is a correct solution.
UPD: Here is the code that I missed by 5 mins.
UPD2: It got AC.

→ Reply

Safayat

7 years ago, # |

Can anyone please share the idea to solve problem D?

→ Reply

vivek_reddy

7 years ago, # |

problem C looks complicated any simple solution ?

→ Reply

balsa_knez

7 years ago, # |

Very interesting C task :D

→ Reply

adamant

7 years ago, # |

Failed to handle cornercases of k={n-3, n-2, n-1} in E on last two minutes of contest having correct ideas, such a pain.....

→ Reply

Sereja

7 years ago, # ^ |

← Rev. 2 →

What is general idea for E?

→ Reply

adamant

7 years ago, # ^ |

By picking element from the beginning or from the end of array you simply move its center by 0.5. Thus for fixed array answer is $\text{[math]}$ for even length and $\text{[math]}$ for odd length.

→ Reply

fruwajacybyk

7 years ago, # ^ |

← Rev. 2 →

Maybe I am wrong (got WA on pretest1) but:

if n is even then the answer is max(a[n / 2], a[n / 2 + 1])
if n is odd then the answer is min(max(a[n / 2 - 1], a[n / 2 + 1]), a[n / 2])

and this twist with k is very easy to handle. [edit: to slow]

→ Reply

7 years ago, # |

There's this guy in this contest whose id is sepanta and he hacked 35 times successfully..and most amusing fact is the person he hacked is Mr.Fox and he hacked him 35 times!!! the guy sepanta has solved 2 problems (A and B) and is currently standing on 42 :| what the hell???

→ Reply

egor.okhterov

7 years ago, # ^ |

Don't worry, he'll be banned =)

→ Reply

7 years ago, # ^ |

his rating is now 1772 :| got a +397 boost ....

→ Reply

yfo

7 years ago, # ^ |

Give it a time :) It will work out itself

→ Reply

HOMIARA_RUBY

7 years ago, # |

rating: rest in peace

→ Reply

Moonlit

7 years ago, # |

what is the 4th test case of problem C?

→ Reply

egor.okhterov

7 years ago, # ^ |

Probably, it checks how you process the case when min of Oleg equals max of Igor.

→ Reply

7 years ago, # ^ |

← Rev. 3 →

try this case abcxyzzzz zyxcbaaaa Each turn the string shouuld be - a???????? - az???????
- azb??????
- azby?????
- azbyc????
- azbyc???c
- azbyc??yc
- azbyc?xyc
- azbycxxyc

→ Reply

adnantech17

7 years ago, # |

Explain please how can i solve B.

→ Reply

7 years ago, # ^ |

← Rev. 3 →

Basically the whole triangle's area is h/2. So, each the n parts' area should be h/2n.

So, for every cut i, you should find h(i) so that the resulting triangle has area i*h/2n. Note that if such a triangle has height h(i), that the base has length (h(i)/h). Therefore, you have to solve (h(i)^2) / 2h = i*h/2n, and the answer is sqrt(i/n)*h.

→ Reply

shahidul_brur

7 years ago, # ^ |

"if such a triangle has height h(i), that the base has length (h(i)/h)." - can you please explain me why the base has length (h(i)/h) ?

Thanks in advance.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

You can use Thales theorem to prove this, since cuts are parallel to the base.

Let b the length of the base you want to compute. Then h(i)/h = b/1.

→ Reply

7 years ago, # |

Anyone please help me to solve B?

→ Reply

7 years ago, # ^ |

See above .many coders shared their idea!

→ Reply

7 years ago, # ^ |

thanks.

→ Reply

adnantech17

7 years ago, # |

Quite fast system test today..

→ Reply

TooNewbie

7 years ago, # |

+25

Fastest system testing I have ever seen :O

→ Reply

ankububble

7 years ago, # |

Ultrafast speed of systest <3

→ Reply

7 years ago, # ^ |

I hope they follow same speed in posting editorials :)

→ Reply

abhishek_saini

7 years ago, # |

+10

Amazingly fast system testing

→ Reply

vikas0706

7 years ago, # |

Fastest System Testing ever !!!

→ Reply

DonMichaelCorleone

7 years ago, # |

what's the answer of s = "ddd", t = "aaa" for problem C ?

→ Reply

StillFantasy

7 years ago, # ^ |

dad

→ Reply

7 years ago, # ^ |

← Rev. 2 →

I guess, you didn't got the joke. :( StillFantasy

→ Reply

7 years ago, # ^ |

lol

→ Reply

mitsuki

7 years ago, # |

Why did my code got TLE? Complexity looks fine to me — CODE

→ Reply

7 years ago, # ^ |

← Rev. 2 →

the limits is 300000 but you set #define MAX 200001

→ Reply

mitsuki

7 years ago, # ^ |

my bad. Got it correct now

→ Reply

7 years ago, # ^ |

When I submit it with GNU C++ 11 I get a RTE verdict on test 11 instead of a TLE verdict.

→ Reply

7 years ago, # |

How to hack B?

→ Reply

Livace

7 years ago, # ^ |

← Rev. 2 →

It looks like all successful hacks are made by cheater

→ Reply

Divyansh_19

7 years ago, # |

← Rev. 2 →

Could someone please explain to me why in Test Case 4 (abc aaa), the answer is aab?

I feel the answer should be aba, because Oleg will place 'a' at Position 1, then Igor would place 'a' at Position 3 because he wants the string to be lexicographically large, so Oleg will be left with Position 2 and he'll place b at Position 2.

Thanks in advance!

→ Reply

hell_hacker

7 years ago, # ^ |

What if Oleg puts b in 3rd position. It will become ??b. Then it obviously becomes aab

→ Reply

Divyansh_19

7 years ago, # ^ |

Yes you're right. Thanks a lot!

→ Reply

MathCrusader

7 years ago, # ^ |

Oleg should place the 'b' in position 3. Then Igor has to put an 'a' somewhere. Whether it is placed in the first or second location, Oleg will put their 'a' in the other one, giving 'aab'.

→ Reply

Divyansh_19

7 years ago, # ^ |

Okay. Thanks a lot!

→ Reply

BrainFreeze

7 years ago, # ^ |

Oleg will place 'b' at 3, and after Igor makes his turn ('a' at place 1 or 2, it is irrelevant), Oleg will place 'a' at last empty space. Answer will become aab, which is smaller than aba.

→ Reply

zeliboba

7 years ago, # |

27081526 In this submit time equal 405ms, but it got verdict TL. How it could possible?

→ Reply

Nurseiit

7 years ago, # ^ |

I think it is ML.

→ Reply

zeliboba

7 years ago, # ^ |

Thanks

→ Reply

ArguteOnAir

7 years ago, # |

pls anyone could explain me why the answer of the test Oleg's reddit and Igor's abcdef is dfdeed but not dfdede ? (test 5)

→ Reply

FLYSKY

7 years ago, # ^ |

Yeah I am also having same problem :(

→ Reply

Mama_Bullki

7 years ago, # ^ |

d????? -> df???? -> dfd??? -> dfd??d -> dfd?ed -> dfdeed

→ Reply

ArguteOnAir

7 years ago, # ^ |

oh ok tks :)

→ Reply

FLYSKY

7 years ago, # |

← Rev. 2 →

Can anyone please explain the output of this test case in problem C.

abcdef

Expected answer is this --> dfdeed

My answer --> dfdede

→ Reply

grenade_4

7 years ago, # ^ |

So, the answer will be of 6 letters. letters for optimal answer- {d,d,e} and {f,e,d} Steps are :- 1)d????? 2)df???? 3)dfd??? 4)dfd??d 5)dfd?ed / dfde?d 6)dfdeed

→ Reply

7 years ago, # |

+11

Fastest system test, and fastest rating update ever, nice round :D

→ Reply

Tutis

7 years ago, # |

How to make a segment sum tree with range updates and range queries? I'm asking for problem F, to maintain a segment tree for every digit that have sums like that digit was 1. :)

→ Reply

0w1

7 years ago, # |

Can problem F be solved with DSU on Segment tree? I tried really hard but still in vain with TLEs. It seems like it can pass in time if I change long long to int, but of course with WA.

→ Reply

mitsuki

7 years ago, # |

I submitted two codes one with long double (code) and one with double code.

double got AC and long double got WA on test 1(though it works perfectly on my machine). I always have a rough time with doubles. Am I missing something? some compiler issues?

→ Reply

7 years ago, # ^ |

it should work with C++14

→ Reply

kingofnumbers

7 years ago, # |

+41

Why ratings are updated without removing cheaters?

→ Reply

7 years ago, # ^ |

anyone knows how to tag the boss? i mean Mike or any of the Codeforces official???

→ Reply

7 years ago, # ^ |

Goto any contest announcement blog. There will be a thanks to MikeMirzayanov. Copy the name. Then, Hover over the codeforces icon at the top of the comment box. Then, select "User". Paste the name. Click ok and post.

You will see, sir MikeMirzayanov will be tagged. :)

→ Reply

bula

7 years ago, # |

← Rev. 4 →

In problem C can someone explain test case:

reddit
abcdef

The answer is:

dfdeed

Oleg plays with letters dde
Igor plays with letters fed

Oleg plays: d?????
Igor plays: df????
Oleg plays: dfd???
Igor plays: dfde??

So why would Oleg now play dfdee? — it is not optimal for him?

He should play dfde?e.

So Igor must play: dfdede

For Oleg dfdede is better than dfdeed?

UPDate: got it

Step 4. Igor plays: dfd??d forceing e on the 4th spot.

→ Reply

Vicennial

7 years ago, # ^ |

In the 4th move,
Igor will play dfd?e?.
Now Oleg is forced to put e in the 4th position.

→ Reply

7 years ago, # ^ |

0 d?????
1 df????
2 dfd???
3 dfd??d
4 dfd?ed
5 dfdeed
dfdeed

→ Reply

babin

7 years ago, # |

← Rev. 2 →

Now that this round is finished, when will you announce the random playrix t-shirt winners ? KAN

→ Reply

riadwaw

7 years ago, # ^ |

you can run code yourself

→ Reply

hrushikesht

7 years ago, # ^ |

He has already posted the handle of winners in reply to his original comment on Playrix Contest Blog.

→ Reply