Codeforces Round #291 (Div. 2)

9 years ago, # ^ |

Unless you are a brogrammer.

→ Reply

Alhelal_01

9 years ago, # ^ |

Relation with Problem.........Codefoces Guy.

→ Reply

Badry

9 years ago, # |

-24

hope i will be blue today ...

→ Reply

StoneCold_

9 years ago, # ^ |

+23

Why do you need to write that here ?

→ Reply

VladGanzha

9 years ago, # ^ |

Psss, nobody needs to write anything here

→ Reply

Badry

9 years ago, # |

sorry if you see that I shoudn't write like this..

→ Reply

Alhelal_01

9 years ago, # |

-9

Have Any Problem Of Valentine's Day?

→ Reply

alexyz

9 years ago, # |

+86

Today is the birthday of the first electronic general-purpose computer.
Happy Birthday ENIAC.
ENIAC

→ Reply

Fear_Is_An_Illusion

9 years ago, # ^ |

Only single yellow guys have such excellent knownledge

→ Reply

Fear_Is_An_Illusion

9 years ago, # |

+10

very interesting problem set, many thanks for not setting a valentines theme.. star wars theme was a pleasant surprise

→ Reply

nrg3

9 years ago, # |

← Rev. 3 →

+20

UPD: Finally, +17:-3, including: 1 triple hack, 4 double hacks, 1 last minute hack.

Well done!

→ Reply

Kareem

9 years ago, # ^ |

LOOOOL!!

→ Reply

9 years ago, # |

Hopeful of being a room winner for the first time :)

→ Reply

khashi246

9 years ago, # |

-10

Riiiiiiiiidam

tanx

→ Reply

9 years ago, # ^ |

I think so for myself! :D

→ Reply

Ximera

9 years ago, # ^ |

+25

That moment when you understand Persian :)))

→ Reply

Batman

9 years ago, # ^ |

I ridam too

→ Reply

9 years ago, # |

I got WA at #6 on problem C. Anyone knows what it is about?

I solved the problem using a Trie.

→ Reply

9 years ago, # ^ |

A hashmap is enough, given the constraints, i think. My approach uses m.log(n)

→ Reply

happiness777

9 years ago, # ^ |

can you explain your solution? I also used Trie but got TLE on testcase 10.

→ Reply

sahildua2305

9 years ago, # ^ |

Hey, can you please explain your approach using hashmap. I couldn't solve the problem during the contest. But have to solve it anyhow, now.

→ Reply

AClover

9 years ago, # ^ |

Try this

2 1
aaa
aab
aaa

answer:
YES

→ Reply

9 years ago, # ^ |

It works on this case.

→ Reply

9 years ago, # ^ |

I've used hashing. It gives right for your test but fails on test #6.

→ Reply

alibi

9 years ago, # ^ |

This is test case 6, I think

→ Reply

9 years ago, # ^ |

← Rev. 4 →

~~I think I found the case:~~

1 1
aaa
aaa

~~Answer: NO, because there should be exactly 1-symbol difference.~~

Oops, didn't notice comment on the bottom

→ Reply

minimario

9 years ago, # ^ |

← Rev. 3 →

I think Pretest 6 has a string equal to original string, when problem says they must differ by exactly one position. Such as this, output should be "NO":

1 1

→ Reply

9 years ago, # ^ |

OMG! Thanks...

→ Reply

9 years ago, # ^ |

You're right :-(. I didn't pay attention to '**exactly** one position'. Now it works. Thanks!

→ Reply

dilipkasana

9 years ago, # |

How to solve A.Or what is test 8 for problem A.

→ Reply

mredigonda

9 years ago, # ^ |

← Rev. 2 →

I failed this pretest in my first submission, i guess it's something like:

9999999999

And answer is:

9000000000

→ Reply

AtomRush

9 years ago, # ^ |

number shouldn't have leading 0 so check if 1st character is 9 or not if it is nine do nothing if not change to 9-s[0] or not accordingly if it is greater than 4 or not . rest all was just checking if character if greater than 4 change to 9 -character less let it be

→ Reply

dilipkasana

9 years ago, # ^ |

So what is anser for 9999.is it 9 or 9000 or what

→ Reply

AtomRush

9 years ago, # ^ |

9000

→ Reply

SHCE

9 years ago, # ^ |

I don't know... but by 'with no leading zeros' I understood that you can't write 0003 (for example). I think that the statement should say something like 'with the same nuber of digits'.

What do you think?

→ Reply

ajinkya1p3

9 years ago, # ^ |

The problem should have mentioned "with the same number of digits"! :(

→ Reply

dilipkasana

9 years ago, # ^ |

← Rev. 2 →

Yes , actually this is very poor statement in the question.I am very disappointed like this type of problem statement [user:Zlobober][user:antoniuk].I am also wonder how some top guys think about this in the only first chance.

→ Reply

Solar

9 years ago, # ^ |

Some number where first digit is 9, i guess. Like 9631 with answer 9331.

→ Reply

waterfalls

9 years ago, # |

← Rev. 2 →

What was the hack test on C?

Overflowing the length in a char array? (up to 6*10^5)

Just time outs?

WA with the same string as in dict?

I submitted a brute force that passed the large pretest (took some work) just to hack on C XD, thinking it was overflowing the char array, but everyone used cin >> string so nothing for me

Somehow no one hacked my solution (maybe not enough time)

EDIT: WHAT, my brute-force C passed systests...

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

+30

ML/TL for generating all possible strings and putting them into map.

WA for using hashes modulo 2^64.

→ Reply

kraskevich

9 years ago, # ^ |

← Rev. 2 →

+13

Not necessary 2^64. I have hacked a few solutions that use one hash modulo 10^9 + something. It is also possible to find a collision for two hashes, too(but this generator is slightly harder to implement).

→ Reply

9 years ago, # ^ |

← Rev. 2 →

I don't think people are so brash, but maybe this is the case

UPD. Turns out that post had only Russian version. That post is about hash collision generator, code: http://pastebin.com/JfTEUwCe

→ Reply

b0mb3r

9 years ago, # ^ |

The one I hacked is looping with strlen(s), which is, of course, linear time.

→ Reply

9 years ago, # ^ |

pretests are a bit weak, i think. I got pretests passed in my first approach where space complexity was O(n^2) [Unnecessary though]

→ Reply

HandIeNeeded

9 years ago, # ^ |

O(Nsqrt(N)) didn't pass. T^T

→ Reply

Temirulan

9 years ago, # |

Is in the problem E answer is polynomial of degree ~100?

→ Reply

const_int_magic

9 years ago, # ^ |

I think matrix exponentiation is the answer..

→ Reply

Khagan

9 years ago, # |

Is solution of 514E - Darth Vader and Tree related to matrix multiplication?

→ Reply

const_int_magic

9 years ago, # ^ |

yeah I'm pretty sure.

→ Reply

Ronnie007

9 years ago, # ^ |

I think that it's similar to this problem: https://www.hackerrank.com/contests/w10/challenges/towers.

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

+20

Let's say that dp[i] is equal to number of vertices at distance i. d[i]<=100, so you need only values of dp[i-1]...dp[i-100] to calculate dp[i]. And this calculation can be represented by matrix multiplication, where variables are dp[a],dp[a-1],...dp[a-100], and you are multiplying this vector by some matrix to get dp[a+1],dp[a],...,dp[a-99].

In order to solve original question you have to add one more variable, ans[i]=ans[i-1]+dp[i].

→ Reply

9 years ago, # |

How to solve B ?

→ Reply

b0mb3r

9 years ago, # ^ |

Count the number of groups of vectors (positioned to x₀, y₀) so that for each pair of vectors in the group, their dot product is zero, and no vectors in different groups give zero as their dot product.

→ Reply

AtomRush

9 years ago, # ^ |

I did a brute force . take the position of gun let it be a,b . then for i=1..n .maintain a array called as killed[i] denoting if you killed ith enemy or not. start a loop from 1 to n check if killed continue. otherwise break .let this position be m. find coefficient of line passing through a,b and this point then for elements m+1..n check if it comes under the line .if it does mark killed[] =1 ; check if all are killed if it did break and print the count

→ Reply

9 years ago, # ^ |

← Rev. 2 →

I construct a, b, c in equation ax+by+c = 0 for (x0,y0) with (xi,yi) , i = 1..n. And you should make gcd(a,b,c) = 1 and a > 0. After that, you can sort n equation (a,b,c). Remove (a_i,b_i,c_i) == (a_j,b_j,c_j) by unique in C++. So that you have the result in O(NlogN)

→ Reply

9 years ago, # ^ |

Hey i did the same but got WA on 8th test case ..

→ Reply

9 years ago, # ^ |

http://ideone.com/uzEJcW

My code link ..

→ Reply

waterfalls

9 years ago, # ^ |

Try this test:

→ Reply

9 years ago, # ^ |

You can see my code

→ Reply

Tudor

9 years ago, # ^ |

you get all N points and you insert tan((y-y0)/(x-x0))in an array tan and the answer is the number of different numbers of array tan .

→ Reply

nc.duy

9 years ago, # ^ |

well, let's count the number of the different slope k = (y — y0)/(x — x0). I think so!

→ Reply

deinier

9 years ago, # ^ |

I did that but I lost 100 point due epsilon precision. What is the default precision we need to use to compare two doubles?

→ Reply

9 years ago, # ^ |

Consider two doubles a and b equal if fabs(a-b)<=EPS, where EPS is something like 10^(-9).

→ Reply

deinier

9 years ago, # ^ |

Then, the number should be 10^(-9). I used 10^(-4) and 10^(-6), getting WA in both. AC after 10^(-9) with the same solution.

→ Reply

chaotic_iak

9 years ago, # ^ |

2 -10000 -10000
7711 946
946 -3235

Correct answer is 2. With epsilon 10^- 6, the answer seems to be 1; the numbers are close enough. (If you're wondering, the differences 6765, 10946, 17711 are consecutive Fibonacci numbers, which is why $\text{[math]}$ .)

→ Reply

deinier

9 years ago, # ^ |

Got it! Thanks.

→ Reply

calmhandtitan

9 years ago, # ^ |

← Rev. 4 →

in such cases when you are not sure of what value to assign to eps, you can use

set<double>

and let the compiler do the rest.

I did the same, and it worked like charm. 9834951

→ Reply

maverick_xiii

9 years ago, # ^ |

I tried storing numerator and denominator seperately as int after taking gcd, and it worked. You can view the solution here

→ Reply

ashish1610

9 years ago, # ^ |

Find the slope of each point with respect to gun. Store them in set. Print the size of the set.
If denominator while calculating slope is zero, assign it some infinite value. I hope it helps.

→ Reply

const_int_magic

9 years ago, # ^ |

Umm did you store the slopes in a double? There could be precision errors then.. not sure though. I prevented myself from doing it this way due to the possibility of this error.

→ Reply

ashish1610

9 years ago, # ^ |

← Rev. 2 →

Yeah stored them as long double. I hope there are no precision errors.
Edit: It passed.

→ Reply

dthreatz

9 years ago, # ^ |

I stored each slope in a set of doubles and my solution passed tests. Guess I got lucky.

→ Reply

AkshajK

9 years ago, # ^ |

An alternative would be to write a fraction class as such:

class Fraction {
	public int a;
	public int b;
	public Fraction(int a, int b) {
		this.a = a;
		this.b = b;
	}
	@Override
	public boolean equals(Object ff) {
		Fraction f = (Fraction)ff;
		return (this.a*f.b == this.b*f.a);
	}
}

→ Reply

qwed0

9 years ago, # ^ |

Or perhaps BigDecimal (seeing how this is Java code)

→ Reply

mketa

9 years ago, # ^ |

← Rev. 2 →

I calculated the slope of the line (y-tY)/(x-tX) and stored it in a map. In the end I just print the size of the map. Can anyone help me with the complexity of this?

→ Reply

calmhandtitan

9 years ago, # ^ |

I guess in the worst case it would be

O(N*logN)

as you have to insert N different slopes in worst case, and each insertion would take at most logN time.

→ Reply

MiltonEiji

9 years ago, # ^ |

I counted the number of differents tans, but I got WA on test 8. Anyway, what is the test 8?

→ Reply

bayram98

9 years ago, # ^ |

( area == 0 ) this is my solution which WA on test 8 ( area < 0.00001 ) this AC

→ Reply

bayram98

9 years ago, # ^ |

you choose x1 y1 one point and erase it and ans++ then erase which point on line x,y to x1,y1
if which points on line erase it

→ Reply

9 years ago, # ^ |

I sorted the points by their slope with (x0,y0) and then compared p[i] and p[i-1] using (p[i].y-y0)*(p[i-1].x-x0) == (p[i-1].y-y0)*(p[i].x-x0). If False, increment the number of shots.

→ Reply

ragib06

9 years ago, # ^ |

← Rev. 2 →

I also counted number of unique slopes with a c++ stl set (9839367). It got WA. But surprisingly, replacing scanf with cin got AC !!!

Can somebody explain what's here:

WA: http://paste.ubuntu.com/10226578/

AC: http://paste.ubuntu.com/10226581/

→ Reply

Wasted

9 years ago, # ^ |

Guys, it`s magic I just move declaration of set at WA code to main scope and got right answer

Code

Full 8 test

WTF?

Seems like that this magic feature forks only under MinGw G++ 4.8 and 4.9 (at Ms works fine) In my Linux machine with g++ 4.9 with same compile keys it works fine.

Can someone make disasembly of this code(dont have win machine with Mingw right now) or explain ?

→ Reply

__Joker

9 years ago, # ^ |

← Rev. 2 →

Yes, seems magical. Did spent quite some time yesterday. Didn't disassemble as could not produce on local. I did played around quite some using the "custom invocation" of the code forces and have noticed the following(not sure how relevant they are).

The problem seems to be, the set is counting some "similar" doubles as different. the results produce using scanf is always higher than what it should result from cin(which we think is right)
If I change to float the behaviour is same for cin and scanf.
If I use iterator and simply iterate over the slopes set before the calling cout<<slopes.size() and getting the right results.
Personally feeling may be scanf is setting constant or variable which is affecting the double comparison on the set.

Whatever be the case, please update if anybody find the reason for anomaly.

→ Reply

andreyv

9 years ago, # ^ |

I think this may be the answer: https://isocpp.org/wiki/faq/newbie#floating-point-arith2

→ Reply

__Joker

9 years ago, # ^ |

Yes, something like this might happened. Thank you for a nice link.

→ Reply

bayram98

9 years ago, # |

please help me problem C

→ Reply

b0mb3r

9 years ago, # ^ |

For each query string s with length L, there are 2L possible variants (i.e. replace each character by the other 2, and since you can do this only once, there are 2L such possibilities). You need an efficient data structure to check whether the variants are in one of N strings. I think using trie is sufficient enough.

→ Reply

9 years ago, # ^ |

I use set in C++ to save n string in set S. After that, with string i in m string query, consider position j, we have string x = s and set x[j] = {'a','b','c' \ x[j] != s[j]}. You can find x in set S in O(log(N)). I think it ok because The total length of lines in the input doesn't exceed 6·10^5

→ Reply

nc.duy

9 years ago, # ^ |

well, i solve it with map (as set) and i couldn't submit it in 2 seconds :(((((

→ Reply

gxnncrx1993

9 years ago, # ^ |

"You can find x in set S in O(log(N)) " Not true. Comparing two strings needs O(length(x)) if they have a very long common prefix, so it's O(length(x)log(N)). Consider this case: 1 1 aaa...aa aaa...ab (The first consists of 300000 'a' and the second consists of 299999 'a' and one 'b')

→ Reply

Tudor

9 years ago, # ^ |

you make a robin-karp(hashing) all strings of the dictionary but with a different letter at each step ( if str[i]=='a' you get 'b' and 'c') and you insert this value in a hash at each step... and for queries you make a classic robin-karp at string Q and check if this value is in hash... You should double hashing for safety(two different bases and two different MOD)

→ Reply

Czarli

9 years ago, # ^ |

I'm not sure if it's correct solution, but you can try to do it with hashing. For each n strings, calculate their hashes without each single letter. Next, do the same with strings from query but this time if any hash of ith string existed before, then answer is "YES" otherwise answer is "NO". There might be some problems, when some strings are equal, but it's not that hard to deal with.

→ Reply

nc.duy

9 years ago, # ^ |

let's define that: a is number of character 'a' b is number of character 'b' c is number of character 'c' we need to find out at least one element in this set: { [a — 1][b + 1][c], [a — 1][b][c + 1], [a][b — 1][c + 1], [a + 1][b — 1][c], [a + 1][b][c — 1], [a][b + 1][c — 1] } and compare them with string t to satisfied the condition! we should use map(or set) to save the input string with [a][b][c]. I think it could process in 3 seconds :D !

→ Reply

dcordb

9 years ago, # ^ |

I think that is wrong, check this test case: 1 1 caaa aaab

the answer is NO

→ Reply

farizazmip

9 years ago, # |

← Rev. 2 →

4 unrated handle spotted the top 5 in current standing! They're unpredictably good o.O

UPD: In final standing the number decreased become two and both of them are the top 2! Fast system testing by the way.

→ Reply

myown1209

9 years ago, # |

To solve problem C, Is "c++ STL set" just enough?

→ Reply

9 years ago, # ^ |

I think it's not, I have used hashing to solve it. BTW, during the contest I wanted to hack a solution with set, but when I tried to send the test it was loading for a while and then nothing — I had to try again and then happened the same. If it turns out that set isn't enough I will be kinda sad :D

→ Reply

Hepic_Antony_Skarlatos

9 years ago, # ^ |

Unfortunately for me,set is not enough. I passed pretests,but in test 20 I got Time Limit.

→ Reply

determinism

9 years ago, # |

I've used unordered_map in problem C, but I've got hacked. What could be the problem?

→ Reply

kraskevich

9 years ago, # ^ |

← Rev. 2 →

The time complexity of your code is O(n^2) in the worst case. I used a test with two arbitrary strings of length 3*10^5 to hack your solution.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

I got TLE in test 28 :( .. my time complexity is O(m * l * log(n)) where, l is length of string in each query. m,n are from problem statement. Can anyone explain how this doesn't run in the time limits? Upd: (m*l)<=6*10^5 (from statement) and log n cannot exceed 18

→ Reply

kraskevich

9 years ago, # ^ |

The time complexity of your solution is not O(m * l * log(n)). Just consider the input that consists of two string: each of them is a letter 'a' repeated 3 * 10^5 times. Your solution makes O(n^2) comparisons for this test.

→ Reply

stopnot

9 years ago, # |

i am submitting div2 3rd ..but its not showing me the case i m wrong on...!!!!

→ Reply

9 years ago, # |

I am very sad about problem D. This is my code in contest and this is my code after contest. They different exactly one positionL = 0 and L = 1. If I have 10s to think that, then I can accept problem D and my standing not low.

→ Reply

9 years ago, # |

← Rev. 2 →

-8

Finally, top 10 for me!!! :D

→ Reply

MBSNWMG

9 years ago, # ^ |

I'm the pathetic No.11 QuQ...

→ Reply

9 years ago, # |

I've used Hashing to solve C. Here's my code 9849480.
It failed on the test #27. It's "..." testcase.
What's wrong with my code?

→ Reply

9 years ago, # ^ |

Collision?

→ Reply

9 years ago, # ^ |

Maybe...

→ Reply

9 years ago, # ^ |

WA on same case :(

→ Reply

9 years ago, # ^ |

← Rev. 2 →

My hashing has collision. I add checking function for 2 strings when their hashes are the same and it became accepted!

→ Reply

hippie

9 years ago, # |

+11

Problem A , in my opinion has a very ambiguous problem statement what is the answer to:- 90 90 or 9?

→ Reply

9 years ago, # ^ |

-12

1<=X<=10^18
The number shouldn't contain leading zeroes.

→ Reply

hippie

9 years ago, # ^ |

My point is, they should have explicitly mentioned whether the number should not have leading zeroes before printing the answer, or during computation.

→ Reply

9 years ago, # ^ |

-13

Read the problem statement. You should not have a zero at starting index after performing inversions. 9 is not allowed as it is actually "09", which has trailing zeroes

→ Reply

coder1748431

9 years ago, # ^ |

I asked author what could be the answer for 9 as it was ambiguous and he said "No comments" -_-'

→ Reply

hsnprsd

9 years ago, # |

ML in problem C! :(

→ Reply

9 years ago, # |

I got MLE on problem C at #19. I solved the problem using a Trie. Can anyone have a look on my submission, please?

→ Reply

happiness777

9 years ago, # ^ |

← Rev. 2 →

I am stuck at MLE, too. this solution seems to use Trie but does not cause MLE... I don't know why, though...

→ Reply

http://codeforces.com/contest/514/submission/9843858

9 years ago, # ^ |

The solution is embarrassingly similar to mine. Yet i get MLE. WOW! :-)

→ Reply

uSeemSurprised

9 years ago, # ^ |

That is really strange my submissions in practise is also giving MLE on test #19.

→ Reply

Ra8

9 years ago, # ^ |

In your query function, you are passing the whole string and doing recursion. So each time you call query, the whole string will be copied and this increases the memory as well as the time. So I think if you just pass the string by reference string& s instead of string s it might resolve the MLE problem.

→ Reply

AkshajK

9 years ago, # |

Can someone explain the algorithm behind this code: http://codeforces.com/contest/514/submission/9850107

→ Reply

natsukagami

9 years ago, # ^ |

← Rev. 4 →

It's a technique which can be used to find max(a[i..j]) when we have queries of increasing i and js. However the code given by you is not that efficient. Take a look at this submission: We can use a C++ 'deque<int>' to answer all the queries in a total of O(n) time.

It's lengthy to explain why the algorithm works (after all it's not too complicated), but the whole operation is expressed as follow:

Everytime we increase j (a.k.a push a[j] into processing) we remove deque.back() while it's smaller than a[j], then deque.push_back(a[j]).
Everytime we increase i (a.k.a pop a[i] from processing) we remove deque.front() from the deque if deque.front() is a[i].
The answer for each i..j query is always deque.front().
In order to limit the sum, each time we increase j (process the next element), we increase i until {sum} ≤ k

→ Reply

hellman_

9 years ago, # ^ |

Thanks much for the algo, it's really simple. In step of increasing j you forgot to push_back(a[j]).

→ Reply

Farsan

9 years ago, # |

+14

In my opinion Problem A description was not clear.For input 90 output should be 9 according to problem statement but test data says answer is 90."Length of output number must be equal to length of input number" this single line of statement should have been added.

→ Reply

stargazer

9 years ago, # ^ |

-6

Nope. "The decimal representation of the final number shouldn't start with a zero."

→ Reply

angelg

9 years ago, # ^ |

You could've assumed that you just had to remove the leading zero.. It's not clear...

→ Reply

stargazer

9 years ago, # ^ |

You can't assume things in a programming contest.

→ Reply

M.Mahdi

9 years ago, # |

Any deterministic solution for C?

→ Reply

ivanilos

9 years ago, # ^ |

I solve it using trie, created a trie for each different length of strings and brute-forced to check if there was a string in the respective trie in each query.

→ Reply

_harun

9 years ago, # |

For problem C,why people get TLE in test #19?

Suppose,this solution

→ Reply

Basement

9 years ago, # ^ |

O(3 ^ len)

→ Reply

_harun

9 years ago, # ^ |

which solution will pass? How to optimize it?

→ Reply

kimbbakar

9 years ago, # ^ |

You can use Trie data structure ....

My code for problem C : http://codeforces.com/contest/514/submission/9843731

Hope , this will clear your concept about Tire .

→ Reply

9 years ago, # |

+13

Why is rating update taking so long?

→ Reply

9 years ago, # ^ |

Even systest is freezed in the end for some reason...

→ Reply

percywtc

9 years ago, # ^ |

Updated:)

→ Reply

choke

9 years ago, # |

I can't find my mistake about C problem, I used hash with unsigned long long

this is my soution: 9844038

Is there any problem if I substract from unsigned long long?

This is another similar solution, he used two hash, but I'm sure colisions is not my mistake ...somebody?

9836207

→ Reply

http://codeforces.com/blog/entry/16365#comment-212594

9 years ago, # ^ |

→ Reply

ashish1610

9 years ago, # |

← Rev. 2 →

Sorry. Got the mistake.

→ Reply

Hepic_Antony_Skarlatos

9 years ago, # |

I am sad I took TLE in C using set-stl,but I am happy because I achieved my first goal that was blue. Now it is div1. I hope to achieve that soon :D. I say that,because I want gray-green users that with "correct" practise everyone is able to achieve everything,and never give up.

→ Reply

ilim

9 years ago, # |

Guys is there anyone who could help me understand why my submission gives wrong answer in test case #6? By my calculation the output kills 3 droids even though checker comment states my solution kills only 2 of them. Any help is greatly appreciated.

→ Reply

misiek08

9 years ago, # ^ |

← Rev. 2 →

"How many shots from the weapon of what type should R2-D2 make to destroy the sequence of consecutive droids of maximum length?"

You have been destroyed 1, 3 and 4th droid, so your sequence has length 2. In the correct answer, 2, 3 and 4th droid is destroyed, so the sequence has — better — length 3.

Word 'consecutive' is the key.

P. S. Sorry for my english :)

→ Reply

sajo

9 years ago, # |

Why do I get MLE for problem D? http://codeforces.com/contest/514/submission/9850749

I have used segment tree so 4*N*5 memory, plus one more array of N*5 (both int). As N is just 100000, this should not exceed 256MB memory limit.

→ Reply

Ra1nWarden

9 years ago, # ^ |

I also did segment tree and passed. Maybe you can take a look. 9865631

→ Reply

sajo

9 years ago, # ^ |

Yeah, I got it later. I am creating 2 new arrays p,q in every call to query. This must be adding up to the memory as the arrays must get stored in the recursion stack. (Not sure, but I think this may have been the cause). When I removed that part, and instead passed an array to the query function, I got my solution to pass. http://codeforces.com/contest/514/submission/9858833.

Anyways, thanks for your reply! :)

→ Reply

buggy.code

9 years ago, # |

+17

My 2 cents, since everyone writing about problem C seems to have tried hashing:

The similarity condition imposed is Hamming distance = 1. This is a metric space and can be solved with any of the metric tree structures. I used a BK-tree, and I got AC.

→ Reply

R.A.X

9 years ago, # ^ |

Your solution is interesting. Can you explain your solution ??

→ Reply

keyvankhademi

9 years ago, # |

+142

sdfdsfsdfsd no one can reach real coders (Even cheaters!)

→ Reply

R.A.X

9 years ago, # ^ |

How he managed to get the solutions before starting of the contest ??

→ Reply

slycelote

9 years ago, # ^ |

See that '00:28' near his handle? It means he's a virtual contestant (submitted the solutions after the contest finished).

→ Reply

9 years ago, # ^ |

That's virtual contest. I think he first took 5 submissins which passed all tests, started virtual contest and submitted them on the first minute.

→ Reply

minimario

9 years ago, # |

When editorial is going to come? It will be interesting to see author's solutions to these problems :)

→ Reply

9 years ago, # ^ |

+12

I'm working on it.

→ Reply

9 years ago, # ^ |

Done.

→ Reply

miloserd

9 years ago, # |

+12

Still waiting for jury to start upsolving... :/

→ Reply

ashchk

9 years ago, # |

How could always the new comers be in the top list in division 2 ?!!!

→ Reply

dthreatz

9 years ago, # ^ |

They are usually Div 1 coders that make new accounts.

→ Reply

StoneCold_

9 years ago, # |

Is O(M*N*log^2(N)) using segment tree supposed to TLE for problem D ?

→ Reply

9 years ago, # ^ |

No.

→ Reply

manetsus

9 years ago, # |

+31

Rebryk, I think data set of problem C ( 514C - Watto and Mechanism ) of today's contest was a little bit weak. Consider this submission: 9852063 which fails the test case:

1 1
abc
aa

Should not the output be NO? It gives YES instead.

Thanks. :)

→ Reply

9 years ago, # ^ |

+14

Yes. You're right. It's my fault.

→ Reply

mayank_kumar

9 years ago, # |

became expert for the first time

→ Reply

gvaibhav21

9 years ago, # |

i am getting memory limit exceeded on test 18 in C... i have used map<string,int> to do it.. can anyone suggest the reason for this? and also what would be a more memory efficient way of doing this question...

→ Reply

FxF

9 years ago, # ^ |

When you use if (f[s]) with a new string s, it makes f[s] = 0 and therefore uses |s| additional bytes of memory.

Try to use set <string> f and if (f.find(s) != f.end()) instead of map <string, bool> f and if (f[s]).

→ Reply

gvaibhav21

9 years ago, # ^ |

thanks a ton :D that was a new thing for me :D

→ Reply

mrgreen

9 years ago, # |

Can somebody please check why I got a run time error on test_25 http://codeforces.com/contest/514/submission/9848840

I have tried the test case on my computer and it worked.

→ Reply

fadlimfp94

9 years ago, # |

this contest really interesting though i didn't solve any problem. actually i wonder why i can't solve at least problem A, and then i know that because some case (case 8) like this:

input :91730629

my output : 1230320

answer : 91230320

in my opinion, i think my answer actually didn't wrong because we could make the minimum positive number by inverting 1st, 3rd, 6th, and 8th character from the input and discard the leading zero. is somebody has the same opinion with me?

→ Reply

R4mt1n

9 years ago, # ^ |

← Rev. 2 →

the length of the output should be the same as inputs ! :)

→ Reply

fadlimfp94

9 years ago, # ^ |

really? then i should miss that in the description :)

btw, which statement says that?

→ Reply

microtony

9 years ago, # ^ |

It is exactly because the statement never said that you can discard any digit. Which means you can only invert digits but then the result cannot contain leading zero(s).

You should not make your own assumptions.

→ Reply

shm0007

9 years ago, # ^ |

Problem description says: "transform the initial number x to the minimum possible positive number by inverting some (possibly, zero) digits". so you can't discard leading zeros,only operation you are allowed to do is invert some (or zero) digits.

→ Reply

NickyByrne

9 years ago, # |

← Rev. 2 →

I used TRIE in Problem C but perhaps it should be String Hash? Anyway I FST beautifully.

→ Reply

NickyByrne

9 years ago, # |

I used TRIE in Problem C but perhaps it should be String Hash? Anyway I FST beautifully.

→ Reply

alibi

9 years ago, # |

Where is editorial???

→ Reply

9 years ago, # ^ |

+20

Sorry, I'm a slowpoke

→ Reply

9 years ago, # ^ |

Done.

→ Reply

alibi

9 years ago, # ^ |

Good job)

→ Reply

BIGBALLON

9 years ago, # |

-6

I got AC on 514B - Han Solo and Lazer Gun,but I alos have a question. gun is situated at the point (x0, y0). can stormtrooper at (x0,y0),too ? if so, i think some code maybe got WA。

→ Reply

9 years ago, # ^ |

It is guaranteed that no stormtrooper stands at the same point with the gun.

→ Reply

Armyx

9 years ago, # |

← Rev. 2 →

I am trying to solve C problem. I see a lot of solutions where there is something like this :

for (int i = 0; i < n; i++) { ... for (int j = 0; j < s.length; j++) {

where n <= 3*10^5 and s.length <= 6*10^5 , so in worst case it works in 9*10^10 ~ 10^11 . Why it pass ? How can I calculate the worst complexity withing given time limit ?

→ Reply

svlads

9 years ago, # ^ |

if n = 3 * 10^5 s.length can't be 6*10^5, because 6*10^5 in the worst is a sum of all s.length

→ Reply

Armyx

9 years ago, # ^ |

Yes, thank you. I misunderstood problem statement. Anyway, is there any good algorithm to determine the worst complexity withing given time limit ?

→ Reply

svlads

9 years ago, # ^ |

← Rev. 3 →

What does it mean: withing given time limit?
Time limit in this problem is 3sec.

→ Reply

Armyx

9 years ago, # ^ |

← Rev. 2 →

I want to know algorithm with 2 inputs complexity, time limit . The output will be answer YES/NO For example:

C = 10^6 T = 1 s => YES

C = 10^19 T = 1 s => NO etc

→ Reply

svlads

9 years ago, # ^ |

1 second on Codeforces is ~ 2 * 10^8

→ Reply

nrg3

9 years ago, # ^ |

Total length of all strings in input is 6*10^5, thus, the code you described does 6*10^5 iterations.

→ Reply