gridnevvvit's blog

Codeforces Round #275
By gridnevvvit, 10 years ago, translation, In English

Soon (on October 24, 21:00 MSK) you are lucky to participate in Codeforces Round #275 for both divisions. Pay attention to the round begining time!

Problems have been prepared by team Saratov SU #3 with members: Gridnev Vitaly (gridnevvvit), Danil Sagunov (danilka.pro), Roman Kireev (RoKi).

We want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

Scoring system:

Div1: 500 1500 1500 2000 2500

Dvi2: 500 1000 1500 2500 2500

UPD:

Contest finished, congratulations for winners!

Div1:

  1. tourist
  2. Petr
  3. subscriber
  4. uwi
  5. PavelKunyavskiy
  6. mmaxio
  7. Ra16bit

Div2:

  1. dickXD
  2. meodorewan
  3. charlie
  • Vote: I like it
  • +191
  • Vote: I do not like it

Comments Comments (164)
| Write comment?
»
10 years ago, # |
← Rev. 3   Vote: I like it -113 Vote: I do not like it

how to solve the div2 D,please help me

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

I am really sorry to say but some of your previous contests english translation was quite really bad to understand . If possible please provide explanation of test cases . Hope this time everything will be fine and everyone will enjoy it :)

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

first round after my 1700+, gl & hf!

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

    And I hope that my first Div. 1 round will be on the next contest...

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

    Same here ;-)

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

Sherlock comix in prevous edit.

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

    This is probably some hella smart & funny joke, but I just didn't get it.

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

      I'm not sure, but active CF users who watched "Sherlock" should understand the concept (at least).

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

        Waiting for Sherlock's new season...

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

          make sure that better than waiting game of thrones cause everytime who reads books, s\he gives spoiler

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

            Still better than watching Persona 4 before completing it, it completely messed up my wish to grind the exp to just know that Teddie is a actually a person :O.

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

    Konstantin.Zakharov awesome :D one of the creative comment post i have ever seen here :D

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

    I just hope that the round won't be "boring" :))

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

Whoa the round is at midnight in my country. Overslept is not an excuse.

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

I want to participate in the contest very much!However,it's at 1 a.m in China,we must stay up!

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

thank you!your problem is hard or easy?your contest has very good problem .!

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

Please short explanation for problems.

Also explanation of sample tests.

" THANKS FOR READING

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

wow I'm so happy there are so many new contests on CF these days. Hopefully this pace won't go down in the future!

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

If the time is corrected, Some of Chinese Coders may start coding from 1:00 a.m. to 3:00 a.m. and waiting the system test until 3:30 a.m. Then sleep for a while and participate the regional warm-up contest. The next day(Sunday) participate the regional onsite contest for 5 hours. What a Fighting weekend.

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

    Definitely no Chinese coders will compete in this round if they are going to participate in ICPC regional just on next day. They just need good rest.

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

      Good night~ wake up at 00:30 a.m.

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

      Alas, I (Chinese coder) really want to compete in this round, though I will not participate in ICPC regional, just the point is that our dormitory's blackout and my laptop can't afford to complete this competition …… ╮(╯▽╰)╭

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

If only the round beginning time would be advanced to regular 19:30 MSK suitable for most participants.

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

Where do i go to register for the contest. not allowing me to do so

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

Any particular reason for the unusual timing of the round ?

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

Timing is perfect for me again, thanks ;-) 19:00 CEST, typically it's 17:30 which is too early to be finished at work...

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

@gridnevvvit Your last round was a DIV2 round and the round you arranged before it was a DIV1 round . so , it's good to see you coming back with a DIV1 round once again :)

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

Smiling:)

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

Omg the starting time of the contest is coincides with my sleeping time :))

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

    Unfortunately, sleep was delayed because it coincides with codeforces round 275. here is the new time

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

There has been a lot of math in recent contests! Hope for something algorithmic! :D

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

First Div. 1 :) Gl & Hf everyone

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

    and your first Div1 has no 1000pt problem :D

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

I dont understand why this congruency works sometimes :

Scoring system will be announced later == Registrations are closed 5 minutes before the round. Why delay it so long as in few minutes before the contest? Why delay it anyways?? Any specific reasons that I dont know of?

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

How to Solve division 2 Problem-:B ?

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

    i think with binary search

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

    i solved it recursively. consider lower bound of allowed numbers to be L. the absolute minimum numbers you need to consider is cnt1+cnt2. so you look at numbers from the range [L,cnt1+cnt2+L-1]. the numbers divisible by both x&y cant be gifted. from the remaining numbers those divisible by x were gifted to second frnd and those divisible by y were gifted to first friend. now the numbers left can be gifted to either friend.After some thinking you can argue that they should be gifted to first friend and if some are left even after that then to the second. the arguement for this is based on the fact that x < y.i am sure you can think of it :). after updating cnt1 and cnt2. apply the process recursively with new lower bound as cnt1+cnt2+L (i.e. upperbound of previous process +1).

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

      I tried a solution like that but it wasn't working for me. I ended up using the fact that for any choice of v, there will be v/x multiples of x, v/y multiples of y and v/(x*y) multiples of both x and y (since x and y are unique primes).

      You can figure out how many free choices you have left and increment v accordingly.

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

        my solution wasn't accepted, either the logic is faulty or my implementation.

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

How to solve C DIV1 problem ? . Thanks in advance.

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

How to solve Div-1 A ?

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

    The first (n — k) numbers could be 1,2,3 ... (n — k) after which we print n, n — k + 1, n — 1,n — k + 2 .... for the rest of the numbers.

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

    First, follow a pattern 1, n, 2, n-1, 3, n-2, ...; do it k-1 times. Than add remaining numbers in the natural order (decreasing or increasing depending on k's parity).

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

    I printed 1 and then printed p=1+k, then decreased k by 1 and then printed p=p-k and continued the series. Like, if k=3 and and n is anything arbitrary for an instance, I printed 1 4 2 3. Notice the difference in each adjacent values. And in the end I printed all the remaining values less than n.

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

    That one's pretty easy. The task asks you to find some array of length n so that the amount of absolute value of differences of each two consecutive elements is equal to k.

    I did it that way:

    Our answer:
1 n 2 n-1 ... n/2

    And if we are about to print the (k+1)-th number we just print our latest number (- OR +) 1 which will make it look that way:

    For example: N = 9, K = 3
1 9 2 3 4 5 6 7 8
And N = 9 K = 4
1 9 2 8 7 6 5 4 3

    As you have probably noticed if K mod 2 is equal to 0 then we print our latest number - 1. Else: latest number + 1.

    Pretty easy solution and easy to write down, work time: O(n)

    edit: whoops, i think i'm late for a party

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

    Not accepted yet, but I think it will be so... :) With first k elements You just can generate something like this: 1 1+k 2 2+(k-2) 3. Every needed difference will be here, k = |1+k — 1|, k-1 = |2 — 1+k|, k-2 = |2+(k-2) — 2|, k-3 = |3 — 2+(k-2)| ... And now, after that, just write the rest, n — k elements, one by one: 1+k+1 1+k+2 1+k+3 ... n-1 n. Difference between 1+k+1 and previous element is for sure not greater than k since k>=1 and previous element has to be between 2 and 1+k. Sorry for my English :)

    EDIT: Aldiyar explained similar solution much better in his post, but it wasn't there when I was writing mine, sorry for doubling answer :)

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

So guys what do you think about the difficulty level of div2 probs?

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

    A-As Usual Difficulty. B-Very Much tricky. Perfect Problem who loves math. C seems easier to most of the div2 contestants but I got lots of pain and still not sure if it will pass. D was an awesome problem. No Idea how to solve it. E- I saw factional output — pressed ctlr+F , looked for a word "expected", found it and immateriality closed the tab.

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

How to solve problem B of div2 ?

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

    Binary search

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

      can you please explain the some more, i used a different approach and would like to know how to do it with binary search :).

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

        All you need to do is to see if a particular N (1..N) can be split into the 2 sets. Let S1 and S2 be the sets for friend 1 (with prime x) and friend 2 (with prime y) respectively We can observe that in a set we can put the multiples of other prime.

        S1 = {all multiples of y — multiples of x*y} S2 = {all multiples of x — multiples of x*y} The elements that can go in either sets are: Remain = N — multiples of x — multiples of y + multiples of x*y

        So just check if using Remain you can satisfy the deficiency in S1 and S2.

        http://mirror.codeforces.com/contest/483/submission/8395374

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

      Bad, it is mathematics.

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

How was Div2 B supposed to be solved?

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

    I solved it using segment trees (sadly after the contest).

    Initially set all the values to 0 and the if a query(L,R,V) comes, update all the values in the range(L,R) with (a[i] = a[i] | V where L <= i <= R).
    while joining nodes in the segment tree do seg[node] = seg[2*node] & seg[2*node+1] and finally check for each query_range whether the bitwise and (&) of all the values equals to the required value i.e check value(L,R) = V . This got AC .

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

      He was asking about Div2 B, not Div1 B :D

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

        sorry, seems i commit mistakes even after the contest.

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

          I wanted to know how to solve Div1 B as well :P So, thanks :)

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

    Some people used binary search, I did not. My approach is as follows:

    1.Set the answer=cn1+cnt2 initially.

    2.Then you can fulfil the requirements of the first friend by giving the numbers to him which are not acceptable by the second friend and vice versa.

    3.Let the friend with more requirement of numbers be friend1(cnt1>cnt2).Then you can give the numbers in the range [1,answer] not already given to any of them to friend 1. Then if his requirement is done you can give the remaining numbers to friend 2.

    1. If you see that both friend's requirement is done then you can print the answer else you can increment answer by sum of remaining requirements of both friends and repeat from step 2.

    Code http://mirror.codeforces.com/contest/483/submission/8394005

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

    i solved taking a long long a = cnt1+cnt2, & then checking if a — (a)/(x*y)>= cnt1+cnt2; if false, then a+=(cnt1+cnt2-(a-(a)/(x*y))), and so on. becouse the numbers that are multiples of x*y cant be taken as answer in any of the two cases. You have to check in the same way if there are enough numbers int the interval that aren't divisible by x, and the same whith y.

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

      Is that working for 3 1 2 3 input?

      a = 3 + 1 = 4
a - a/6 >= 1 + 3
return 4

      but the result is 5 — it was first input from problem statement...

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

I think 1 sec for B and C is too strict.

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

    Totally agree, especially if you submit in Scala :(

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

    In C, it's necessary to kill off O(nm2m) solutions.

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

      But unfortunately some of them have passed:(

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

      it is not necessary, it can be made greedy

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

    Yes, I got TLE just because of using scanner in Java instead of buffered reader. 2 seconds would have been better

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

so the author thinks that div1 B as hard as div1 C ?

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

    I agree.Let's hope that no source with correct idea will get TLE.It wouldn't be nice...

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

      Yeah.The hope is not enough...I took TLE with my 2^m*n complexity which works much better in practice.If this was the official complexity, than that limit is too small.In the other case, the pretests are not good(nobody took TLE on pretests)

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

        There are sources which pass the tests and have 2^m*n like mine, so, anyway, the time limit should be bigger for letting the sources which are not optimized at maximum to get AC to...the problems were very nice anyway.

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

Accepts for C is more than B in DIV2 :D

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

I dislaked A — div1 very much. f*ck math.

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

Too fast SysTest . Hope Rating update will also be this fast :D

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

I could not optimize C in time. Unfortunately it works 1.2 secs at worst case :(

UPD: Thank god, codeforces faster then my pc. :D

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

Not sure if I'm stupid or just bad at constant optimization — is a 50*20*2^20 solution supposed to pass for div 1 C?

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

    My 50*2^20 got TLE, so I'm guessing no.

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

    If so then 1s TL is not enough for such tight constraints.

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

Bye Bye div1 :(

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

In what world are B and C the same difficulty? :D

I'm curious what the hell did the author think

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

    Maybe it was meant to work in 50*20*2^20 =(

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

      We did not notice, that idea of solution with working time O(len·2len) (len = length of strings) is too hard.

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

      Well then 1s is a horrible time limit. And even so, I think the problem is still harder.

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

    You maybe mean "C and D".

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

      No, I meant that the author gave 1500 for both B and C while the results show their complexity to be slightly different

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

        In general, it's hard to evaluate problem difficulty once you know the solution (especially if you wrote it and tried a few variants).

        Hmm, but there are three authors... Typically, getting a couple of others to test a problem gives you a good idea about the difficulty...

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

          True that it is hard, but except the three authors there is usually a tester/helper (I guess Zlobober in this case) who should detect such miscalculations.

          I'm really curious of the solution, maybe it does look simple once you know it.

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

            Actually I found a way to improve my 50*20*2^20 solution to 20*2^20 fairly easily, but the explanation would be pretty long. The solution is that if X is a set of questions, then DP[X] is the average of DP[X|(1<<i)] for all i that aren't in X, plus the number of strings that can't be distinguished by that set of questions.

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

      No, B and C. They were worth the same number of points, and the actual gap in difference is dramatical.

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

    Not only that .This is the condition in DIV2 ->

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

      Yep, serious mistakes in complexity predictions. I guess it would've been really good to use dynamic scoring if the authors weren't too sure .

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

Good bye Yellow!

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

Wow, a lot of systest fails and hacks in C. I'm wondering if most of the failed submissions mixed up string length and n somewhere.

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

    WA22 is the case n = 1. My solution printed 1 while the answer is clearly 0. I saw lots of solutions which failed this test.

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

      Ok, this seems like a problem with a high probability for cheap mistakes. Not that I'm complaining. It is the only reason why I got such an unprecedentedly good (for me) result.

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

This contest was some difficult then other contests! Are someone explain solution of div 2 B problem??? please explain! (sorry for bad english !)

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

    Binary search the answer..... to check whether we can distribute the presents between the friends using a certain v, we can use inclusion-exclusion. this might help : there are exactly n/p numbers between 1 to n which are divisible by p.

    hope it helps.

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

8387870 Why my submission is skipped ?

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

What was the expected time complexity for problem C?

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

    I had O(N * 2 ^ string length)

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

    O(L*2^L) as mentioned in a comment above. Turns out the idea behind such solution is way harder than authors thought. I think O(N * 2^L) also passes, but most of the solutions were something like O(N*L*2^L) and failed.

    L — string length

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

I had tried to use unsigned long long and cin>> in D2B problem, but on my system it was wrong, signed long long works properly. Anybody knows why it may be?

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

Testcases in div1 C seem to use CRLF line feeds (not LF). I think it is unusual in Codeforces.

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

Can any one please explain how to solve Div-1 B ?

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

    interesting for me too, after ends I wrote O(2*m*n), so TL.

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

    I used segment tree to find possible answer and another segment tree to check that answer is correct.

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

    Segment tree with updates on segments. 8393603

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

    For each constraint ... We iterate over the bits of q ... if the ith bit is turned on ... then it means that all elements in the range (l,r) have this bit turned on as well ... else if the ith bit is turned off ... then it means that at least one element in the range(l,r) has this bit turned off.

    So for all the turned on bits ... We turn on this bit on all the elements in range(l,r)

    After that for the turned off bits ... We check that the range(l,r) contains at least one position where this bit is turned off.

    We can use either segment tree or cumulative sum and binary search to implement this idea.

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

Can anyone please tell me why WA at test case 24 for problem c div 2 . code i handle the condition k == 1 then print ( i + 1) . whats going wrong here .

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

Rating has been updated.. time to press F5!

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

    anyone who saw your comment must be already refreshed his/her browser.

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

So night before yesterday I got 4 hours sleep, I did 6 hours of exams yesterday and got < 4 hours sleep before this contest.

I went from 12th in last contest to 517th in this one.

Damn.

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

Spent whole contest trying to code D, and only now realized the solution is deceptively simple: note that the number of ways to color a subtree is the product of the number of ways to color each of its children, plus the same product for the reverse order. Or it would be, if it weren't for double-counting.

Turns out that the combinations that will be double-counted are the ones in which every painted subtree has an even number of painted vertices, or every painted subtree has an odd number of painted vertices and the number of painted children is odd.

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

Great Contest!! Finally above 1700

Btw, can anyone help me out with this http://mirror.codeforces.com/contest/483/submission/8393197

Problem D,div2

I tested it one ideone as well but it is giving runtime error there too.

I basically used bitwise range tree to solve the problem.Please help

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

Looking at number of TL's on C i realize how small is amount of coders who check their solutions in custom invocation before submit:)

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

Can anyone help me with my code for Div1-B?

My code: http://mirror.codeforces.com/contest/482/submission/8386444

I saw some solutions very similar to mine, but I am not finding any bug or seeing why my approach does not work.

Thanks.

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

First 4 minutes of contest: how I do programming and solving problems, screencast. [EDIT: now not private]

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

In Div 2 B, I didn't do binary search but derived a direct O(1) formula based answer and it passed. Here is my code : code. Is my solution correct or were the testcases weak??

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

can someone tell me how to solve div2 D????

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

where is the editorial of the round ?

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

When editorial going to be published? In addition, very surprised to see that Division 2 B problem was much harder than C problem (by statistic)

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

Problem --> Interesting Array (CF Round 275): Div.1/B or Div.2/D

Tourist's code : http://ideone.com/c5dTmY

In this problem, for every set bit in query, we set the corresponding bit for all the numbers in the given range. I can't understand how he's doing that by:

s[from[k]][j]++; s[to[k] + 1][j]--;

Also, for calculating the number of set bits for a given bit position, for a given range of numbers, he's made some sort of cumulative array. Please explain its construction:

bal += s[i][j]; a[i][j] = (bal > 0); sum[i + 1][j] = sum[i][j] + a[i][j];

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

    I will try to explain by posing a different problem:

    Given m queries of the form a, b, p; Add p to each element between arr[a] to arr[b]; Length of the array is n.

    Trivial solution will do it in O(m * n);

    To optimize, what you can do is, add p to arr[b]. And add -p to arr[a-1];

    Those two units of information is enough to let you know that you want to add p from arr[a] to arr[b].

    Keep on doing that for all m such queries.

    Finally, do, something like:

    arr[n-1] += arr[n];
arr[n-2] += arr[n-1];
arr[n-3] += arr[n-2];
...
...
arr[2] += arr[3];
arr[1] += arr[2];
arr[0] += arr[1];

    So, just one final loop like above can add p to all elements between arr[a] to arr[b] for all such m queries.

    Complexity is: O(m + n)

    Try it on paper.

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

      Thank you so much for you explanation!

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

What's wrong with the editorial ? i can't see it now, but some days ago i can reading it.

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

    translating maybe. the last time I saw the solution of two last problems were written in Russian

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

Why is the tutorial not accessible now? It was accessible a few days back..!!

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

Only solved A，but rating +13.

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

Why am I getting TLE in problem B(div 1)? My complexity is 32*nlogn*3 which is approximately 6*10^7, that I think should pass in 1 sec. My code is here

→ Reply