Rebryk's blog

Codeforces Round #291 (Div. 2)
By Rebryk, 10 years ago, translation, In English

Hello, Codeforces!

I'd like to invite you to Codeforces Round #291 (Div. 2). It'll be held on Saturday, February 14 at 19:30 MSK.

Great thanks Maxim Akhmedov (Zlobober), Vasya Antoniuk (Antoniuk) for helping me preparing the contest, to Maria Belova (Delinur) for translating the statements into English, to Mike Mirzayanov (MikeMirzayanov) for the great Polygon platform.

Good luck everyone!

UPD: Score distribution will be the next — 500-1000-2000-2000-2500.

UPD: Editorial. Sorry for the delay)

  • Vote: I like it
  • +248
  • Vote: I do not like it

Comments Comments (216)
| Write comment?
»
10 years ago, # |
  Vote: I like it +43 Vote: I do not like it

wish it will be the way to DIV 1 :-)

→ Reply
»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

I hope your next round will be Div. 1 too :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    This round was a Div1 itself... :D

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What a shame ! I have a flight on that time. I will miss that round. I hope not to be busy at next contest on codeforces . Contests make addicted :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can participate virtually...

    → Reply
»
10 years ago, # |
  Vote: I like it -21 Vote: I do not like it

I want to be a Candidate Master...

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Not everyone gets what they want. For example I want to be a potato, but I can't... Probably the fact that my name isn't GLaDOS helps.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Hey! I just chanced upon this comment, and I see you've become a Master now. Congratulations.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks, my dreams come true xD

      → Reply
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I want to be a Master i wish my dreams come true like u

        → Reply
»
10 years ago, # |
  Vote: I like it +244 Vote: I do not like it

That's why I have no girlfriend...

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah! that's because making out in valentines day is too mainstream for programmers :3

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Unless you are a brogrammer.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it -24 Vote: I do not like it

hope i will be blue today ...

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Have Any Problem Of Valentine's Day?

→ Reply
»
10 years ago, # |
  Vote: I like it +86 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

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

Well done!

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Riiiiiiiiidam

tanx

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

I solved the problem using a Trie.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Try this

    2 1
    aaa
    aab
    aaa

    answer:
    YES

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It works on this case.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is test case 6, I think

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    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

    a

    a

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      OMG! Thanks...

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    9999999999

    And answer is:

    9000000000
    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

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

    WA for using hashes modulo 2^64.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      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
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah I'm pretty sure.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B ?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Count the number of groups of vectors (positioned to x0, y0) 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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it 
            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 .)

            → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        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
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

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

        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Or perhaps BigDecimal (seeing how this is Java code)

            → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        1. 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)
        2. If I change to float the behaviour is same for cin and scanf.
        3. If I use iterator and simply iterate over the slopes set before the calling cout<<slopes.size() and getting the right results.
        4. 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
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

please help me problem C

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      the answer is NO

      → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    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
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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
»
10 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Finally, top 10 for me!!! :D

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    1<=X<=10^18

    The number shouldn't contain leading zeroes.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

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

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

ML in problem C! :(

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +9 Vote: I do not like it

    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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can't assume things in a programming contest.

        → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any deterministic solution for C?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Suppose,this solution

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Why is rating update taking so long?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry. Got the mistake.

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    "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
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do I get MLE for problem D? http://mirror.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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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://mirror.codeforces.com/contest/514/submission/9858833.

      Anyways, thanks for your reply! :)

      → Reply
»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it +142 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    They are usually Div 1 coders that make new accounts.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

became expert for the first time

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      btw, which statement says that?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is editorial???

→ Reply
»
10 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            1 second on Codeforces is ~ 2 * 10^8

            → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution couldn't even read input if these two loops would TL

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem A has too many traps, and some of them is so boring, such as the fist digit can't be zero. I think it is meaningless......

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this give TLE for problem C? => http://mirror.codeforces.com/contest/514/submission/9853243

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem C, I did not understand why the hash value of a string will not overflow long long. And if I mod using a 4 digit prime then there should be collisions.

Given the clue, "The total length of lines in the input doesn't exceed 6*10^5. Each line consists only of letters 'a', 'b', 'c'.", there can be a string of length 10^5 whose hash value can be huge.

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi, somebody else used hash for the problem C?

I have WA #6 but I don't know why. Any help would be appreciated! :)

http://mirror.codeforces.com/contest/514/submission/9860261

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    The string must differ by one char, i.e. here's the test: 1 1 aa aa

    NO

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For hashing, if I use 101 then I get WA for test case 8 but if I use 257 then it is accepted. Why so?

I chose 101 because the ascii value of c 99, hence I thought 101 was enough.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you see a passed solution you think is wrong, is there a way to hack it in the practice room?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    NO

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      that's too bad, it would be nice to be able to double-check that your hack was correct, and also keep other people for thinking a wrong solution was actually correct.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces Round #291 (Div. 2) champion ppfdd got AC on problem C.

But there is massive hack for his code.

While hashing, He converted a,b,c to 0,1,2.

So the result for this input:

1 1
abc
babc

the output generates 

YES

which definitely WRONG ANSWER.

There should have been at least one test case regarding this factor. :3

→ Reply