zloyplace35's blog

Codeforces Round #368 (Div.2)
By zloyplace35, 8 years ago, translation, In English

Hello everybody!

Codeforces Round #368 (Div.2) takes place on August 20th. As usual Div.1 participants can join out of competition.

I am the author of all problems.

I want to thank danilka.pro and GlebsHP for helping me prepare this contest, vovuh for testing it, Roms for statement reading and MikeMirzayanov for platforms of Codeforces and Polygon.

I advise you read all problems, hope, you will enjoy them :)

Good luck and have fun!

UPD1: 500-1000-1500-2000-2500

UPD2: tutorial

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

Comments Comments (255)
| Write comment?
»
8 years ago, # |
  Vote: I like it -45 Vote: I do not like it

It seems interesting:)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it
    I am good at half-zhang. So take my bus quickly.yo ka wa ka ti ki yo ku la wu!
    竜がこの水物なトピ主を喰らう!
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      no one will understand what "half-zhang" is unless he is a Chinese...

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

      The server has handled even more participants before, so don't worry, just concentrate.

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

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

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

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.

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

    I think you've got the wrong post...

    but your words are really nice

    :)

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -131 Vote: I do not like it 
if(contestIsBy("amd"))
    scoring = "500 , 1500 , 2000 , 2500 , 3000"
    solved = "2000 , 800 , 20 , 1 , — "
else
    scoring = solved = usual
→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +98 Vote: I do not like it

    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.

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

      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

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

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

Must be an interesting contest, 7000+ participants.

Good luck for ya all.

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

Where is scoring distribution?

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

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

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

coders are increase day by day.

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

I really like round. Thanks for nice contest :)

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

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.

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

    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)

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

      Interesting. Thanks for the help!

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

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

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

      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 ?

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

        No, no, no. It's much more simple. They just google it.

        Here is justification for that behavior Click.

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

    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

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

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

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

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

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

      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.

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

    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

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

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

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

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

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

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

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

    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)

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

      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)

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

        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.

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

          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.

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

            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

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

    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

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

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

    It's solution is googleable.

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

      Ok. So, at least, I didn't cheat =)

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

        Using prewritten codes or resources that are published before contest is not considered as cheating.

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

        If the solution is googleable it just means the problem is unoriginal, nothing more.

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

    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

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

    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.

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

      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.

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

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

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

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

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

      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.

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

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

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

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://codeforces.me/contest/707/hacks/249193/test

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

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

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)

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

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

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

    Offline

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

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

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

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

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

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

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

        Never mind, yours is recursive too.

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

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

    I also interested in idea of solution of D.

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

    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.

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

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

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

        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.

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

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

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

    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

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

      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

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

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"

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

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

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

Surprised so many people solved C..

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

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

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

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

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

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

        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.

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

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

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

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

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

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

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

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

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

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.

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

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

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

    I missed submitting Dijkstra for B by 10-20 seconds.. Yeah I know it has a better solution but couldn't come up with it.

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

      How exactly would djikstra help here . Wouldn't fit in the time limit i guess .

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

      You just need to look at the k cities with storage.
      For each city with storage you analyse all the adjacent cities. If the adjacent city does not contain a storage, then you can create a backery there.

      As you move along these k cities, you track the minimum distance between the city with storage and adjacent cities without storage. There is no need to go deeper.

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

      I am not sure that Dijkstra will pass

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

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

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

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

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

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

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

      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

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

can O(m*q) solution pass D?

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

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

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

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

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

Can anyone tell me how to hack?

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

    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.

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

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

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

    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.

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

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

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

        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.

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

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

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

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

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

    pls tell an approach to solve D

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

      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

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

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

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

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

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

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

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

    anyway it was a new experience, I'll google your problems in your next contest

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

    It is actually a good problem for educational rounds.

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

      That's exactly my thoughts about C.

      The coordinator could've asked for another C problem and used this one in a future educational round.

      This one aside the contest had very good problems.

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

    I got AC without Googleing. Running time was O(n) though, not O(1).

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

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?

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

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

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

    Totaly Right.

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

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

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

        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.

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

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

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

            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.

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

              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.

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

Very Bad Pretests in A & C.

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

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

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

    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.

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

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

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

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.

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

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

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

    never mind found the mistake

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

      The unseen '\n' is the deadliest.

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

      what is the mistake? I am same as you and i got WA in 5

      http://codeforces.me/contest/707/submission/19984724

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

        mine are different my code shows black&white even if there is a coloured pixar but it should show colorful

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

        I think your problem is than when you read n and m, the first char you read is the '\n' after the two integers. Then, you don't read the last character of the input, and if that character is the only one that is not W,B,G, your answer will be B&W, when it should be color. Use scanf("%d %d ",&m,&n) to skip the '\n' and avoid that mistake.

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

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

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

    Yet you failed at that google-able worst problem ever.

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

      i tried to solve it without cheating

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

        Cheating or no cheating, it's still not the worst problem ever. Though I might agree if you said unoriginal.

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

          also it's not it's not a logical or implementation problem if you know the mathematical law you will get Accepted without thinking on the solution

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

This contest was for hackers, not for coders

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

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

    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

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

      Because we all need hope.

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

      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

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

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; }

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

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

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

    You have 2 nested loops both using the integer i.

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

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

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

      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.

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

        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?

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

          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.

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

            Damn,small detail costed a WA !! thanks anyway!

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

            cin.ignore() would also be a great command to learn.

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

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

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

    Same happened with me!!

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

    Probably because scanf also reads blank spaces as characters.

    ex: 2 2 G G G Y

    Your code says that it's #Black&White.

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

    The invisible '\n' character got you.

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

    just a guess

    change scanf("%c",&a); to scanf(" %c",&a);

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

    You're almost reading the char wrongly.

    scanf("%c",&a) reads also the spaces you should make it scanf(" %c", &a)

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

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

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

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

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

somebody please help me!!!

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

    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. :'(

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

    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.

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

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

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

    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.

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

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

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

WA on test 85 for problem C.

http://codeforces.me/contest/707/submission/20001952

I am the unluckiest person in this contest :/

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

    at least, you won't make the mistake again (;

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

Very bad contest. Very bad pretests. :-(

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

    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.

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

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

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

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

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

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

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

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

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

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

http://codeforces.me/contest/707/submission/19985014

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

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

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

      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.

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

    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.

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

B and D and E without tags!

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

    Dabagh's rating in all(three) his contests are 1516 :D his diagram is horizintal :D

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

      Thats one of the amazing things i ever seen !

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

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?

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

    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

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

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

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

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.

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

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.

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

    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 ?

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

      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

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

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

    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.

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

    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.

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

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? :/

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

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 -_-

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

    http://codeforces.me/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).

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

      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

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

    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.

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

    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://codeforces.me/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.

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

      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.

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

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

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

    the pretest in this contest was so bad

    this contest was hacking contest not for solving problems

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

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://codeforces.me/contest/707/submission/19996544

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

    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!

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

    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://codeforces.me/contest/707/submission/20014005

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

      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.

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

        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.

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

          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.

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

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

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

http://codeforces.me/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...

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

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

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

    Good day to you,

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

    Hope it helps

    Have nice day! :)

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

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?

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

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

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

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

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

        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!

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

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

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

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

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

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

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

    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

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

How to solve problem D?

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

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

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

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

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

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

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

        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.

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

          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.

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

When will the tutorial be released?

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

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

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

    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.

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

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://codeforces.me/contest/707/submission/20019991

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

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

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

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

→ Reply