Блог пользователя zloyplace35

Автор zloyplace35, 8 лет назад, По-русски

Всем привет!

20 августа в 16:05 MSK состоится рейтинговый раунд Codeforces #368 для участников из второго дивизиона.

Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Я постарался сделать задачки, в которых нужно больше думать, чем кодить. Надеюсь, каждый найдет себе задачку по вкусу.

Спасибо координаторам danilka.pro и GlebsHP за помощь в подготовке контеста, vovuh за прорешивание, Roms за вычитывание условий, а также MikeMirzayanov за платформы Codeforces и Polygon.

Удачи!

UPD1: 500-1000-1500-2000-2500

UPD2: Поздравляем победителей!

Div. 2:

  1. Philipsweng
  2. ACCE12138
  3. lastans
  4. fastcoder
  5. bblss135
  6. YxuanwKeith
  7. chenjiamin

Div. 1:

  1. ksun48
  2. MrDindows
  3. dreamoon_love_AA
  4. uwi
  5. wangyisong1996
  6. matthew99
  7. irkstepanov

UPD3: Разбор

  • Проголосовать: нравится
  • +315
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -45 Проголосовать: не нравится

It seems interesting:)

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

There's a slight typo in the post. It should be round 368 instead of 365.

»
8 лет назад, # |
  Проголосовать: нравится +115 Проголосовать: не нравится

It's your first round, first rounds are always amazing. As a Div. 2 contestant, I want to thank you for preparing the contest for us.

And since it's a Div. 2 contest and there will be a lot of competitors from both divisions, I want to kindly ask the Codeforces team to make sure we will have an acceptable queue and a responsive Codeforces. Thank you.

»
8 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

And the points will be 500-1000-1500-2000-2500 as usual. I guess B-)

»
8 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

It will be tough and tricky I guess. Long break and again regular round, Thanks codeforces. Wish you all have a great jump..:)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think it was because of IOI, codeforces doesn't want IOIers to miss the rounds.

»
8 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

vovuh for testing....I think problems will be on Pokemon Go! and we'll have to try to catch Pinsir, seems bit interesting.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -29 Проголосовать: не нравится

If you are doing your best,you will not have to worry about failure.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

Make sure that server will not lag today.I got the result of my submission after 15 minutes in previous contest.This is happening since last 3 contests.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah, and I am going to lose my shit if this ended up as one of them as this is the first early contest in months...

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    6500+ registrants already, I'm getting feeling of long queue again !!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Могу поспорить, что задача C будет по геометрии)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Давай на 100 рублей =)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Кто-то мог остаться без соточки :)

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Будь мужиком, кидай деньги сюда: 4377 7314 2790 2959.

        Контест, конечно, завалил, но хотя бы денег заработаю...

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Ты в танке?? Задача C была по геометрии.

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

_**PERFECT TIMINGS FOR ROUND #368 :D **_

»
8 лет назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

Where on earth is the world full of the flowers If it really existed, I must go I would love to climb the highest mountain no matter what the cliffs are

To live better and love deeply no matter what it takes I do right by myself rather than to seek other's satisfaction I never choose to give up my dream even in my darkest days

Maybe I am not the talent but I have the pure dream I will spent my whole life proving it Maybe I am not the hand of the diligent but I would keep exploring to stake my youth without any regrets

To run forward against the cold shoulders and the jeering crowds if we didn't go through all kinds of hardships and difficulties, how can we feel this wonderful life The destiny can't let us down on my knees even we have paid in blood embrace

To keep running with the pride of childlike simplicity if we didn't persist to the end, how can we see the glory of the life Better to light up a life than accept a life we don't want One day it will be reborn

The charming future always says hello to me even suffering is my only companion, I will keep moving I wanna sail on the bluest ocean no matter whether I will come back or not

I am lonely when I will fail that's the sign of the coward As long as I am alive, please clench our fists before the daybreak we are even more brave to wait for the most dazzling moments during the sunrise

To run forward against the cold shoulders and the jeering crowds if we didn't go through all kinds of hardships and difficulties, how can we feel this wonderful life The destiny can't let us down on my knees even we have paid in blood embrace

To keep running with the pride of the people if we didn't persist to the end, how can we see the glory of the life Better to light up a life than accept a life we don't want Don't compromise until we get older for the goodness of our hearts.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -131 Проголосовать: не нравится
if(contestIsBy("amd"))
    scoring = "500 , 1500 , 2000 , 2500 , 3000"
    solved = "2000 , 800 , 20 , 1 , — "
else
    scoring = solved = usual
  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +98 Проголосовать: не нравится

    I'm sorry but let me tell you what it looks like to me.

    amd makes contests for everyone. But a contest has hard problems so you decide to shit over his work. And it's not even in the thread for that contest, but you feel the need to do this in a totally unrelated thread (probably just to get some cheap contribution?)

    Am I wrong? Because to me it just seems entitled, disrespecful and inconsiderate, especially after this.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -52 Проголосовать: не нравится

      come on! I was just taking a break with commenting under this post! contribution ?!?! let it be -1000 or +1000 ... who cares ?! and about amd ... I just joked ... I know amd's contest aren't bad or useless ... the are pro

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You assign scoring and solved to strings which is not very useful, but let's skip it for now.

    The most confusing part in your code is that you assign usual variable both to scoring and solved, but they have entirely opposite meanings: this way the hardest problem would be solved by the most people and visa versa.

    The proper way would be:

    scoring = usual_scoring;
    solved = usual_solved;
    
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Must be an interesting contest, 7000+ participants.

Good luck for ya all.

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Where is scoring distribution?

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

7k+ participants. I hope the queue wait time for a submission is low.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

coders are increase day by day.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I really like round. Thanks for nice contest :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me how to do C in a time shorter than O(n^2). That was the best I could come up with.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    If n <=2 ans = -1

    if n is odd ans will be (n*n-1)/2 and (n*n+1)/2 if n is even ans will be (n/2*n/2-1) and (n/2*n/2+1)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -14 Проголосовать: не нравится

      Interesting. Thanks for the help!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I didn't realize odd can be handled so easily!! I factorized and all that.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      how do coders come up with formulas like these? do they need to have a previous deep knowledge in mathematics/geometry or do they just notice the relation between the 3 sides using examples of right triangles ? or is it something else ?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    You can use (n+1)^2-n^2 = 2n+1.

    N is odd -> use that formula with N*N.(N*N is also odd) N is divided by 4 -> use 3,4,5 Else -> divide N by 2 and use the formula

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      There are some interesting methods for this problem. Thanks for the help!

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    a = n^2 — m^2, b = 2*n*m, c = n^2 + m^2

    m < n

    Assume that the side is one of a,b,c

    and validate it.

    for Example iterate until 1e5 to check the m and check if the given side is divisible by 2 * n and that L / (2 * n) < n

    For validating the other two values, you can use binary search to find the sqrt of

    n^2 — c, and b — n^2 Also you'll iterate only till 1e5 because the maximum length is 10^9 so you can iterate till the sqrt of 10^9 So the total complexity is O(sqrt(N) * Log(N))

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks! I should've realized the max I could go was the square root of 10^9. This makes a lot of sense, thanks again.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I used binary search and used the traditional 3SUM interview question to solve it in nlogn

    where n is the number of perfect squares less than 10^9

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    every pythagorean triplet can be expressed in the form of
    a^2 + b^2 = c^2 where
    a = m^2 — n^2
    b = 2mn
    c = m^2 + n^2
    Refer this
    if x is even, it can be substituted in b = x = 2mn
    thus x/2*1 = mn
    m = x/2, n=1
    deriving a and c from this as : a = (x/2)^2 — 1, c = (x/2)^2 + 1
    if x is odd, it can be substituted in a = x = m^2 — n^2 = (m+n)*(m-n)
    1.x = (m-n)*(m+n)
    m-n = 1, m+n = x
    m = (x+1)/2, n = (x-1)/2
    deriving b and c from this as : b = (x^2-1)/2, c = (x^2+1)/2
    PS : Look for the corner case when x < 3
    :)

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

First contest for me here! I struggled to see where I was going wrong in B — I'll read the editorial ASAP.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice problem set, I suspected that the problem set was too hard when I came up with complicated versions of solutions when I solved it, until I locked my problem and viewed others' solution went like "Oh... crap. Now my solution seems a risk of implementation."

I wonder if problem E has anything to do with sqrt decomposition, wondered why was the ask query is limited to 2000... Looking forward to see the solution in the editorial as I spent my time on clunky solutions and had no time for it! =D

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Problem E can be solved by 2-Dimension Segment tree.(Which Calcualtes the sum)

    Because the "Ask" Query is only 2000, You can precalculate the number of lightbulb which is included in this query for each garland.

    1. Update the i-st garland. — O(garland_size) * log(NM)
    2. Calculate the sum of the lightbulb which is included in query. — O(logNM)*2000
    3. Repeat for All i(1<=i<=k)

    It is O(Sum of Garland_size + 2000*k)*log(NM)=2000*2000*log(2000)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      And for the "Switch" query, you can just make an check array. Just switch true and false of the check array. — O(q)

      The "Ask" Query will calculate the sum of check[i]*Number_Of_LightBulb[i][query_num]. — O(k)

      The final complexity is O((n*m+2000k)*log(NM)+q)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks for the writing, I understood most of it besides one thing: Why the 2D-segment tree, isn't it enough to compute each garland individually? I suppose 2D segment tree can't speed up the process as different parts of the garlands are inside of the ask range.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Without the 2D-Segment tree, We have to do the Loop which

          1. Update the i-st garland — O(garland_size)
          2. Calculate the sum of the lightbulb which is included in query — O(garland_size*2000)

          It is O(Sum of Garland_size * 2000).

          Because of part 2 has an bad complexity, we have to use 2D-segment tree.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            I just implemented a Quadtree to solve it, and I got smashed my MLE. I am not familiar with implementing both 2D segment tree and quadtree, could you please kindly help point out my mistake? (Maybe I should use an array instead a bunch of pointers?)

            Thanks in advance. =D

            UPD: Nvm, fixed it. =P

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have found another solution for Task E. For every ASK query : - split each garland in continuous subarrays which are included in the query rectangle and sum up the values of those bulbs. - one split can be generated only when the garland 'jump' an edge of the rectangle (maximul 4 * N)

    The final complexity is O(n^2 * log(n))

    19998646

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

So many people solved C... Was it really that easy or you just write the bruteforce out of despair like me?

for (ll b = 1; b <= 1000000000; b++)
{
    ll sum = a * a + b * b;
    if (isSquare(sum))
    {
        ll c = getSquareRoot(sum);
        cout << b << " " << c << endl;
        return 0;
    }
}
  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    It's solution is googleable.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    It took me a long time to figure out the equation version. The last two sample cases are really suspicious, that made me realized you could always let X=(a+b)*(a-b).

    For n%2 you could also find an equation, pick up your pen and you will be surprised. =D

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

    Every pythagorean triple (a, b, c) can be written as:

    a = m^2 — n^2

    b = 2mn

    c = m^2 + n^2

    for some integers m and n.

    From here, it's only a matter of finding a combination of integers m and n that will satisfy one of the three equations and then just substituting to find the other 2 sides.

    For example if the given side is even, it can always be substituted in the b equation where m = 1, and n = b/2. And if the given side is odd, it can be substituted in the a equation: a = (m^2 — n^2) = (m-n)(m+n) ==> 1*a = (m-n) * (m+n) ==> m-n = 1 and m+n = a.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      A minor thing: not every tuple of positive integers (a,b,c) such that a^2 + b^2 = c^2 can be expressed according to those formulas. Example: 9, 12, 15. (https://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple)

      It is true that every primitive Pythagorean triple (one in which the sides don't have a common factor) can be written with those formulas for some m & n. Some non-primitive triples can be written that way too.

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Is the intended complexity for E O(ASK_Q * K * log^2(N)) or there is a better solution?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please explain your approach? I couldn't come up with anything other than sqrt decomposition. :\

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Let's make a list for each garland the i-th list contains the ASK queries that the i-th garland was on during them. Now for each garland let's enumerate through its cells and add the value of the cell to a 2D BIT. And then for each ASK query this garland was on during, let's update its answer by the sum of the rect it represents. After updating all the queries we undo the added value of the cells.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

the second question was too interesting, at least for us newbies, some would pick up the hard implementation approach while there's a simpler solution also..

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone can't visit codeforces during the contest? I can't visit codeforces for about 20mins from 0:15 after contest,and then during 1:00 I can't visit codeforces too.I'm sure that my Internet connection is okay.

»
8 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Saw a O(n*m*q) solution for problem D, writes a generator at the last moment to hack it.

The contests ended and I was left with no time but to hit myself hard with a facepalm.

http://mirror.codeforces.com/contest/707/hacks/249193/test

GOD DANG IT I WROTE "cout<<n<<m;" instead of "cout<<n<<' '<<m<<' '<<q<<endl;"

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Wasted so much time on B(didn't notice that you can't set up a bakery on a storage city) that I had no time for C, but what is the approach for C, do I have to use these?

a = k * (m^2 — n^2)

b = k * 2mn

c = k * (m^2 + n^2)

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve D? I encountered persistent data structure for the first time in my life...

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Offline

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Yeah, offline. I have built tree of requests and walked over it using DFS

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Iam keeping a counter that counts changes, and therefore, I know the answer instantly after each update.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Huh, I did the same but recursively, which TLE-d. I guess function overhead was too much.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Never mind, yours is recursive too.

        Oh, the way you handled the third case is pretty neat — I didn't do that.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I also interested in idea of solution of D.

  • »
    »
    8 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +6 Проголосовать: не нравится

    You can do the operations 1, 2, 3 and their reverses in O(1) and keep track of the total count and the count of the specific shelf.

    For operation 4 I made a list of adjacency for each operation, then after processing this position I would process all adjacent positions and revert the operation after all adjacency positions are processed.

    For example, for the testcase:

    3 3 5

    1 1 1

    3 1

    4 0

    4 1

    3 1

    Then:

    adj[0] = [1, 3]

    adj[1] = [2, 4]

    adj[2] = []

    adj[3] = []

    adj[4] = [5]

    adj[5] = []

    You should process the queries offline. Position 0 is initial state.

    The code.

    Passed systests! Unfortunately I didn't solve C and submitted D at the very end and it wasn't worth much. Anyway, it was an interesting problem to solve.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hi. What does adj[i] represent for? What value it stores? Thank you. ;-)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You have q queries to process, they are numbered from 1 to n, and query 0 is the initial state, when no query was processed. You should store them, calculate and then print the results.

        adj[i] is a vector which stores all queries that should be processed right after query i.

        In the testcase I used you see that query nº 4 (4 1) restores the state right after query nº 1 (1 1 1). That means that query nº 4 should be processed right after query nº 1, so adj[1] contains 4.

        Notice that operation 4 doesn't act on the shelfs so processing it is simply saving the current count of books.

        Since all operations done in the shelfs are invertible, and done in O(1), you can process the queries in a DFS manner without spending much time restoring the state of the shelfs.

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    My solution is probably not the intended one, so it may TLE but this is the best I have came up with during the contest.

    Keep a vector for each position, for each of the queries...

    4) I will start with the fourth one, keep the call time and the reset time. Reset the counter back to the state by tracking the outputs. Time complexity O(1)

    1 & 2) Binary search the lower bound of 4th query call time and the upper bound reset time(Both initially zero), check the size of the operations made outside of the range. Check parity to see if the shelf is filled/not, push back the current time if update is needed. Time complexity. O(logN)

    3) Foreach column do the same thing as 1&2. Time complexity O(MlogN)

    Worst case scenario O(M * q * log N), that should be 3e8 operations, and I have faith in the CF server could handle 1e9 operations/s... Hopefully :P

    UPD: System test case 15 got me, surprisingly by wrong answer not by TLE...

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    D can be solved by implement persistent segment tree directly and answer query online.I used one segment tree of size n and n trees of size m.The first tree store roots of the n rows, flip state and how many 1s in each row.Tree of each row store value of each position.The complexity is O(qlogn) in time and O(qlogn) in memory. My Code

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I like your approach. I solved it directly with a persistent data structure :P

      I represented the state as vector<vector<bool>*>, and I'd just need to create 1 new shelf per query. This passed in 0.5 seconds, but was about 100MB less than the Memory Limit, so it might have MLE'd under certain conditions.

      Check out my code

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Problem c is trivial with euclids formula.

triples are of form (j * j - i * i, 2 * i * j, j * j + i * i) with j > i. If n is not 1 or 2 you can always do it:

If n is odd make the first term n by taking i = n / 2, j = n / 2 + 1 (so we print 2 * i * j and j * j + i * i);

if n is even make the second term n by taking i = 1, j = n / 2 (so we print j * j - i * i, j * j + i * i)

I think this problem made it too tempting to goo into wikipedia and search "pythagorean triple"

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +51 Проголосовать: не нравится

20000000 th submission I can't belive , 20000000!!!

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Surprised so many people solved C..

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    We have access to google, and we ran the search "Pythagorean triplets".

    Sadly, I'll fail systests thanks to n=2

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      What a sad story. I would have ended in the same spot if there wasn't a sample for n=1.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I checked both 1 and 3, but n=even was very trivial compared to my n=odd logic(I didn't realize that was trivial too) and ended up neglecting 2. Yes its very sad. I was hoping rating rise, now, expecting fall.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I didn't consider n=2, luckily someone hacked me and I found the bug.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there anyone who kept on getting WA for pretest 4 in D ? Here is my code 20003997

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Oh, you have the same solution with mine. Take a look on it, my code have passed pretests

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I found the mistake ..while doing DFS I thought that while going back from some edge remove is inverse of add ..but this is not true unfortunately..

»
8 лет назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

I was trying to hack someone's code for E (Garlands) with the largest possible test case (about 92MB) using a generator, but then I got a verdict saying "Generator crashed"--my generator got a TLE instead.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I need more 3 minutes ,so that I can solved problem D. It's a sad story.

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

The solution of problem C can be easily found on many websites, while it's much harder to figure out the solution by oneself in a short period of time. Anyway, great contest, no lags :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I can't find it, any links? thanks!

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    @JeffreyHo ... I figured out a solution myself which is why I guess it is quite a unique one.

    I stored the factors of n in a vector. Since we have n*n to deal with, I basically decomposed n*n into all possible combinations of any two of n's factors p,q such that p*q = n*n

    now, a*a +n*n = c*c => n*n = (c-a)*(c+a) = p*q

    Now assume min(p,q) = c-a and max(p,q) = c+a. Now just check if equation is satisfied. My code

    What I still can't figure out in my own code is ... how hypotenuse cases are handled. My code seems to prove that if a*a + b*b = c*c then there exists x*x + c*c = y*y, OR x*x + a*a + b*b = y*y ... Does this always hold true or is there a counter case. A proof from someone would be really helpful.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      My code always produced answers in which the input was not the hypothenuse. Indeed, if it is possible to get an answer, then there is an answer in which the input is not an hypothenuse, because if the input is a power of 2, 2^n, a possible answer is 2^(n-2)*3, 2^(n-2)*5, and if it is not, let the input n=r*k, where k%2=1, and k>=3. Then a possible answer is 2*(k/2)*(k/2-1)*r,r*((k/2+1)^2-(k/2)^2). So your code has no problem if it doesn't consider the case of hypothenuse

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can O(m*q) solution pass D?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    You can keep a counter that keeps track of change of number of books, so you won't have to iterate over the shelves.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You are right.I didn't think of that point and I submit a solution just to check if it will TLE.But now I find I m too simple because there is no big test in pretest...

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

was my first contest. solved only A and B . :(

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me how to hack?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    1) Lock your solution. (After you passed its' pretest, of course)

    2) Go to the room section.

    3) Select anyone's solution of the locked question.

    4a) Input your test case manually like you usually do in local, this is recommended for simple logic flaws.

    4b) Input your test case by a generator(by your program), this is recommended for pulling of a TLE.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

"being turned on, brings Alesha some pleasure," ...

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve D.i could quyery out 1 and 2 or 3 and 4 in O(1) but how to do 1,2,3,4 all in O(1) time

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    Instead of treating each query one at a time first store all the queries. Then create a tree where for node p the parent node is either p-1 if the query is 1, 2, 3 and k[p] if the query is 4. Then instead of processing the query in order perform a DFS on this tree. Then, as you said it takes only O(1) for queries 1, 2, 3 and query 4 is latent in the order in which we process the query. Therefore O(q).

    I'll add my submission if it passes system tests.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      could you elaborate your algorithm a bit please .I know dfs .Thanks for replying

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        For reference, 20018322

        For example take the test case,

        4 2 7
        3 2
        2 2 2
        3 3
        4 0
        1 3 1
        4 2
        1 2 2
        

        In which we can form the tree,

           0
          / \
          1 4
         /   \
         2   5
        / \
        3 6
           \
           7
        

        where instead of the order 0->1->2->...->7, if we perform with the DFS order of 0->1->2->3->2->6->7->6->2->1->0->4->5, all the queries can be treated in O(1) as you have mentioned with O(q) queries.

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

"being turned on, brings Alesha some pleasure, " ...

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

A completely wrong program (http://mirror.codeforces.com/contest/707/submission/20000102) caused by a misunderstand of the problem (div2D) pass pretest... So weak pretest !!(crying,/(ㄒoㄒ)/)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    pls tell an approach to solve D

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Use SegmentTree. Build a tree for operations. Every operation's which type is 1 to 3 father is the version before it. For type 4,it's father is k. Then use dfs. When you go down ,Change it. When return ,Change it back. Record ans when you dfs.

      Sorry ,My English is not good

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        This is not a segment tree, just tree, I guess

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          You must use some data structure to do changes and qureies. My focus is not on SegmentTree. You must have misunderstood what I meant.

»
8 лет назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

a classic problem is not OK for contests! I'm talking about problem C.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have question about third task, maybe someone can invent good solution.

Let's suppose n must be a hypotenuse. What is minimal complexity for solving third task then?

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +50 Проголосовать: не нравится

Why do the problem — setters include question "C" — div2 where u need to search for formula on google and i am wasting my time thinking of logic , totally useless question that too with a wise score of 1500 pts .One of the Worst Contest I gave till now on Codeforces.

Edit : For anyone who didn't want to solve with that formula look at my accepted solution . Your text to link here...

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Totaly Right.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится

      and because of this , my rating will suffer today , and those who google each and every question for copy pasting answers will enjoy :(

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        It's not that hard to find out the equations by yourself... But yeah, still, it takes a pretty long time to come up with it from 0 to 100.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится -7 Проголосовать: не нравится

          Well , I am pretty sure that those 2000 people didn't derive the equations

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            I mean, the observation itself definitely deserves a Div2C difficulty, but I agree that it solution can be googled made it unfair both in terms of difficulty and the observation time.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится

              Deriving this is actually kinda easy. I was the first person on Div 2 to solve C, and I pretty much just used a very simple O(1) derived from simple factoring.

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Very Bad Pretests in A & C.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I guessed it from the "pretest passed" response. it was so quick. :D

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    But apparently, the pretests for E are very strong, since only one submission that passed the pretests failed the system test. I'm not sure about hacked submissions, though.

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

In problem A , I thought that there's no space between characters of each line , and my code passed the pretest ... I know it's my mistake but I think you should use better pretests ...

»
8 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

I guess the complexity of intended solution of pE is O(2000*(n+m)).

For each "ASK" query, all garland enter or exit the rectangle range at most O(n+m) times. We can exploit this property and consecutive sum dp to solve this problem.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can any one tell me why this failed the test 19984978?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

c is the worst problem ever you can google it and get the mathematical law

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

This contest was for hackers, not for coders

Darn I failed B because I set infinity as 10^9, not 10^9 + 1 :(

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i set it to 10^9+1 but now i got TLE on test41

    why dont problem setters just use hard and extreme test cases for the contest

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Because we all need hope.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      your TLE should not be for that . my infinity was 1e15 and get AC, actually it is o(m), for each edge you should check if one head is storage and the other is not and answer is the minimum value of the "OK" edges

»
8 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

why my "19990351" is WA?

include

include

include

include

include

include

include

include

using std::sort; using std::max; using std::min; using std::cout; using std::stack; using std::cin; using std::endl; using std::swap; using std::pair; using std::vector; using std::set; using std::map; using std::multiset; using std::unique; using std::queue; using std::greater; using std::string; using std::priority_queue; using std::lower_bound;//返回第一个不小于 using std::upper_bound;//返回第一个大于 using std::max_element; using std::min_element; typedef long long LL; const double PI = acos(-1); const LL LINF = 0x3f3f3f3f3f3f3f3fll;//4e18 const int INF = 0x3f3f3f3f;//1e9 const double eps = 1e-8; const int MOD = 1 << 16;

int n, m;

int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) { char ch; scanf("%c ", &ch); if (ch=='C') { cout<<"#Color"<<endl; return 0; } if (ch == 'M') { cout<<"#Color"<<endl; return 0; } if (ch == 'Y') { cout<<"#Color"<<endl; return 0; } } cout<<"#Black&White"<<endl; return 0; }

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone tell me where is the mistake? http://mirror.codeforces.com/contest/707/submission/19983693

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You have 2 nested loops both using the integer i.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      that's not the mistake because i is redefined in inner loop so outside i is unaffected.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      That's not the real problem as the nested i doesn't affect the another one. The problem is getline stops at ' ' so only 1 character was read per loop.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I tested in my system, it reads whole line however problem i found is that it's not scanning first row !! can you explain why?

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          When you read n and m you are not actually reading the entire line, you need add a

          cin >> ws;
          or
          getline(cin, st);
          

          Right after you read n and m.

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

what is wrong in this solution for A

http://www.codeforces.com/contest/707/submission/19984174

It failed on test case 5

Plzz Anyone tellme the mistake

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I got score 0 this competition and I DONT KNOW WHAT IS WRONG WITH EVERY SOLUTIONS I PUT IN THE SYSTEM!!!

a -> http://mirror.codeforces.com/contest/707/submission/19984724

b -> http://mirror.codeforces.com/contest/707/submission/19995846

d -> http://mirror.codeforces.com/contest/707/submission/20003567

somebody please help me!!!

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    for problem B the max cost equals int(1e9) that is large than the initial value of cost you defined cost=987654321;

    My solution failed also due to a similar mistake. :(

    I made the the ans = MOD where MOD is a predefined const variable equals int(1e9) + 7; but sadly I changed it to be int(1e9) before and forgot to edit it again. :'(

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    a) '\n' character was read in the first line.

    b) The dummy value was not set high enough, you set it to 9.87e8 but the edge limit was 1e9.

    d) Let the time complexity aside, this line -> "q=q-(i-c);" is probably a bad idea.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    in B your problem is this line : cost=987654321. The distances are up to 1e9, so your program gives WA in test

    2 1 1
    1 2 1000000000
    1
    

    which I managed to hack with succesfully :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Man, my condolences.

    As for the solution for B, I think that you have set too small initial value for the cost = 987654321. The max value, that you can get is 109 and your variable is already less than that.

    The other problem is that your arrays are of size 20000 = 2·104, but the max number of cities is 105 = 100000.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can we please have a statistic about how many contestants had '\n' and ' ' slayed in problem A. =P

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

WA on test 85 for problem C.

http://mirror.codeforces.com/contest/707/submission/20001952

I am the unluckiest person in this contest :/

»
8 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Very bad contest. Very bad pretests. :-(

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    In my opinion that makes this contest great — many opportunities for hacking! Be happy, that there are at least some pretests and not just final system testing.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    pretests for B and C was weak .. I think...

»
8 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

System testing stuck on 100% for a long time. :/

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I think the pretests are too bad :( but anyway,thanks for preparing this contest and also thanks for Codeforces' good job.

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Yes, C was bad, but B and D are really interesting, imho

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can Anyone explain why this solution works he's taking 2*m*n inputs . why no TLE ?

http://mirror.codeforces.com/contest/707/submission/19985014

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    because m, n <=100. So 2*m*n <= 20000. Usually for 1 second, 10^7 operations will pass.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      u are not getting the question . actually per test u should take a m*n matrix as input but this guy is taking 2*m*n inputs , he's taking extra inputs.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    When you reach the end of input cin doesn't do anything.

    Note that when you run your program on your computer with console I/O, when your program reaches a line like cin >> x, the operating system will pause your program and wait for the user to enter a whole line of input. Only after that the program will resume. You can actually enter the end-of-input character on Windows by pressing Ctrl+Z.

    When the codes are graded on CodeForces, I/O is redirected to/from files or by means of a pipe (not sure), these methods automatically append the end-of-input signal. You can safely put a line like cin >> x at the end of your program for testing purposes.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

B and D and E without tags!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://www.codeforces.com/contest/707/submission/19995711 : This submission in GNU C++11 gives compilation error while same code http://www.codeforces.com/contest/707/submission/19996044 in GNU C++ gives accepted.This happened during today's contest Luckily I shifted to GNU C++. Can someone tell why this weird thing happened?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Not completely sure, but when using C++11, instead of declaring iterators as iterators, you can declare them as autos, and the compiler will automatically assign them the correct type to your variable. This is less error-prone than declaring individual types

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    It's because name hash of your global variable is already used by std::hash in c++11.

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

I hope next time who set contest try to avoid problems based on mathematical rule only (like C) ,who set contest should know this is online contest and anyone can ask google or Quore or stackoverflow.

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I was a little bit suprised when so many people solved problem C. I didnt google it and I found the divisors of n^2 and then since x^2+y^2=z^2 => x^2 = z^2-y^2 => x^2 = (z-y)*(z+y) where x =n, and for any triangle since the equation |z-y|<x<z+y should hold, I iterated the divisors of n^2 starting from the smallest one and till n since (z-y) must be smaller than x(also n). and then I found z-y and z+y and checked whether it is valid or not.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    but to check the divisors of any number i know that you should iterate till the square root of the number in this case the sqrt of (n^2) will be O(n). n= 1e9 which will not fit the Time ?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      oh my bad I check divisors of n because no need to find divisors greater than n since z-y cannot be greater than n

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem C,

Katya wondered if she can specify the length of some side of right triangle and find any Pythagorean triple corresponding to such length? Note that the side which length is specified can be a cathetus as well as hypotenuse.
What does it mean ? As far as I understand, the given length can be any side including hypotenuse. But if I see the tests, I couldn't find any test where the given side is hypotenuse. Am I missing something ?
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The easiest way would be to take the given side as the smallest side and work out the lengths of the other two since input is at most 10^9.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe it was just for tricking people that didn't came up with the equation, whose uses brute force to consider one more case and fall into TLE.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Div. 2 A, my code got WA on test 11, while the same code gives the correct output on my system and also on ideone

ideone

codeforces

Does the input have some extra '\n' characters or spaces? :/

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

I suppose DFS is a common solution for D. I have absolutely no clue what idea stands behind that.

However, I had another idea which is basically coding persistency described in the problem. In exchange I would love some people with a DFS solution to explain their solution in detail.

Let's observe what happens with the bookshelf on each step: you at most change one row (inverting books). Thus, a dumb solution would be for each query keep a node which has pointers to N bitsets of length M. Then, whenever you need to modify a bookshelf, just create an identical node to the one on the current step but change one pointer to a new bitset. Going back to older version simply means taking the node from that step. In total, for each query you create a bitset of length M, a node with N pointers. In terms of complexity, it works fine. In terms of memory, it's a bit consuming though: Q * (sizeof(bitset of size M) + N pointers) = Q * (M / 8 + N * 4) = 412 MB which is close to memory limit.

Not to risk, a smarter solution is to create two layers: root node has 25 nodes to nodes with 40 pointers to bitsets (25 * 40 = 1000). Now on each query you add one bitset, one node with 40 pointers, and one with 25 pointers, which is about Q * ((40 + 25) * 4 + M / 8) = 38 MB.

Now how do you use DFS to solve the problem? Thanks!

UPD: Even the dumb solution passes -_-

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    http://mirror.codeforces.com/contest/707/submission/20009279

    Actually you are pretty close to the solution. Instead of keeping the bitset of the current shelf and keep pointers of the state whenever you are asked to go back for it, we can consider it in another way.

    State 1 -> State 2 -> ...

    State 1 -> State X(where query 4 1 was called)

    And here we can perform an dfs, we perform the modifies needed, and revert the actions of "state 2 ... state X-1" to retrieve the state of the shelf. This means instead of requiring O(n*m*q) from rebuilding the whole shelf, or O(q*q) which reverts everything online, you can see that solving it offline only takes O(q).

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Put the intended solution aside, I am really surprised that the bitset has managed to exploit the memory limit. That's a new trick I've learnt today. =D

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

    Problem D can be solved by using an offline approach.

    We will read all queries before answering any of them and, in the reading itself, we will build a tree. The tree can be built in the following way:

    • If the query i has type 4, then it will ask us to return the shelf state to the one of query k; in the graph, it means k is the father of i.

    • If the query ihas type different from 4, then the father of i is i - 1.

    Now, we have built a graph which the state of a node only depends on the operations done by its ancestors. With this in mind, we can maintain a global "state", which will be the answer for each query while we traverse the tree. Whenever we get to a node in the traversal, we apply the operation of that node to our global "state"; and whenever we leave that node (i.e., its recursion is ending) we deapply (what would be the correct word here?) the operation of the respective node. This way, we have the correct "state" for every node in the tree, since no node will influence the answer of any node that is not its child.

    If there is something unclear or some silly mistake, feel free to ask/correct.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did the same thing during the contest (though I've now also coded the DFS thing that everyone suggested). In case you want to see it, here it is: http://mirror.codeforces.com/contest/707/submission/20002884

    Before I coded it, I considered the memory usage and also tested it to see that it would work out just fine in theory, but to be honest, I was more concerned that the O(m*q) runtime wouldn't be fast enough. I figured with an efficient c++ implementation it could work though... Anyway, it turns out that when I tried the most problematic case for this approach (essentially all of type 1) it ran on my computer in 0.8 seconds so I figured it was good enough. Also, the DFS approach as far as I understand also takes O(m*q) time so it's not like it's that much better.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Oh I see that you can actually change the DFS approach to work in O(q) time. Well I guess I was unfairly helped by the lax memory and time requirements =P.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How harsh that 4 or 8 wasn't a pretest for C. I wrongly assumed n was always the smaller cathetus and passed the pretests

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    the pretest in this contest was so bad

    this contest was hacking contest not for solving problems

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What is the DFS approach to problem D ? I was able to come up with an easy online solution using a persistant segment tree, But cant figure out the DFS one. Someone please brief. Also, AC solution using persistant Segtree: http://mirror.codeforces.com/contest/707/submission/19996544

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't know about DFS, but simply storing the queries in a vector, and queries of 4th type in another vector and sorting this second vector will also work.

    But the DFS method seems to be common, I'm curious to know a well explained solution too!

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    In the dfs approach you try to keep the history of jumps due to query of type 4.

    1. We store all the queries first.

    2. Using this list of queries we build the graph with query no.(order in which they appear) as vertices and logical sequence of executing the query as edges, the graph is build by traversing the queries:

      (a). For queries of type 1, 2, 3 you add an edge for the given query no and given query no - 1.(that's the standard order in which you want the queries to be executed one after another)
      (b). For queries of type 4 you add an edge for the given query and the query point referred by it(I am assuming the graph to be undirected but not necessary).(We do this so that we can evaluate both branches(one due to the normal order of queries and other due to this 4th type of query) while doing the dfs in future).
    3. So after building the graph you start the dfs, now for every vertex you visit you apply the query and while leaving you deapply(not a word I know :P) the query to return to the state where you were before entering the branch of the graph so now you can evaluate those jumps without any problems.

    4. You store the book count for the corresponding query after applying it, in an array.

    5. Traverse the array and print the values.

    I hope this is quite clear, and

    Here's link to my submission:

    http://mirror.codeforces.com/contest/707/submission/20014005

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Great explanation!! But instead of deapplying, we can check the number of children the node has. If children>1, it means there's a query of type 4 for this node. Just store the value computed this far in the tree for those children. This way, we will always evaluate query 4 first, and we don't have to deapply.

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        No, I don't think that is possible. Suppose you have linear graph of say size q/2. add one more node as neighbour to every node, i.e every node has two edges except the leaf nodes. Something like this:

        root

        |\

        |\

        |\

        ..

        ..

        upto q/2

        So you will have to save the state(I am assuming the raw and naive state i.e state of every shelf and every book in every shelf) of q/2 nodes say you store it in bitsets, then also you will need q/2*n*m bits = 5*10^10 bits = 6.25*10^9 bytes=6.1*10^5 kb = 5960 mega bytes. Unless you have a better way to store the states, this might not work.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I think my understanding was wrong, but this is what I see :

          There is one chain, and each node in the chain can have some leaves, which are the 4th query. The last node in the chain can have some 4-queries, or none. If the last node on the chain has one 4-query, then we process it and return. Therefore, apart from checking no. of children a node has, we also have to check for the case that if there's only one child, whether or not that child is a 4-query(only the last node on the original chain has this).

          If any of the nodes in the main chain is a 4-query, then we won't be able to check the way I proposed. So, we'll have to first make the main chain(all q queries), then separately add the 4-query nodes to the main chain with a flag that indicates that this is not in the main chain.

          This is actually very cumbersome, and we could've achieved offline by simply sorting a vector of 4-queries and processing the list of input queries upto each element in the 4-query vector. These are two separate vectors.

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

For C

You know that the difference between squares is odd and there is a pattern.

1 4 9 16 25 36

3 5 7 9 11

Where in every odd number comes

Hence if n is odd n * n can be found between two consecutive squares.

if n is even bring it down to the nearest odd.

if n is power of 2 then for 2 it is -1

else for 4 you know 3 and 5

so you know a triplet for every power of 2 as well.

Came up with this solution in an hour. Guess should have googled it :P

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

http://mirror.codeforces.com/contest/707/submission/19994995

In problem E, I used 2d summation table for each garland. I think its worst time/space complexity is O(n^3), but I got AC...

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

some one tell me how to derive a formula for C ?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Good day to you,

    the "things" in C are Pythagorean Triples — you can find a nice article here.

    Hope it helps

    Have nice day! :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://www.codeforces.com/contest/707/submission/20012886 That case 53 for which it is showing wrong answer is actually correct..I have calculated it with calculator,,Can someone tell me why it is showing Wrong answer?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    You may have mistaken the answer for what your program output. Your output is definitely not a Pythagorean triplet.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      sorry for hacking you man, I hope you read the problems completely for now on

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I honestly appreciate it. I was able to fix it afterwards. In fact every question I solved this past contest was judged correct but failed system tests or were hacked. I'll definitely be thinking a little harder next time!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    (96466018,96466082,111120) is a Pythagorean triple,not (96466018,96466082,111117):)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    the value of the phythagorean triplet in your output is (96466081.996544324252684266295429) you have to sure that the values are correct before output it

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

i think my solution for prob C is quite simple

we only need to consider the case of which n is a cathetus

we need to find a, b such that n^2=a^2-b^2

so n^2=(a-b)(a+b)

since a-b is a divisor of n^2, and a-b and a+b must have the same parity with n then a simple solution is a-b=1 for odd n and a-b=2 for even n.

therefore for odd case we have ( (n^2-1)/2;(n^2+1)/2) , and ( n^2/2-1;n^2/2+1 ) for even case

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    for n<=2 there are no solution, but for n>2 there's always a solution so we don't have to consider the case of which n is a hypotenuse

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem D?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Problem D: 20003798 can anyone tell me why I got RE in this submission I just use dfs and get back function.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There are q Nodes, i.e. 1e5 nodes at max.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But I set MAXN=1e5+5 Can you explain more details please?

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Oh, my bad... Sorry for the confusion.

        I just fed it with 1e5 queries of "4 0" and nothing went wrong, I shall see if random generated cases will trigger the RE.

        UPD: Well... I can't find the case... Hopefully someone else can point it out for you.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          I find if type == 4 i will be larger than 1000 but when I solve different types in dfs I use sum[i], flag[i], sh[i][j], i will extend the edge (in type 4) That's why I got RE

          It's a fool error.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

When will the tutorial be released?

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

7000+ coders participate in this contest. Maybe because the contest time is not that late as usual and begins at 21:00 in UTC+08. (In general, contest starts at 00:30 in UTC+08...) Hope more contests can start earlier.. ;-)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Surprisingly, this time I have not seen any freeze or delay of web, despite of this number. I think they have hardened the back end.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For D it seems a simple simulation would suffice.

You can create the adjacency graph.

But for simulation of the process divide m into 29 bits of 35 (in worst case) integers and simulate. Operation 3 takes O(35) units of time (simple XOR'ing with all ones) in worst case.

Here is a passing solution — http://mirror.codeforces.com/contest/707/submission/20019991

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Has anybody received notification letter before the contest? I might have missed the contest owing to the absence of the announcement.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think the test data for E was weak. How could this solution 20022277 pass system test?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

hahahhahahaha