qoo2p5's blog

By qoo2p5, 3 weeks ago, translation, In English,

Hi!

On Monday, July 31, 2017, at 14:35 UTC rated Codeforces Round #427 for participants from the second division will take place. As always, participants from the first division can take part out of competition.

The problems for this round were prepared by me. Many thanks to Alexey Ilyukhov (Livace) for help in preparations of the round and testing the problems, AmirReza PoorAkhavan (Arpa) for proofreading the statements and testing the problems, Gaev Alexandr (krock21) for testing the problems, Nikolay Kalinin (KAN) for the round coordination and, of course, Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon platforms.

The round will last for 2 hours, and you will be given 6 problems. I recommend you to read the statements of all problems. I hope everyone will find an interesting problem!

Scoring will be announced before the round.

Scoring: 500 — 750 — 1250 — 1500 — 2250 — 2250.

UPD.

Thanks for participating!

The editorial is here.

Congratulations to the winners!

Div2:

  1. ywwyww

  2. nick452

  3. JustAnAverageCoder123

  4. cxt

  5. wa1tz7I9

Div1:

  1. dotorya

  2. rajat1603

  3. anta

  4. Kaban-5

  5. HellKitsune

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

»
3 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

wow, already another round, i'm exited!

»
3 weeks ago, # |
  Vote: I like it -174 Vote: I do not like it

Damnit codeforces, two consecutive rounds is too much.

»
3 weeks ago, # |
  Vote: I like it +40 Vote: I do not like it

Hope short statements like your announcement :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how can registration? please tell me

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

2 rounds in 2 days..amazing..

»
3 weeks ago, # |
  Vote: I like it -29 Vote: I do not like it

Two consecutive rounds.. in one time, when some people just are not able to take part — they are sleeping, including me :(

»
3 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

2 rounds in 2 days?

sign me the FUCK up good shit go౦ԁ sHit thats some good shit right there right there if i do ƽaү so my selfi say so thats what im talking about right there right there (chorus: ʳᶦᵍʰᵗ ᵗʰᵉʳᵉ) mMMMMᎷМ НO0ОଠOOOOOОଠଠOoooᵒᵒᵒᵒᵒᵒᵒᵒᵒ Good shit

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    You look like you might need to take a break.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I think I might've taken the caffeine instead of the decaf. :(

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can't register. Says I'm already registered for the contest. Can someone help?

EDIT: Fixed now.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Errr...That means you ARE already registered and dont need to register any more...do you need help to un-register or what? :P

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope, I'm not registered, and it still keeps saying "already registered". I know how to unregister.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        If you look up the users who are registered for the competition, you will see your name there! It says that you are registered!

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Will the problem statements as short as this announcement? :)

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

wow double div2 rounds! Brilliant!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Yeah, I think it's to make up for all the unrated rounds we had last month.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Whom About this round ?

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Two consecutive round that is awesome ! Thanks qoo2p5

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

3 day after today will be another contest so we should say : one week ,3 contest,what a beautiful week!!!!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    There should be a coding weak every few months or so...where we get a competition each day of the week!

    (Or will it be too much? )

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      <<There should be a coding weak every few months or so...where we get a competition each day of the week!>> that will be amazing ^_^ <<(Or will it be too much? )>> are you serious????

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Well it would be t000000000 much for the people like that guy above with 84 downvotes who said "Damnit codeforces, two consecutive rounds is too much."

        T00 much? lmfao!

        I'll tell you guys what too much is, too much is the gap between these competition,thats what too much is! LOL :P

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly. Hope we'll get such kind of "Beautiful Weeks" in future also..

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

WOOOWW so good that 2 contests in 2 days

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope electricity will be fixed till the beggining of the contest :D

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Wow, I like have a codeforces round everyday.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

nice

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Wrong tag 417! Please edit.

»
3 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

is it going to be rated?

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

I had one question. is it rat

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Another Round very quickly.. So exited..

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Not able to submit even though I'm registered.Anyone facing the same problem?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, same problem, I couldn't submit for the past 10 minutes

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Second question is not accepting soln , submit link is not working for second ques, what the hell is going on

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Too difficult C these days .

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    C is at an acceptable difficulty IMO, but i don't think that D is a problem that worth only 1500 points...

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

some guy just opened an account and solved all 6 problems .... (I think this is a hattrick if memory serves me right) -_-

At this rate, there will be fewer div2 coders than div1 coders

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i wanna know how opening another account helps?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      be a grandmaster first then open a new account and participate in div2 contest. You will be quite surprised yourself to see your performance

»
3 weeks ago, # |
Rev. 2   Vote: I like it +48 Vote: I do not like it

Answering questions in this round was like.

We're sorry if the statements was not as clear as we thought

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Haha, sould've just written that in the statement.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    30 minutes spent after i came up with that. It is illogical to have 2 stars on a grid at the same position (and how can he see two starts at the same point?) so it was better to write it in the statement. (Me personally got the point when i realised that number of stars could be up to 10^5 and grid has 10^4 cells)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Usually in this type of statements, I see that the phrase "All thingys have distinct co-ordinates" is given in such cases. Like in problem F, you are told that there is no road that connects a city to itself. So if you see no such statement, you usually take the worst case interpretation. So from my point of view, I don't think there was anything wrong with the statement

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      That's why statements weren't changed

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    prefix sums

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I (hope I) solved it with 11 2-dimensional Fenwick trees.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Super overkill, dude...

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes...I realized that after the contest. Since the brightness of the stars is fixed for given moment, then we don't need the Fenwick tree at all. Still, my solution passed the system test, but I agree there's a cooler approach. :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the same :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain that solution? I solved it using dp.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Let's for a moment assume that time stops and brightness of the start doesn't change at all. How could we then calculate the total brightness for a given rectangle? A 2-dimensional Fenwick tree does this in O(log100 * log100) per query.

        However, stars' brightness change in time over time. It's easy to notice their brightness state is cyclic and after c + 1 seconds it goes back to the initial state. Since c is quite small (up to 10), we can maintain c + 1 Fenwick trees for each remainder of t % (c + 1).

        Note that even though this works, as szawinis mentioned, this approach is quite an overkill and calculating the 2D prefix sum is much less verbose and easy approach.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For every initial s calculate 2d prefix sums of stars so we can answer queries in O(c), because for each initial star brightness we know how many were there in the given rectangle and we can easily calculate what will be the brightness at the given time for this particular brightness.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How exactly to sum more than one star in O(c)? Please explain a bit for me, thanks

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it +7 Vote: I do not like it

        I don't totally know mraron's solution, but here's mine (got AC on sys test):

        Check every star, for every t (it is 0-c, so from 0 to 10), add it to the star's coordinate's and store the sums for a given time and given coordinates in a 3d array [t][x][y] (it's [11][101][101]).

        After you have the sum for every coordinate and every t, you can calculate 2d prefix sums for the table ([101][101]) and after that you can answer every query in O(1).

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I see, I oversight to generate all possible t [0,10], my function to sum it is just plain wrong answer, and TLE. Thanks!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you calculate a 2D prefix in less than O(n2) time?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        We can calculate 2d prefix sums of array x × y in O(xy) in this problem x and y are the order of 100.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Aha. So do I take it that if the bounds on x_i, y_i where higher, this approach wouldn't work? The method I thought of was O(qlogn). Sort the points by x then y coordinates and binary search on them and use a 1D prefix sum to calculate their sum. Then you can easily get their updated brightness after t_i time. does this work?

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah because the overall complexity is O(cxy). I don't understand your solution yet, how do you exclude the points with bad y coordinates?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can sort the points by the x points, then by the y points. Calculate a prefix sum for this sorted array of points, then binary search on the points to get the right points to include and calculate their brightness as sum in prefix table + the number of elements*t_i and take it mode the number of elements * c. So each query should take O(log(n)) time for a total algorithm of O(qlogn) time.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Apparently a O(n + xc(y + q)) solution passes (here x = y = 100) with a sufficiently fast language. First, keep an array of all coordinate and brightness possibilities; put each star into its appropriate array. Now, compute the prefix sums of each row/brightness combination. Given this, we can answer each query in O(yc) time: iterate over all row/brightness combinations and find the number of stars in that row with the specified brightness that is also inside the query (can be done in O(1) because you have prefix sums). I'm sure you can fill in the rest of the details.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice pretests xD

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve D?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried hashing but it failed on test case 5 are there anti hash cases in pretest

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      mine gets tl and mle

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I clculated hashes of substring using only a linear array

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Mine failed pretest 5 too with hashing

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How can you hash when the string can contain not only letter characters?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        It does: The first line contains the string s (1 ≤ |s| ≤ 5000) consisting of lowercase English letters.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          OMG WHY COULDN'T SEE IT MAN =(. Btw what is your MOD number?

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it +6 Vote: I do not like it

            It's always good practice to double-hash, so the two primes were 31, 37 and mods were the usual (1e9)+7 and (1e9)+9.

            I think pretest 5 is not an anti-hash test, since with double hashing, the chances of ever getting a collision are so low, it's nearly impossible. So, we can conclude that our algorithms were wrong :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try using 2 hashes

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used hashing with unsigned long long int. I was getting WA on pretest 5, but the error was with the greater K I was testing

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to do so: DP[i][j][k]=DP[i][i+sz-1][k-1] && DP[j-sz+1][j][k-1] && leftside = rightside. When i figured out what my function for leftside==rightside is not right :( I think it is O(n^2log^2n)?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think what leftside==rightside(i, j, k) can be done with binary search :S Mine failed, i made it like it was (i, j, log_2(j-i)+1)

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Find values till logn. After that answer will be zero. Complexity n*n*logn

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      yes but i get tl

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I was also getting TLE. Forgot to memorize dp.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you find 1-palindromes? I see solving to logn in n^2, but how you find palindromes in n^2?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        d[i][j] = is substring [i, j] palindrome, d[i][j] = d[i + 1][j — 1] & (s[i] == s[j]).

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        Click
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        its easy for 1 palindromes lets say pal[i][j] = true if substring from i to j is palindrome now if j — i >=2 : if pal[i + 1][j — 1] = true and s[i] = s[j] pal[i][j] = true

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you check if leftside == rightside in O(1)?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    I did something like this: you first have is_pal[i][j] = the substring from i to j is a palindrome. (is_pal[i][j] = 1 if is_pal[i + 1][j -1] = 1 and string[i] = string[j]) Now, notice that a K-pal is also a K-1 pal. So we need the maximum "degree" of a substring: 0 if it isn't a pal, 1 is it is a 1-pal, k if it is a K-pal. We will have dp[i][j] = the degree of substr from i to j. When we reach [i][j], we have to analyse its 2 halves and if [i][j] is a pal. Now notice that if [i][j] is a k > 1 pal, then it is a pal and its halves are also pals (so they are equal). If that is the case: dp[i][j] = dp[one half] + 1. Now add them to your answer. (Hope this will pass EDIT: it did pass )

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    For simplicity, put a | between each character, as well as at the front and the back of the string. Now all palindromes will have odd length (possibly centered at a |). A radius of a palindrome is half its length, rounded down. (For example, the radius of abcdcba is 3.)

    First, find longest palindrome centered on each character. Naive O(n2) search is fine.

    Now, we will compute , being the largest level of the palindrome centered at m with radius r, minus one. , since a single character is a 1-palindrome. To compute , let r' = ⌊ r / 2⌋. If the longest palindrome centered at m has radius less than r, then . Otherwise, will be equal to , and you can set . Why it works is left for the reader, or I'll explain later.

    Now that you have your , we can prove that ai is equal to the number of that is greater than or equal to i. We can find all ai's in O(n2) time.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I used suffix arrays to be able to check in O(1) if a sequence is a palindrome. Then I just checked each sequence to see if it is a palindrome. If it is, I check whether half my sequence is a palindrome and so on. Total O(N*N*logN) it fit in 1.3 secs.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Basic insights. Every k-palindrome would be a palindrome, can be easily proved using induction. Every k-palindrome would also be a (k - 1)-palindrome.

    So, we only need to find max k for every palindromic substring of S, such that it is a k-palindrome.

    Here's what I did.

    1. Generate prefix and suffix hashes for S, let them be HP and HS.
    2. Iterate over all substrings. For substring S[i][j], check if HP[i][j] = HS[i][j], i.e. if prefix and suffix hashes are same only then the substring would be palindrome.
    3. If S[i][j] is palindrome, recursively do the following.
    4. If len(S[i][j]) = 1, return 1. (strings of length 1 are 1-palindrome)
    5. Else L and R be left-half and right-half of the strings, as defined in the question. Check if hash(L) = hash(R), i.e. check
    6. If hash(L) ≠ hash(R), return 1. (given string is just a palindrome)
    7. If hash(L) = hash(R) then do step 3 for L, and return ans(L) + 1

    Now, this solution wasn't passing under time-limit, so to optimize I used an unordered_map to store answer for all palindromic substring hashes that I've seen and if I see the same hash for any substring again, I just lookup answer for it in the map.

»
3 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

Very nice problems! Thanks, qoo2p5!

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Short announcement, short statements. Cool!

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it
Hmm.. Suspicious
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you have to mention mikemirzayanov for this one

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yup, looking at his submission, he just change a comment to intentionally get hacked. Though, we cant be sure if the hacker co-operated with him.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      IMO they should remove TheStupidOne, and take away the hacker's points gained from hacking.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

HELP! Somebody help me with B. I didnt passed the pretest. Though it passed all tests i made my as per my intution on my pc. i dunno what i missed.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    where is your solution ?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't read the whole submission but the number n can be huuuge, you can't store it in an integer type. A string will do though.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        the problem is with variable p , because the range of it could be 10^100000 !

        when you define it as int, you can assign numbers in range 10^9 to it

        long long is suitable till the number is not greater than 10^18

        if the number is bigger than 10^18 it's better to use string

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you sort the string????

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i think it could fit in an int still i used ll.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        ten to the power of 1e5 CAN NOT fit in a long long...

        It's 1e5 digits the maximum a long long can hold is about 18 digits I think

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        the maximum limit of an ll is 10^18, even ull is up to ~ 20^18, so n won't fit in any numeric type variables, you should've used string

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          oops! Just noticed. I didnt read the constraint very carefully and used ll :(

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Thx for the short statements!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to write a proper generator to cause TLE on B. I keep getting Generator crashed. I tried print(1e8) loop 1..1e8 : print('8')

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    String was only aloud to be 1e5 digits long

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does O(N2log(N)) pass for D ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    not for me

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It pass pretests, but I really doubt it pass the full system testing :(

    UPD: It passed

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I got MLE ! (time complexity as well as space complexity was O(n*n*logn))

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not for me too :( I was so positive about it, since, N^2log(N) was equating to 3 * 10^8 operations and tl was 3 secs.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well its actually not 3 * 1e8 there are so many things in you loops which will make it more than 1e9

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It did for me in 1.3 secs.

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

anyone has any idea about the third pretest for C ??

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    it should be having more than one star at some position

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hack tcs for div2 A,B? Thanks!

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve E ???

PS: E was a very awesome problem.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I have an idea asking for each of bit of the position but dont have enough time to code

  • »
    »
    3 weeks ago, # ^ |
    Rev. 4   Vote: I like it +29 Vote: I do not like it

    Let answer be A and B (A<B). For each bit position, find whether the bits at that position are same or different in A and B. For highest diff position, A has 0 and B has 1. For all other positions, find the bit at that position in A. Correspondingly, you get the bit for B.

    To check if the bits at position pos are same/different for A and B, put all numbers having 0 at position pos in a set and query the system. If the number of occurrences of Y is 1, then the bits at pos are different in A and B.

    To find the bit at position pos for A (after you've found the highest differing bit high), put all numbers with high=0 and pos=0 in a set and count the number of Ys in it. If the number of Ys is odd, then A has 0 at position pos and 1 otherwise. Now based on the relation found earlier (bits at position pos are same/diff for A and B), you know the bit for B too.

    To count the number of Ys in a set, use the following -
    If size of set is even, the no of Ys is 0/2 if XOR is 0 and 1 if XOR is X^Y.
    If size of set is odd, the no of Ys is 0/2 if XOR is X and 1 if XOR is Y.

    You can see my code for an implementation of the same.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was asking for each bit. Then answer for some bit must be y or x xor y and then I have numbers which have only one y. For first number I just make binary search on numbers with this bit.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    For simplicity, suppose there are 1024 icicles numbered from 0 to 1023, so you can interpret them as 10-bit bitstrings.

    First 10 questions: ask the icicles that has 0 on i-th position, for each i. If there are 0 or 2 of the special icicles, the XOR will be 0; otherwise, the XOR will be x^y. Also note that it's impossible for all questions to give XOR 0.

    Now you know the answers to the questions. Suppose the special icicles are numbered p, q, and their XOR is r. We claim that the i-th bit of r is 1 if the i-th question gave x^y, otherwise it's 0. It's actually not difficult to prove; you can try it, or I'll expand on it later.

    Now you know that there are 512 possibilities of pairs of the special icicles. Interestingly, each icicle is involved in exactly one of them. Pick one icicle from each pair arbitrarily, then binary search on them.

    EDIT: Since n is not necessarily 1024 (it's impossible to be that, in fact), you need to fudge with it a little. You're still asking the same question, but now the response is either 0 or x^y (if there are an even number of icicles), or either x or y (if there are an odd number of icicles).

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Let set Ai be the numbers from 1 to n that have their ith bit on. Also let F(H) function be the xorsum of set H's elements. If for some set X or then X contains only one special element. We'll calculate F(Ai) for every 0 ≤ i < 10 (this is 10 operation). Let j be the first set Aj that Aj contains a special thing. Let's do binary search in 9 steps to find it (we can do it because |Aj| < 512). So we have the index of one special thing, but remember the 10 steps we did earlier? Just invert those bits in this one to find the other special thing.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain problem D in detail!!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    First of all, observe that there can be no k-palindromes such that 2k > n / 2.

    Let's calculate dp[k][l][r] which denotes whether [l..r] is a k-palindrome (i prefer something like bitset < N > dp[K][N]).

    The basic case is k = 1. This can be obtained in O(n2) if we just launch from all possible middles of palindromes.

    For k > 1 and [l..r] we just have to check several things (assuming m is the median of this segment): whether s[l..m] = s[m + 1..r] and whether dp[k - 1][l][m] and dp[k - 1][m + 1][r] are (k - 1)-palindromes (depends of parity, but the main idea remains the same). Hence you get .

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      if [l..r] is K palindrome , then its also K - 1 palindrome , hence you can get complexity down to N2.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, nice observation. Didn't even think this way :)

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How? Even then, there are N^2 log(n) states. Then how can you bring down the complexity to N^2?

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Instead of using state DP(L, R, K) denoting whether str[L..R] is a K-palindrome, use the state DP(L, R) which stores the max K such that str[L...R] is a K-palindrome.

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can you please explain a little bit more about it. How can we find whether a number is k palindrome or the max K such that the particular substring is palindrome without checking whether it's a k-1 palindrome or not?

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I used 2 DPs. A string is K-palindrome if it is itself a palindrome and its first half is (K-1)-palindrome. Non-palindromic strings are 0-palindromes.

              is_palin(L, R) returns true if str[L,R] is palindrome.

              DP(L, R) returns largest K such that str[L,R] is K-palindrome. To find K, I first check if str[L,R] is palindrome itself or not and then use the relation DP(L,R) = DP(L,MID) + 1, where MID is the end of the first half of the string.

              See my code.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thanks a lot for this awesome explaination.-:)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I wonder why my n log n solution got TL.. I'll be very lucky if you helped me. :) 29077577

      Is it all about bitset?

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      How can you know s[l..m]=s[m+1..r] without hashing? and also can you explain a good hashing function?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Calculate lcs[i][j] — the length of largest common substring of indexes i and j.

        It can be easily seen than lcs[i][j] is lcs[i + 1][j + 1] if s[i] = s[j] and 0 otherwise. So you compute this in O(n2).

        How can I know now? I have to check whether s[l][m + 1] is greater or equal than m - l + 1.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution for D is pretty straightforward I think, let me know if something is not easily understandable from my code.

    http://codeforces.com/contest/835/submission/29067296

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's really scared that In problem D I came out with a very complex idea( to me :) ),which make me code for more than an hour T^T,Hope it pass...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting for round #428 ...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm curious did anybody manage to get AC on D with O(n^2logn)? My O(n^2logn) solution was about as optimized as it could be (super low constant) but got TLE.

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

This was a really nice and smooth contest, good problems, short statements and good pretests. Thanks to everyone involved for making this such a great contest.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I literally spent the whole contest trying to solve C but I kept getting WA on pretest 3
Here's one of my submissions 29072095

I'd be glad if someone tells me what I'm doing wrong, it really drove me nuts throughout the entire contest.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    try this case:

    2 1 2 1 1 1 1 1 2 0 1 1 1 1

    answer should be 3

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was doing such a stupid mistake by iterating over the input multiple times in case of coincided coordinates, handled it, and ur test passes now, still WA on test 3 though.

      New submission 29076795

      Appreciate ur help.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Most people messed up because they didn't realize two stars could be at the same point. I didn't look at the code but perhaps that helps?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem — C?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hint: use partial sum

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    i have the same problem as your submitted code, but i solve it, the second operand of % should be on c+1 not c !

    because the original problem tells us s<=c and if s>c the variable s have to be equal to zero, so the range of numbers that s can have is 0,1,2,...,c

    After that you will face with TLE :D

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any discussions on the last problem? How do people write such long codes in such short time.

I cannot even write codes for C without bugs.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what have you done for problem C ? your submission is like DP

    could you please describe your idea for me ?

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

test cases for problem C were very weak.even O(q*n*n)(n=100) solution got AC. see this solution i think it should be rejudged with proper test cases.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    I think there is maxtest in system tests, and I think judge can do 10^9 simple operations in 2 seconds.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yeah its not fair!, The problem should be rejudged with proper test cases.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Yes, it's my fault, but the test cases are not weak. Codeforces invokers are quite fast, so 10 ^ 9 simple operations passes in 1.5 seconds.

    I tried to make the contraints not too strict, but it happened that they were too small.

    But, as I can see, the problem hasn't affected many participants, so everything is alright.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

By the way, I would like to thank qoo2p5 for the absence of anti-hash tests for problem D :) This really makes me happy (although I should have calculated lcs in O(n2) time :D).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It was a thrilling match. In the last three minutes, I came up with a solution, but I didn't have time to write. I am tooooo weak

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Because of one symbol, I got WA. I erased this symbol after contest and got AC. I'm so sad...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to hack in contest

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lock your problem and click in other submission in your room

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      then it shows the solution of the roome then

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        double click on someones solution, after that you will see his/her code.

        click on hack it and write a test case that proves the solution is wrong

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Could someone help with this one ? O.o Problem B submission I can't figure out why it should get WA on 24 :/

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what are moar and req?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    nevermind, I am a dumbass ._. found the silly mistake in line 179

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When, calculating req you want to take ceil((k - sum) / (9 - i)).

    int req = (moar + (9 - i))/(9 - i); should be

    int req = (moar + (9 - i - 1))/(9 - i); as in case (k - sum) % (9 - i) == 0, your req would be off by 1.

»
3 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

How to solve F?

»
3 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

Scrolling to find a comment about rating change? If yes, like this comment :P

»
3 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

regmsif is a cheater for sure. Templates of his submissions are completely different. KAN

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    And he solved B and F almost at the same time.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -24 Vote: I do not like it

      he is not cheater: http://blog.csdn.net/lych_cys/article/details/51326079 F was from before :)

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it -30 Vote: I do not like it

        instead searching for other, go and read editorial and learn a new thing :(

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 3   Vote: I like it +13 Vote: I do not like it

        Templates of his solutions of other tasks are still different.

        Timestamps of your submissions also seem suspicious to me, by the way.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it -31 Vote: I do not like it

          Why couldn't i write codes in different styles? i used to use one of the styles, and recently i'm trying to change to another one (you'll find it if you check my submissions before). These styles are both good and bad, one of them seems more beautiful, while another one seems shorter, and can be typed quicker. i don't mean to cheat.

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Generally, when completing in a contest, people have a template and copy that base template for all codes.

            So, when people see codes with two different styles, it appears that there might be two different programmers competing under one account.

            I would suggest in the future, when competing in a contest, use a consistent style throughout the contest to avoid this type of situation.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          you are crazy :)

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I won't say he is a cheater for sure, but it doesn't explain the difference in tab width, and the small difference in submission time. and also there's quite some small difference in style like the use of class and line spacing etc..

»
3 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

does backtrack approach works for problem C ?

any ideas ?

»
3 weeks ago, # |
Rev. 4   Vote: I like it -24 Vote: I do not like it

Is the educational round unrated? Or somebody just forgot to update the ratings.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    yeah, all educational rounds are unrated.

»
3 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

In problem C, Is it possible that two stars are at same position?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Yes it is, knowing that there can be up to 10^5 stars and there are at most 100^2=10^4 pionts on the plane it's pretty clear that there will be some overlaping stars.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      So for example if there are 2 stars at same place ( brightness 2 and 3, c=4). after 1 moment it's brightness will be 3 and 4(total = 7) ???

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yes, you are correct. Overlapping 2 stars would affect neither one of them.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Is it rated? Looks like not...

Or somebody just forgot to update the ratings.

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone explain why is't publish the final result of contest?!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why aren't the ratings updated? 3 hours already since the contest ended.

»
3 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

KAN qoo2p5 Please check Ali.P and Ali.PI submissions, seems same thing to me, possible cheat. Ali.PI Submission , Ali.P Submission

»
3 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

Nowadays much submissions are being done in a contest compared to the previous ones.
Really astonished by this !!!

»
3 weeks ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Ratings rolled back? weird. Edit: They are back with new ratings. Apparently mine increased. wtf?

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What's wrong with the rating changes in this contest? My new rating disappeared and so does many others (I checked)!!!

UPD: NOW BACK TO NORMAL.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How this one passed C — 29077578 :| Just looping from (x1, y1) to (x2, y2). Shouldn't that give TLE? As it is O(1e5 * 100 * 100) ~ O(1e9) in worst case!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My rating disappears and my submission is marked "skipped". What's wrong

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Your's C: 29067352
    jt3698's C: 29073459
    Your D: 29073399
    delete4's D: 29073330

    Only variable names differ! Notorious Coincidence or what?
    CF usually forgives cheating for first time and second time bans both account :)

    I think you also cheated in A & B. And used ~4 accounts, and one of those accounts also got outside of contest [I wonder why other's solution didn't get skipped -_- ].

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Both of the submission you put are significantly later than mine. And you can check the codes are in agreement with my coding style.

      If you I am considered cheating because I leaked my solution on ideone. Fine. But why is jt3698 and delete4 still in the competition?

      And please clarify the reason you think I "also cheated in A&B"

      After a closer inspection, I think jt3698's code is very different from mine. You should think more carefully before accusing other people.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for sending me the links, though.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Actually the problem F is quite similar to one problem in NOI(China)2013 . So if I have solved that problem before and I copied the code so I finished the problem very fast(only in less tha 5 min, for example ) , is that cheating?(Actually this time I wrote the code again)

Sorry for my poor English.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And I'm curious about how the anticheater system works.

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

The same solution for problem C using C++ got accepted link

but got TLE using C# during the contest Link

And I see many solutions like this.

very nice...

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    LOL. Another solution passed using C++ Link

    but the same solution got TLE using C# Link

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I tried to solve E using binary search, where first i'm finding index such that xor of indices 1 to index contains exactly one y. Then using binary search between [1,index] and [index+1, n] i'm finding indices of y. But due to redundant queries i'm not getting right answer for n > 500. Can someone optimize it or tell why is it not possible to solve using binary search. Here's my code http://codeforces.com/contest/835/submission/29088791. Thanks in advance

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It is not possible to find using binary search the first Y in a sequence which has 2 Ys, because the prefix XOR function is not monotonous.
    eg. Let the sequence be str[] = XXXYXXXYXXX (1-indexed)
    The prefix XOR of str[1..2] is 0, of str[1..4] is X^Y and that of str[1..8] is also 0.

    What do you do when you encounter a prefix XOR having value 0? Do you go left or right? In case of str[1..2], you need to go right. But in case of str[1..8], you need to go left. The prefix XOR values are NOT monotonous.

    The algorithm you mentioned will work if the sequence has only 1 Y.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let's say mid = (1+n)/2, now if 1 to mid values don't contain only one y i.e(value is not y or x^y) then we take mid1 = (1+mid)/2 and mid2 = (mid+n)/2, now we keep doing mid1 = (1+mid1)/2 and mid2 = (mid2+n)/2 until one of these mid values don't contain exactly one y. Then we assign values as i mentioned before i.e start1 = 1, end1 = mid(or mid1 or mid2), start2 = end1+1, end2 = n and proceed as before. If something's wrong here, please correct me.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know why DIV.2 problem C is NA... 29145513

BUT!!! This code is accept.. 29145520

It's just different this code

for (int t = 0;t <= 10;t++) { sum_val_map[t][y][x] = ((c + t) % (C + 1)); (NOT ACCEPTH)

for (int t = 0;t <= 10;t++) sum_val_map[t][y][x] += ((c + t) % (C + 1)); (ACCEPT)

Somebody explain it to me plz!!

Do duplicates come in as inputs?