CodeCraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) Announcement

8 years ago, # |

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

→ Reply

Kemal

8 years ago, # |

+56

Random --> there is a chance for Div.2 users :)

→ Reply

osmanuss

8 years ago, # |

+28

→ Reply

8 years ago, # ^ |

+21

→ Reply

8 years ago, # |

+12

I hope one day i will get a T-shirt from Codeforces. that will be the best recognition of my hard work. I can't dream for a T-shirt in this round but some (+) rating.

→ Reply

_DN_

8 years ago, # |

← Rev. 3 →

-35

randomly !! Come on there is nothing random in coding even random functions don't work randomly

→ Reply

totsamyzed

8 years ago, # ^ |

Well, there are some ways to generate truly random numbers :)

→ Reply

redocyz

8 years ago, # ^ |

+19

How? And what does "truly random" even means?

→ Reply

totsamyzed

8 years ago, # ^ |

Wiki

→ Reply

XR_Maala

8 years ago, # ^ |

← Rev. 2 →

the random numbers are generated by alghorithm like von neoman or using the common method (last number generated*constant + increament) MOD m beacuse of that it's not truly random .. so the truly random numbers are the number which can really generated randomly by some way

→ Reply

_DN_

8 years ago, # ^ |

-18

that's what i meant and people sink me in much down vote(i don't like it)

→ Reply

redocyz

8 years ago, # ^ |

-6

I suppose there are 2 reasons for it: 1) Your colour. 2) What's the point of pointing that out? I am sure the words have appeared here many times before, so people here might be tired of seeing it.

→ Reply

_DN_

8 years ago, # ^ |

← Rev. 2 →

aha you mean likeability and judgment.
1)likeability: as much as you have color tends to red as much as you may be right.
2)judgment: you probably writing that to get contribution.

it's not facebook guys there is no celebrities her as much practicing as much tend to red & as much u help others as much u get contributions

→ Reply

8 years ago, # ^ |

+78

Why are you going too far?

We have absolute random here, You know, There's no logic behind the codeforces community's votes...

→ Reply

lucaasdamaso

8 years ago, # ^ |

+29

you're totally right sa1378. take my downvote

→ Reply

8 years ago, # ^ |

+26

That's the way Patrick does it ;). Upvote...

→ Reply

saliii

8 years ago, # ^ |

← Rev. 2 →

+20

huh! Not too randomized!!! Actually, the name of the writer, the color, his picture and then the comment is a little important!!! I like Sid! Upvote...!

UPD: To be honest, my rank in the CF's contests are more randomized(*_/*)! I wrongly read a problem again and I spend much of my time on it and then, BOOOMB! Hope you read all of your problem correct!!!

→ Reply

8 years ago, # ^ |

I like the second part of your username! upvote :))

→ Reply

8 years ago, # ^ |

Clarification: "An" means "Shit" in Persian...

→ Reply

saliii

8 years ago, # ^ |

← Rev. 2 →

And It was just a mistake in my username. (~) Hope I can change it next year!!! +_+

→ Reply

C137

8 years ago, # |

-14

Time to say goodbye to grey and cyan, and restore my blue color :D

→ Reply

Carson

8 years ago, # |

-26

Looking forward to the longer contest :)

→ Reply

8 years ago, # |

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

→ Reply

rotavirus

8 years ago, # |

-39

It is rated!

→ Reply

King_George

8 years ago, # |

-32

Longer time and fewer problems than Goodbye 2016.Wondering if the problems gonna be harder. How difficult will the problems be?

→ Reply

Sazzon

8 years ago, # |

Any past contestants of CodeCraft can measure the problems difficulty equivalent to common rounds of codeforces for newcomers?

:-)

→ Reply

skbly7

8 years ago, # ^ |

+48

You may measure the problems difficulty yourself too. :D
Here are the last 3 year questions.

CodeCraft 2016 http://codeforces.me/gym/100889

CodeCraft 2015 http://codeforces.me/gym/100589

CodeCraft 2014 https://www.codechef.com/CDCRFT14

→ Reply

Sazzon

8 years ago, # ^ |

Thx! :)

→ Reply

ColdSu

8 years ago, # |

-32

** ** *****.

→ Reply

knst

8 years ago, # |

+10

Here is something wrong with HTTPS certificate:

net::ERR_CERT_AUTHORITY_INVALID
Subject: felicity.iiit.ac.in
Issuer: StartCom Class 1 DV Server CA

Could you check it?

→ Reply

8 years ago, # ^ |

You can add an exception in your browser to access it. Our ssl certificate is issued by startcom and it might not be installed. Let me know if the issue persists.

→ Reply

knst

8 years ago, # ^ |

← Rev. 4 →

+10

Why do you choose Certificate Authority "starcom"?

starcom is the worst choose CA, bcs it lost the trust. And it's not problem of my browser, it's a issue of CA because this CA abuse too many rules of creating certificates.

And "Starcom" was bought by "WoSign" who lost the trust too.

proof: mozilla blog, google blog

Could you use self-signed certificate? It is not better choose but it is better than starcom IMHO

→ Reply

8 years ago, # |

← Rev. 2 →

+29

From the post: Note : Don't forget to register on our website to be eligible for prizes.

The page for that registration is (perhaps?..) https://felicity.iiit.ac.in/threads/codecraft/

Aaaand, the Register link leads to... https://felicity.iiit.ac.in//auth/login/

What's the matter with you people, asking to register before registration is even working? Edit: I mean, there are currently no means to associate a Codeforces account with the "registration" on your site.

Also, the site font is poorly readable in Firefox in a wide range of scales (but looks fine in Chrome).

→ Reply

8 years ago, # ^ |

-15

For registration for prizes, all you need to do is create an account on our website with the "nick" same as your codeforces handle. In case the nick is already taken please send us a mail @ [email protected].

→ Reply

8 years ago, # ^ |

+12

You know, you could have mentioned the "same nick" part in your post before people try to register.
In some cases, mine and knst's included, what you ask for is impossible.

→ Reply

8 years ago, # ^ |

I will update the post.
We have resolved the issue of nick. Please try again.
Sorry for the inconvenience.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+39

Try again what? I've already registered under different nickname, since the site didn't allow my nickname to be used. And, I don't see any way to change it now.

Edit: From the post: UPD: The constraint of registration for eligibility to prizes has been removed. — Thank you, I like this solution!

→ Reply

8 years ago, # ^ |

Argh, was reading comments and registered there and only then I have read this UPD..

→ Reply

knst

8 years ago, # |

← Rev. 2 →

+62

Error: Nick must be at least 6 characters long

really? And what I should write? knst_SPACE_DELIMITER?

→ Reply

c4cheats

8 years ago, # |

-22

Wow, this contest has my mind firing on all sorts of topics.

CodeCraft — Beer. Craft Beer.

Felicity — I am thinking about the CW show Arrow when I see this, but when I see the the font, I think about FireFly. I don't even watch firefly. Something about it makes me think about it.

Last is Threads. I am thinking about some gangster and his threads.

Well, anyway, thanks for the mind simulation and I am looking forward to the round!

→ Reply

8 years ago, # |

"Note : Don't forget to register on our website to be eligible for prizes."

I registered it on the website and it redirects me back to the front page. When I re-open the register page it still says "click here to register", what did I miss?

→ Reply

8 years ago, # ^ |

Once you have registered, you can login and update your account information. Don't forget to set your nick same as your codeforces handle. In case it's already taken, please send us a mail @ [email protected]

→ Reply

8 years ago, # ^ |

Sorry, I see no way to update account information on the Threads '17 site. Please do kindly provide a link, or instructions how to find it, if such a page exists.

→ Reply

8 years ago, # ^ |

-7

I still get this page after registration, is this behaviour normal, or is it because of my nickname doesn't match with my CF handle?

→ Reply

8 years ago, # |

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

→ Reply

up-and-down

8 years ago, # |

+12

Waiting for a round with codeforces stickers as presents.

→ Reply

repeating

8 years ago, # |

what's the mechanism of the randomly chosen :/

→ Reply

8 years ago, # ^ |

int x=1+(rand()%500) ;

→ Reply

aka.Sohieb

8 years ago, # ^ |

+25

I think you mean int x = 26 + (rand() % 474)

→ Reply

8 years ago, # ^ |

← Rev. 3 →

no it should be int x= 26+rand()%475 .

→ Reply

ISeeNoGodHere

8 years ago, # ^ |

+11

aka.Sohieb you are wrong. You forgot to include 500 in the range.

→ Reply

lightweightsenpai

8 years ago, # |

+103

→ Reply

Abdo_Naser

8 years ago, # ^ |

+62

and when you get "Accepted"

→ Reply

dhruv.joshi

8 years ago, # |

Gordian knot looks interesting, is there some sort of archive of the past problems to have a look at?

→ Reply

Ahmad

8 years ago, # ^ |

Click

→ Reply

dhruv.joshi

8 years ago, # ^ |

man thats from codecraft, i was asking about gordian knot, the project euler style event.

→ Reply

IvanJobs

8 years ago, # |

Wow, nice round. Never got a t-shirt ever. Good luck with me, haha.

→ Reply

8 years ago, # |

+52

Looks like this will be a magic round.

→ Reply

Swistakk

8 years ago, # |

+27

Will the drain be adjusted to the contest's length? If it was not planned to be, PLEASE DO SO :)! It was argued many times why not adjusted drain is a cancer and the longer duration the bigger cancer! Please, please, please.

→ Reply

shakil.ahamed

8 years ago, # ^ |

-13

Did you mean difficulty? Its impossible to do if asked before 3 hour of the contest. :(

→ Reply

themaskedhero

8 years ago, # ^ |

drain describes how fast points gained from submitting drops

→ Reply

shakil.ahamed

8 years ago, # ^ |

Thank you :)

→ Reply

8 years ago, # |

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

→ Reply

born.kira

8 years ago, # |

My First Indian Contest, Hoping For A Positive Rating Change.... bharat mata ki jai....

→ Reply

chill21

8 years ago, # ^ |

bharat mata ki jai :)

→ Reply

allenite

8 years ago, # |

all we can do is hoping for the good contest

→ Reply

shakil.ahamed

8 years ago, # |

Was the score for the problem just changed? Specifically what caused that?

→ Reply

bala7a

8 years ago, # |

why I can't register to the contest !!

→ Reply

kabirsahni8

8 years ago, # ^ |

same here!help!

→ Reply

Mahdi_Jfri

8 years ago, # |

-73

Worst contest ever!

→ Reply

deepanshugarg

8 years ago, # ^ |

+14

Please elaborate.

→ Reply

8 years ago, # ^ |

+15

No, it was superb!

→ Reply

Soroosh

8 years ago, # |

-15

Pretest 12 on problem B is an immovable object..

→ Reply

Amiri

8 years ago, # ^ |

+13

I guess your initial value for ans is less than 1 and your code cannot output correct answer for this test case:

input:
1
1

output:
1

→ Reply

weapon_x

8 years ago, # ^ |

-13

Use an unstoppable force on it. :)

→ Reply

prashantkn94

8 years ago, # |

+11

for the first time I feel there is so much time left for the contest to end. :(

→ Reply

vicky1997

8 years ago, # |

Great Contest ... hoping for the increment in rating !!! Best of luck Guys

→ Reply

allenite

8 years ago, # |

-103

testcase 5 1 1 1 1 1 answer is 1 this case sucks

→ Reply

8 years ago, # |

after the contest gets over , help me solving problem C.I have done the mathematics behind it but dont know what algo to use and what data structure to implement my maths

→ Reply

mitsuki

8 years ago, # ^ |

Two pokemon of types i and j can be permuted if the number of occurences of pokemon type — i and j are equal in all the gyms.

Try to prove it.

My pretests passed though.

→ Reply

8 years ago, # ^ |

as is said i got the maths.You are correct.But i dont know what data structure to use and how to implement it.

→ Reply

bvd

8 years ago, # ^ |

I used hashing technique, but I'm not sure this is a wise way to solve this problem.

→ Reply

Abdo_Naser

8 years ago, # |

+14

that moment ,when you help people but you can't help your self ... -hack A then you hacked !-

→ Reply

8 years ago, # |

+18

Did anyone solved problem C with hashes?

→ Reply

Laiu

8 years ago, # ^ |

+10

Ye i used hashes

→ Reply

rachitiitr

8 years ago, # ^ |

Yes I did.

→ Reply

v_geta

8 years ago, # ^ |

http://ideone.com/idEWaY can you tell me where i am going wrong ?

→ Reply

pakhandi

8 years ago, # ^ |

1 3 1 is not equal to 131

→ Reply

urusant

8 years ago, # ^ |

+10

Yep.

→ Reply

ndkhaivn

8 years ago, # ^ |

Same here :D

→ Reply

Ahmad

8 years ago, # |

Can someone explain how to do C?

→ Reply

rachitiitr

8 years ago, # ^ |

For each pokemon type x, maintain a multiset of indexes of gyms containting x. Now form clusters of similar multisets. A cluster of size n can contribute n! ways to the answer.

→ Reply

Vicennial

8 years ago, # ^ |

Could you explain why the contribution is n! ?

→ Reply

Rusu

8 years ago, # ^ |

← Rev. 2 →

It's the number of permutation. You can permute all the N pokemons (from that cluster) between them and the number of each pokemon type from that cluster is the same.

→ Reply

Ahmad

8 years ago, # ^ |

I did something very similar to that. Can I ask how you calculated n! mod m? And how you modded your answer variable in general?

→ Reply

spk

8 years ago, # ^ |

m can be maximum 1e6 so just precalculate fact[i]%MOD (1<=i<=1e6)

→ Reply

8 years ago, # ^ |

but gyms and their count in that gym both must be same right??How do you deal with that

→ Reply

rachitiitr

8 years ago, # ^ |

I used map< vector , int> cnt for that. But I don't know about its time complexity then solved it using hashing. Not sure if it will pass systest or not.

→ Reply

AndrewB330

8 years ago, # ^ |

← Rev. 3 →

+16

I used trie for counting numbers for each type, it works in O(N + M)

UPD: we can store a chains of pairs in trie, each chain describes how many pokemons of this type in each city.

→ Reply

bhishma

8 years ago, # ^ |

Could you please elaborate your approach .

→ Reply

AndrewB330

8 years ago, # ^ |

Here is my code http://codeforces.me/contest/757/submission/23752278

→ Reply

8 years ago, # ^ |

← Rev. 4 →

code

void solve()
{
	T = 1;
	f[0]=1;
	rep(i,1,N-2) f[i] = 1ll*f[i-1]*i % mod;
	while( n-- )
	{
		cin >> k;
		map<int,int> mapp;
		rep(i,0,k)
		{
			cin >> x;
			mapp[x]++;
		}
		map<int,vector< int > > cnt;
		for(auto u : mapp)
		{
			cnt[ u.ss ] . pb( u.ff );
		}

		for(auto u : cnt)
		{
			map<int,int> setid;
			for(auto t : u.ss)
			{
				if( setid.find( a[t] ) == setid.end() )
					setid[ a[t] ] = T++;
				a[t] = setid[ a[t] ];
			}
		}
	}
	rep(i,1,m+1) 
		//if( a[i] != 0 )
			mapp[ a[i] ]++; // this is a global map, not the one we saw earlier
	ans = 1;
	for(auto u : mapp)
	{
		ans = 1ll*ans*f[ u.ss ] % mod;
	}
	cout << ans;
}

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+15

This code is not needed once we have access to this: 23747486
No maps, no tries — the code is very simple.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

I wish I could think of simple solutions like that.

→ Reply

8 years ago, # ^ |

I am even more impressed by the fact that he came up with a solution in 4 minutes =)

→ Reply

8 years ago, # ^ |

I didn't know we can sort an array of vectors like he did.

→ Reply

docodon

8 years ago, # ^ |

Can you explain what is being done over here in this code !

→ Reply

8 years ago, # ^ |

Each vector a[i] has indices of pokemon gyms where this pokemon initially was. On sorting, the vectors get sorted among themselves.

Now, if a[i]=a[i-1]:

These two pokemons were present in the exact same gyms with same frequency in each of them. Now, we know that any permutation of such sets is a valid one, thus, we increment 't' and multiply to the ans.

eg- if input was
3 5
4 1 2 1 3
6 2 3 3 2 4 5
4 2 3 4 5

Then, a[] will look like this
1 : 1
2 : 1,2,2,3
3 : 1,2,2,3
4 : 2,3
5 : 2,3
ans = (1) * (1*2) * (1*2)

→ Reply

suraj021

8 years ago, # ^ |

I cannot understand what you did after storing the indices of gym for each pokemon?

→ Reply

8 years ago, # ^ |

It's not what I did, it's what Tourist did.

He sorted the array of vectors. The sorting resulted in lexicographical sorting among the vectors. In my comment above, a[] looks like that due to lexicographical order. Each vector in a[] represents a pokemon( we don't care which pokemon it originally was, we just care about the vector it represents ). So, if two pokemons have same vector, this means, they can be evolved into each other. Similarly, if k pokemons have same vector, they can be evolved into each other( hence, answer for this group of pokemons is k! ). If two vectors are not same, then the corresponding pokemon can't be evolved into each other.

→ Reply

8 years ago, # ^ |

Let me add a few minor points.

Each vector<int> can be thought of as a type descriptor (not pokemon descriptor) and we compare those type descriptors with each other (not pokemons).

Each type descriptor is composed out of pokemons (well, their's type).

→ Reply

torquecode

8 years ago, # |

+14

Overall a quite good contest but it feels sad when the ranking are decided by number of successful hacks instead of speed of solving problems.

→ Reply

8 years ago, # |

← Rev. 2 →

anta did 18 successful hacking attempt while tourist 10 (both are good)..... after that tourist solved problem 'G' and placed first.

→ Reply

I_Love_Tina

8 years ago, # |

← Rev. 4 →

-44

WHY,WHY in problem D is needed to set limits up to 75?Why not 50??It is so strict.

Problem E is a very good problem to practice your oeis skills....

Please,pratice more before making a round,and even if you try don't put stupid problems with stupid observation and stupid limits.

→ Reply

radoslav11

8 years ago, # ^ |

How exactly did you use oeis?

→ Reply

I_Love_Tina

8 years ago, # ^ |

← Rev. 2 →

Treat primes independently,you can easily get that you can deal only with p^x and only x is important,generate answers for n = 2, 4, 8, 16 and do oeis for every n with r = 0, 1, 2, 3, 4.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+10

I did OEIS for two vectors with fixed N, saw that they are quadratic and cubic polys, interpolated and factored polys for many different N and saw a simple pattern:

A factor p^e of N contributes to the product:

r if e = 1,
(r - 1)r(r + 1)(r + 2)...(r - 1 + e - 2) * (r + 2 * (e - 1)) / factorial(e) otherwise.

fix: r here is r from query increased by 2.

→ Reply

dreamplay

8 years ago, # ^ |

How to solve it, was it based on mobius function? Fr(n) was multiplicative, probably. Also I tried to use if p is prime, f0(p^a) = 2, f1(p^a) = 2a + 1, f2(p^a) = (a + 1)^2, f3(p^a) = (a+1)(a+2)(2a+3)/6, and then it got lost.

→ Reply

halyavin

8 years ago, # ^ |

← Rev. 3 →

f_n(p^a) = f_{n-1}(1) + f_{n-1}(p) + f_{n-1}(p^2) + ... + f_{n-1}(p^a) = f_n(p^{a-1}) + f_{n-1}(p^a). I just used dynamic programming to precalculate all values.

→ Reply

halyavin

8 years ago, # ^ |

+14

No need for OEIS in E. It is just plain dynamic programing for O(MaxR * MaxPrimePower).

→ Reply

DoubleNy

8 years ago, # |

for problem B, with this input

3 3 3

the output is 3 ?

→ Reply

areke

8 years ago, # ^ |

yep!

→ Reply

8 years ago, # ^ |

Yes.

→ Reply

DoubleNy

8 years ago, # ^ |

← Rev. 3 →

I have copied one solution and on my computer the answer is 1, obviosly i hacked him, but got Unsuccessful hacked attempt, now I saw that on codeforces for same solution the answer is 1, why so ?

→ Reply

Amiri

8 years ago, # ^ |

Did you copy or retype? (you can't copy during contest)

I think you have made mistake in typing his\her solution.

→ Reply

DoubleNy

8 years ago, # ^ |

← Rev. 3 →

no, i didn't, i even made copy-paste(after contest) and the ansewer is 3.

→ Reply

kwangg

8 years ago, # ^ |

but... it should be 3, right?

→ Reply

urusant

8 years ago, # |

+18

Can anybody explain how to solve D?

→ Reply

8 years ago, # ^ |

+29

I used the following dynamic programming:

A state is a mask of already seen numbers (the largest number is always at most 20) and the position in the string.
A transition is just going from one position to some other to the right from it and adding the corresponding number to the mask.

This solution is fast enough if implemented properly.

→ Reply

W4yneb0t

8 years ago, # ^ |

← Rev. 3 →

+21

The key observation is that out of the n*(n+1)/2 substrings, there can be at most n*5 substrings that correspond to numbers between 1 and 20, so you can cut a factor of n from the runtime.

→ Reply

Swistakk

8 years ago, # ^ |

You forgot about leading zeroes.

→ Reply

8 years ago, # ^ |

+13

There are still at most 5 transitions. 0 is not allowed, so leading zeros only move the start of the valid range to the right. They can't increase its length.

→ Reply

Swistakk

8 years ago, # ^ |

Ahh, if we fix start of interval there are at most 5 ends, I missed that, nice.

→ Reply

fruwajacybyk

8 years ago, # |

+92

Hacking is hard when you are colorblind...

→ Reply

shubhamgoyal__

8 years ago, # |

What was the approach for problem E?Did it involve mobius inversions?

→ Reply

Alpha_Q

8 years ago, # ^ |

← Rev. 4 →

+52

I noticed that the function is multiplicative. So I tried to solve for a prime power p^e. Notice that

. $\text{[math]}$

If you let $\text{[math]}$ then the above translates into

. $\text{[math]}$

This recurrence is the same as counting monotone lattice paths from (0, 0) to (e, r). Combining with base cases, you can find the solution

. $\text{[math]}$

→ Reply

TheeLooser

7 years ago, # ^ |

Wow!

→ Reply

Alpha_Q

7 years ago, # ^ |

-_-

→ Reply

8 years ago, # |

Problem B hacking case 3 1 1 1 output: 1

→ Reply

c-and-j

8 years ago, # ^ |

Fail...

→ Reply

8 years ago, # |

To solve Problem D, I was using the fact the maximum number could be 20. Hence my DP array should be :DP[1<<20][75][75] (which is MLE) where the state of DP is(mask,idx,currentCuts). How can i optimize my memory ?

→ Reply

rajat1603

8 years ago, # ^ |

+15

you dont need to keep track of currentCuts as you just need the total sum and not the actual value for each K

→ Reply

8 years ago, # ^ |

Thanks.It was to silly of me to put currentCuts in DP state.

→ Reply

tomlau

8 years ago, # ^ |

Damn... But I have managed to squeeze into time and memory limits with keeping track of currentCuts :)

→ Reply

rajat1603

8 years ago, # |

+67

the friend residing in that city dies, so he is unhappy as well.

→ Reply

MarwanNabil

8 years ago, # |

-26

tourist again :( !

→ Reply

anta

8 years ago, # |

+260

Hacking of C was so exciting.

For example, Errichto used XOR for hashing. So I wrote Gaussian elimination.

Errichto and wokop22's best strategy was submit a code just before the contest ends. So I don't have enough time to hack it.

And the result of this is Errichto's win. Congrats!

→ Reply

8 years ago, # ^ |

+28

That sounds kind of contest-breaking, they shouldn't be about this.

I'll remember it as a viable strategy regardless. :D

→ Reply

Errichto

8 years ago, # ^ |

+37

I'm glad you had fun. And during the round I didn't realize that my solution is hackable because of xoring — so I learnt something today.

→ Reply

vitruvius

8 years ago, # |

Hi. I am noticing many people this round who are colored red and rated Grandmaster. However, when I click on their profile, their rating is much less than 2400. Does anyone know why this is? Is it a bug with the website?

→ Reply

8 years ago, # ^ |

Lurk more.

→ Reply

8 years ago, # ^ |

+10

Do you confirm that Santa Claus is real?

→ Reply

8 years ago, # ^ |

You have been here for 4 years. 4 years Carl!

→ Reply

mitsuki

8 years ago, # ^ |

it is magic

→ Reply

8 years ago, # |

→ Reply

8 years ago, # |

← Rev. 2 →

+34

Thank you for good contest.

Special thanks to C (which can be solved without hashes :)) and E authors.

→ Reply

linkret

8 years ago, # ^ |

How did you solve C without hashing?

I used sums of rand()s, but it's basically the same thing as hashing.

→ Reply

8 years ago, # ^ |

+25

One can show that storing the vector of pairs (gym, count) for all Pokemon is fast enough in the worst case.

→ Reply

anuraganand

8 years ago, # ^ |

+23

What is the worst case complexity for such sorting and how can we prove it?

→ Reply

W4yneb0t

8 years ago, # ^ |

It depends on your choice of sorting algorithm. I don't know exactly what std::sort does, but it got AC.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+10

Well, actually problem is about splitting pokemon types into clusters, where in one cluster number of pokemons of each type is same in each school.

Let's build this clusterization sequentially, adding school by school to it.

(You may ask here what "clusterization" is. Clusterization here is array c[i], which contains identifier of cluster for each type, one class will have same numbers, and different from all others).

So how to process a school?

Group pokemons together by type and count them (in each group, you will have pairs "type, count" after it). Then group pokemon types by number of pokemons in them. (This step can be done in $\text{[math]}$ ), don't touch pokemon types with zero pokemon count, it would be too slow).

Now we have "old clusterization" and new classes to split it.

Iterate over groups of types with same number of pokemons. Split each group by current clusterization. Take note, that each subgroup will have a common type.

So we will simply assign to c[i] some common unique value for all types in this subgroup. (How to get this unique value? Just maintain the maximum of current values in c[i]).

Remark. We just didn't payed attention to group with 0 pokemon types, but if you look carefully you will see, that it's c[i] don't need to be updated.

Remark. All steps above are done in $\text{[math]}$ time.

Remark. If you have troubles understanding text above, you may want to draw some pictures on paper -- draw a circle and split it's area into pieces. Consider this to be old clusterization. Add some more circles into previous one, it should have some non-trivial intersections with previous classes. Consider this to be groups of pokemon types with same number from new school, currently processed.

→ Reply

8 years ago, # ^ |

How do you store such clusters? I was trying to avoid sets/maps but in the end had to store clusters as sets, to allow quick removal (when intersecting one cluster with another). 23753670

→ Reply

http://codeforces.me/contest/757/submission/23755165

8 years ago, # ^ |

+13

As i said, I only store c[i] array. No need to store more.

My approach is intersection each class of pokemons within school with old clusterization. This way i get brand new clusters, which can be be enumerated and assigned to array back.

→ Reply

cerberus97

8 years ago, # ^ |

I had a similar approach to @cdkrot's comment.

→ Reply

8 years ago, # |

any ideas how to solve B? I found it quite hard to do it in O(N) or O(Nlogn)

→ Reply

tfg

8 years ago, # ^ |

If gcd(a, b) != 1, a and b have at least 1 prime in common. For each prime that divides each number do freq[prime]++ and take the greatest of frequencies.

→ Reply

Garfield_

8 years ago, # ^ |

I tried that with once with clasical prime factorization(23760980) first and then with sieve(23762396) and both time TLE on 11th pretest :(

→ Reply

8 years ago, # ^ |

← Rev. 10 →

what you are doing wrong is you are generating prime numbers uptil (100000).the prime number count uptil that is 9950.So your run time will be 10^4*10^5=10^9 approx. which will result in a tle on case 11 .I was having the sae problem.Then i did something smart .I calculated primes only uptil sqrt(10^5).And while traversing array i kept on dividing the arrays with these primes.At the end what was left in the array were themselves primes which u can count in an O(n) operation.So the complexity was brought down from 10^5*10^4 to 10^5*sqrt(10^5)=10^5*10^2=10^7 approx which is within time bounds

→ Reply

tfg

8 years ago, # ^ |

Instead of checking until X every time, save a vector for each number with the primes that divide it. Remember that the sieve is O(nloglogn) so the memory complexity of having the prime factorization is O(nloglogn) as well.

→ Reply

Tiny

8 years ago, # ^ |

do something like sieve function.

→ Reply

appro

8 years ago, # ^ |

Do the prime factorization of each element of array. Elements which have atleast one prime factor in common will have gcd>1,thus they can be included. Maintain an array x in which x[i] is the count of array elements which have x[i] as one of its prime factor. Answer will be the maximum x[i].

→ Reply

8 years ago, # ^ |

I did but got TLE code

→ Reply

8 years ago, # ^ |

← Rev. 2 →

for(int i = 2; i <= mx; i++){
    now = 0;
    for(int j = i; j <= mx; j += i)
        now += cnt[j];
   ans = max(ans, now);
}

Works O(mx * log(mx))

→ Reply

suraj021

8 years ago, # ^ |

How?

→ Reply

8 years ago, # ^ |

N / 1 + N / 2 + N / 3 + ... N / N = N * (1 / 1 + 1 / 2 + 1 / 3 + ... + 1 / N) = N * log(N)

→ Reply

suraj021

8 years ago, # ^ |

Not the time complexity but the explanation of solution.

→ Reply

SarvagyaAgarwal

8 years ago, # ^ |

gcd(x,y) = g implies x,y >= g and g | x,y .

The outer loop just fixes the gcd and the inner loop sums up the counts of all multiples of that gcd .

→ Reply

Smaug

8 years ago, # ^ |

+50

Am I the only who had been surprised when seeing Zlobober is asking this question and then noticed that it's zlobber not Zlobober? :/

→ Reply

8 years ago, # ^ |

+29

Yay, I was also kinda surprised. Just wait until magic ends, and it will return to normal.

→ Reply

barun511

8 years ago, # ^ |

While this submission did not pass system testing (WA on test 82)...it was such a monumentally hilarious idea that I think it should be public..

23759222

→ Reply

Grunt

8 years ago, # |

wish no fst！

→ Reply

I_love_tigersugar

8 years ago, # |

+154

Thank you!

→ Reply

Tiny

8 years ago, # |

+15

Really unusual problem set, not very hard, but no easy problem..

→ Reply

torquecode

8 years ago, # |

← Rev. 2 →

I tried to hack this solution for problem B. It uses strlen() for computing length in each iteration. So, I thought it would O(n*n) complexity. I gave input string of "zzz..." 10^5 times but it passed easily. Any help on why did it happened ?

→ Reply

8 years ago, # ^ |

A compiler can optimize it if the string doesn't change (it's not guaranteed, though).

→ Reply

torquecode

8 years ago, # ^ |

Suprisingly, I successfully hacked another such solution(here) with the same case.

→ Reply

vsp4

8 years ago, # ^ |

Its because he is using global variables. Hence (almost) no optimizations.

→ Reply

I_love_tigersugar

8 years ago, # ^ |

One solution uses GNU C11, the other uses GNU C++. Does this make the difference?

→ Reply

8 years ago, # ^ |

Modern compilers are smart, so perhaps they take this opportunity to optimize and place the calculation before the loop.

→ Reply

https://en.wikipedia.org/wiki/Birthday_attack and https://en.wikipedia.org/wiki/Birthday_problem

8 years ago, # ^ |

AFAIK, compiler is not optimizing semantics of strlen and other funcs.

But strlen's implementation is bloody fast -- it can be written using SSE for example.

→ Reply

picaso

8 years ago, # |

Nice set of problems! Problem statements were well articulated.

→ Reply

Bedge

8 years ago, # |

← Rev. 3 →

Used hash in problem C, failed systest. #notcool#feelsbadman

→ Reply

koderliar

8 years ago, # ^ |

your hash type is 32 bit, it means your hash value has 2^32 possible value, according to:

It says that if we have 10^6 object (pokemons) and hash value is 32 bit (2^32) the probability of at least 1 collision is over 99% no matter how good your hash function, but if we use 64 bit the probability of collision is far less than 1%

I'm curious if there are accepted user with 32-bit hash? I want to confirm wiki theorem :p

→ Reply

Bedge

8 years ago, # ^ |

Actually my hash type is 64 bits, I used unsigned long long. but maybe my base 98317 is too weak.

→ Reply

iliekcomputers

8 years ago, # ^ |

I did it using two simultaneous hashes with different bases and got AC.

→ Reply

Abhedyam

8 years ago, # ^ |

Passed using hashing here.

→ Reply

jihoon

8 years ago, # ^ |

← Rev. 2 →

To prevent systest fail, I used three hash functions :) Here is my source!

→ Reply

hugewarriors

8 years ago, # |

+10

This time lots of hacks & system failure !!!! :P

→ Reply

KhashayarSH

8 years ago, # |

← Rev. 2 →

+103

→ Reply

Errichto

8 years ago, # ^ |

+15

Can someone explain me this comment? Does it suggest that tourist invents better problems? I don't get it.

→ Reply

Superty

8 years ago, # ^ |

+43

It refers to the CodeCraft tagline, "So you think you can code?"

→ Reply

8 years ago, # |

+48

Hmm...

→ Reply

ipaljak

8 years ago, # |

+27

mtomic the TOPPEST of ANIMALS!!! Take a bow son, take a bow!!!

→ Reply

pas.andrei

8 years ago, # |

← Rev. 2 →

+65

And there were 104 tests...

→ Reply

8 years ago, # ^ |

congrats. you just got an AC.

→ Reply

pas.andrei

8 years ago, # ^ |

Thanks, by declaring int nr[80][(1<<20)+100]; I got AC. I overextended a bit with the memory :).

→ Reply

DBradac

8 years ago, # |

+44

Got WA on C because of low RAND_MAX. Gotta love Windows.

→ Reply

linkret

8 years ago, # ^ |

← Rev. 2 →

Me too.

Something like rand() * rand() + rand() would probably work.

EDIT: Confirmed, got AC with this change.

→ Reply

Errichto

8 years ago, # ^ |

← Rev. 2 →

rand() * MAX_RAND + rand() is better — all values can be achieved, assuming that consecutive calls of function are independent.

Edit. As mareksom pointed out (thanks!), my way isn't perfect either. It isn't deterministic which of two rand's will be computed first and thus theoretically two runs of the same program can give different behaviour. So, it's better to do int tmp = rand(); int big = tmp * MAX_RAND + rand().

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+30

To be completely precise, assuming that rand() gives a uniformly distributed value on [0, RAND_MAX], and that two consecutive calls of rand() are independent random variables (that is not true, of course, but imagine that), to get a wider uniform distribution, you should use int tmp = rand(); int big = tmp * (RAND_MAX + 1) + rand(), since RAND_MAX (that is equal to, for example, 32767 under Windows) is an inclusive bound.

→ Reply

zorro_

8 years ago, # |

+76

Am I the only one who copied wrong spelling in hurry just because of this line in explanations

→ Reply

ho-jo-bo-ro-lo

8 years ago, # ^ |

No. I've found at least 6 solutions doing this, in my room :|

→ Reply

Knight_of_Thirteen

8 years ago, # ^ |

Yeah, you literally killed your room :/ I guess it should be a record or something. And by record I mean placing 288th only solving 2 problems and 19 hacks :D

→ Reply

likecs

8 years ago, # ^ |

I once stood 49 based on just hacking and solving just 2 problems. (my third one failed system test). Link to round and Scoreboard

→ Reply

Knight_of_Thirteen

8 years ago, # ^ |

That was quite awesome :D On the other hand, today was a mixed contest of Div1 and Div2. So, 288th is kinda equivalent :D

→ Reply

yashar_sb_sb

8 years ago, # ^ |

I did it too!

→ Reply

gultai4ukr

8 years ago, # |

How many tests were provided for G?

Because it is really bad feeling.

→ Reply

chintu

8 years ago, # ^ |

← Rev. 2 →

Someone made that solution accepted by changing one line(one cout to printf) — 23770624

→ Reply

gultai4ukr

8 years ago, # ^ |

Lol, really. Now it's much more unpleasantly.

→ Reply

8 years ago, # |

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

→ Reply

raghav_19

8 years ago, # |

-8

here is a bug in system testing with my code 23767420 in problem 757E - Bash Plays with Functions my submission got WA on test case 57 while when i compiled on codechef ide with the same code it gave me the correct answer....i also faced the same problem of compilation before some time but it was on practice mode but this time it will affect my rating please resolve it if possible

→ Reply

codelegend

8 years ago, # ^ |

Did you run the code with test case 57 as input (on the codechef IDE)?

→ Reply

raghav_19

8 years ago, # ^ |

yes i run my code with by taking 20 initial case of test case 57 and on codechef IDE it gave me the correct answer for those 20 case while on codeforces it gave me wrong answer on 1st case in 57 test case

→ Reply

nuip

8 years ago, # |

+54

Test cases for D are so weak! We don't have to use 20 to pass all cases.

→ Reply

mochow

8 years ago, # |

I thought of getting TLE on C using just vectors and sortings without hashing. But it gets AC fast enough.

→ Reply

Temirulan

8 years ago, # |

Awesome contest :)

→ Reply

Askha

8 years ago, # ^ |

+10

Eventually red, gj)

→ Reply

8 years ago, # |

+39

Yay finally became orangy on my birthday :)

→ Reply

kpw29

8 years ago, # ^ |

Yay finally I failed another contest, even though I scored F I won't get 2200 before my round :<

→ Reply

rhezo

8 years ago, # |

Why can the maximum number be 20 in problem D? I think it should be 16 only. Because minimum number of bits required to represent all numbers from 1 to 16 is 70. Minimum number of bits required to represent all numbers from 1 to 17 is 76. And the string length is only ≤ 75. Am I right?

→ Reply

ifsmirnov

8 years ago, # ^ |

You are wrong in your calculations, 74 is enough for 20.

→ Reply

8 years ago, # ^ |

Apparently not. Here is the string of length 74 which is a concatenation of binary representations of 1 to 20.

→ Reply

rhezo

8 years ago, # ^ |

Yes, I miscalculated. My bad!

→ Reply

chintu

8 years ago, # ^ |

re-calculate the same again, its 74 bits required for 1-20.

→ Reply

savinovalex

8 years ago, # |

What about problem F? I'm really curious.

→ Reply

zorro_

8 years ago, # |

+23

Congrats rajat1603 for becoming red

→ Reply

8 years ago, # |

magic is so buggy with rating changes!

→ Reply

idee.fixe

8 years ago, # |

+39

Someone just copied tourist's code for problem G and got AC but using C++14 instead of C++11 heh

→ Reply

chintu

8 years ago, # ^ |

he also changed one cout to printf.

→ Reply

tourist

8 years ago, # ^ |

← Rev. 2 →

+424

Yeah, and the funny thing is that neither changing cout to printf nor submitting under C++14 works for me :)

Resubmitting many times might probably help.

→ Reply

8 years ago, # ^ |

+13

or add some comments :)

→ Reply

I_love_Tanya_Romanova

8 years ago, # ^ |

+94

Another way to make it pass is to politely ask compiler to produce faster code using O3 (23772403).

→ Reply

TerryMcGinnis

8 years ago, # ^ |

I thought places like CF would have -O3 by default. Surprised to learn that isn't the case.

→ Reply

Superty

8 years ago, # ^ |

+10

The default is -O2.

→ Reply

animeshf

8 years ago, # ^ |

+18

I heard from the problem setter that the expected solution was O(N * log(N)) and that only highly optimized O(N * log²(N)) should have passed.

→ Reply

8 years ago, # ^ |

+13

During the contest I tried to submit the $\text{[math]}$ solution that does not use the fact we swap only the adjacent elements, but it used Cartesian trees and it worked about 6-7 seconds on maxtests. After the contest I managed to replace all Cartesian trees simply with vectors and binary searches, it still works in $\text{[math]}$ and fits in 2.1 sec: http://codeforces.me/contest/757/submission/23772311 Though, it now relies on that only the adjacent elements are swapped.

This solution may even be optimized to $\text{[math]}$ if we use fractional cascading technique, but it is much harder to implement and I'm not sure if it would significantly reduce the running time.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+10

How could fractional cascading work? I think my approach is the same and I have thought about fractional cascading, but it seems like there may be too many children for each node so we can't store next-level pointer for every branch.

→ Reply

8 years ago, # ^ |

Seems you are right, I didn't notice that in contrary to segment tree in centroid decomposition we have many children. Looks like it makes impossible to find the right position in O(1) when moving from level to its child.

Ok, I don't know how to solve it in $\text{[math]}$ :)

→ Reply

8 years ago, # ^ |

+10

I've just realized that if we ternarize the tree by adding d - 3 edges of zero length to each vertex of degree d > 3 (as described in the editorial), my approach works fine, since the centroid decomposition tree becomes no more than ternary and we need to store no more than three mappings from current level into children levels.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

Right. It's funny that binary tree actually works better in a centroid decomposition solution in this case. :)

→ Reply

8 years ago, # ^ |

Well, I met a new problem when I tried to implement it: is there a simple way to maintain fractional cascading after a swap? Since swap is a relatively simple operation I guess there might be one, but I can't find it.

→ Reply

MinakoKojima

8 years ago, # ^ |

← Rev. 2 →

+10

The TL of Problem G seems to be too tight!

→ Reply

8 years ago, # ^ |

← Rev. 3 →

Maybe the author has a better solution. If not I would be sad about these constant factors...

Anyway, I should foresee this before implemented it, but "solving the last problem" is really a beautiful fantasy :(

Edit: All right, I'm stupid. It seems like I used some unnecessary data structures...

→ Reply

nimxor

8 years ago, # |

+84

When will the list of Tshirt winners be announced? Anytime soon?

→ Reply

orange4glace

8 years ago, # |

3 101 Why answer is 5 in Problem D?

→ Reply

Wildebeest

8 years ago, # ^ |

← Rev. 3 →

orange4glace

|1|01|
|10|1|
1|01|
|1|01
10|1|

→ Reply

orange4glace

8 years ago, # ^ |

Oh, I counted 10|1| twice.. :X thanks!

→ Reply

themaskedhero

8 years ago, # |

How is F solved?

→ Reply

RockyB

8 years ago, # |

+22

When will be editorial?

→ Reply

http://codeforces.me/contest/757/submission/23774954

8 years ago, # |

Can anyone please help take a look why did this submission failed on test case 9? I spent some time on comparing it with some AC submissions and found out that the code went wrong starting on str[52], but I have no idea why did it cause the problem.

→ Reply

8 years ago, # ^ |

The range of your dp should be 2^20 instead of 2^19.

→ Reply

8 years ago, # ^ |

Ah... That was a really dumb mistake. Thanks for the help.

→ Reply

t3rminated

8 years ago, # |

i figured a N*sqrt(N) solution for problem B ,by dividing each number of array with i,(n/i) and then taking the max of count of numbers each divides , but it fails on test #54 — link ,, any help?

→ Reply

8 years ago, # ^ |

There might exist an a[j] > sqrt(n) where a[i] = n/a[j] does not exist.

→ Reply

8 years ago, # |

+14

any editorial?

→ Reply

hrushikesht

8 years ago, # |

@tanujkhatter When will the editorial be released?

→ Reply

Phenol

8 years ago, # |

+24

Baba When will the editorial be released?

→ Reply

VovanF98

8 years ago, # |

Could anybody please explain how to solve D,i've tried to comprehend the solituon of tourist but didn't get it,and i can't wait until the editorial is published:)

→ Reply

8 years ago, # ^ |

I've used simple recursive search with memoizing and cutting search when there is not enough space to finish the sequence. Got AC with PyPy, 2.5s / 4s: 23765504

→ Reply

mak_0111

8 years ago, # |

In problem C, why does 1. get TLE -
1. (Using unordered_map) http://codeforces.me/contest/757/submission/23759809
2. (Using map) http://codeforces.me/contest/757/submission/23779874
Isn't unordered_map supposed to be faster?

→ Reply

sengxian

8 years ago, # ^ |

unordered_map can be hacked. See this: https://ipsc.ksp.sk/2014/real/problems/h.html

→ Reply

ignatiy134

8 years ago, # |

+11

Thank you for this competition. Problems were very interesting. I like problem B.

→ Reply

creat2012

8 years ago, # |

where is the offical solutions?

→ Reply

8 years ago, # |

+143

What about Tshirts?

→ Reply

8 years ago, # |

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

→ Reply

Azuki_daisuki

8 years ago, # |

+36

I wonder when the T-shirt winners will come out…

→ Reply

8 years ago, # ^ |

← Rev. 2 →

+13

| every hour update the page with this blog...

→ Reply

8shubham

8 years ago, # |

Hey !! I was trying to attempt problem C and I think my logic is correct but I am getting a WA on test 31 and I am not able to figure out bug in my code http://codeforces.me/contest/757/submission/23790926. I think problem is related to string which is used in map but I am not able to understand, can anyone help on it ??

→ Reply

8 years ago, # ^ |

← Rev. 2 →

mp[x] += i+'0';

i can be big (> 256), so your solution incorrect.

→ Reply

8shubham

8 years ago, # ^ |

I am not able to understand properly can you elaborate on it a little. Thanks

→ Reply

Azuki_daisuki

8 years ago, # ^ |

You seem to try to add a character i + '0' at the end of the hash of x mp[x], but in the value of a character must be under 128 (256 if unsigned char) while i can be as big as n. That is where and why it went wrong.

→ Reply

8shubham

8 years ago, # ^ |

Thanks!! I understood the problem.

→ Reply

8 years ago, # |

+110

It's time to announce how the random t-shirt winners are selected. We have a generator based on testlib.h (see code below) which will print the winning places. The seed will be the score of the first place in the tomorrow 8VC Venture Cup 2017 - Elimination Round.

Generator

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

using namespace std;

int main()
{
    rnd.setSeed(9889);

    set<int> winners;
    while (winners.size() < 25)
        winners.insert(rnd.next(26, 500));

    for (auto winner: winners)
        cout << winner << " ";
    cout << endl;
    
    return 0;
}

→ Reply

iliekcomputers

8 years ago, # ^ |

What if there are two people with the same ranks?

→ Reply

8 years ago, # ^ |

-13

"The seed will be the score of the first place in the tomorrow"

So if there are two people with the same ranks, score will be the same.

→ Reply

8 years ago, # ^ |

+12

Challenge succeeded!

Within this procedure we will assume that ties are broken by the time of last AC.

→ Reply

fruwajacybyk

8 years ago, # ^ |

← Rev. 2 →

+124

There is a tiny chance of the following scenario:

someone (person A) had rank 26-500 in Codecraft contest
person A leads in 8VC contest by a big margin,
person A checks if his current score gives him T-shirt for Codecraft

3Yes: person A gets T-shirt.

3No: person A does stupid hack and gets -50 pts. goto 3.

→ Reply

8 years ago, # ^ |

+62

61 84 129 162 170 190 227 239 247 251 272 292 312 344 352 355 363 365 386 415 420 433 442 443 466

→ Reply

8 years ago, # ^ |

+10

That's true. This list of users will be announced a bit later.

→ Reply

farmerboy

8 years ago, # ^ |

+13

Please announce the list of winning users, just for sure :D

→ Reply

tt.anhquynh

8 years ago, # ^ |

+13

The list has not been announced yet. :(

→ Reply

SAKT

8 years ago, # ^ |

+29

For the last t-shirt :)))

→ Reply

_Mr.T_

8 years ago, # ^ |

Nice

→ Reply

darkkcyan

8 years ago, # ^ |

:( My rank is 291 :(

→ Reply

sanket407

8 years ago, # |

-10

In problem C , getting WA on test 74 !! Stored all gym no. for each pokemon type in arralists and sorted ! Solution similar to that of tourist's ! http://codeforces.me/contest/757/submission/23807513 http://codeforces.me/contest/757/submission/23747486

→ Reply