bharat.khanna.cse14's blog

By bharat.khanna.cse14, 3 months ago, In English,

Hello Codeforces,

Manthan, Codefest 17 will take place on Sunday 24th September, 2017 20:05 IST with a duration of 2.5 hours (tentative). The round is rated for both Div1 and Div2 participants and consists of 7 problems.

The Department of Computer Science and Engineering is conducting Codefest from 22nd-24th September. Manthan (मंथन in Hindi, meaning Brainstorming), the algorithmic programming contest under the banner of Codefest, is being held as a special Codeforces round. The round follows regular Codeforces rules.

The round is prepared by bharat.khanna.cse14, ayush24 and divyam.

We express our heartiest thanks to KAN and gritukan for their help in preparing the contest and MikeMirzayanov for the awesome Codeforces and Polygon platforms!

Prizes:

Overall 1st place: INR 25,000 Overall 2nd place: INR 18,000 Overall 3rd place: INR 12,000

1st place in India: INR 10,000

1st place in IIT(BHU) Varanasi: INR 4,000 1st place in freshman year, IIT(BHU) Varanasi: INR 1,000

About Codefest: Codefest is the annual coding festival of the Department of Computer Science and Engineering, IIT (BHU) Varanasi, which is held online and is open to participation by all! Register on the Codefest website now! Total prizes worth ₹400,000/- up for grabs with events covering domains from Math, Machine Learning, Natural Language Processing and Capture The Flag style competitions. Go to the Codefest website to find out more!

UPD1: The scoring distribution is 500-1000-1500-2000-2500-3000-3500

UPD2: System testing has been completed. Following are the winners of the contest:

1. anta

2. moejy0viiiiiv

3. tourist

4. Shik

5. LHiC

Best in India:

rajat1603

UPD: The editorial for the first 4 problems has been posted. We will update the editorial of the rest 3 problems soon!

Announcement of Manthan, Codefest 17
 
 
 
 
  • Vote: I like it  
  • +178
  • Vote: I do not like it  

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

7 problems in 2 hours?!

UPD: Contest extended.

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

    Maybe it's like Div 2A, Div 2B, Div 2C/1A, Div 2D/1B, Div 2E/1C, Div 1D and Div 1 E?

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

      I think they should extend the contest a bit. 2 hours and 30 minutes would be better I think.

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

        Why so many downvotes? I just said my opinion!

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          Rev. 2   Vote: I like it -42 Vote: I do not like it

          Well the users are about to be crazy.

          Codeforces users' attitude to comments :

          Useful: Ok, upvote for him, it's nice to me.

          Useless: DOWNVOTE!_(It's not harmful to me and not useful,So why upvote?)_

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

          ignore these shit tards my friend.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it -43 Vote: I do not like it

    1

»
3 months ago, # |
  Vote: I like it -26 Vote: I do not like it

This contest will consist of lots of mathematical problems. This is speciality of Indian contests. Brush up your maths skills to perform well. :)

»
3 months ago, # |
  Vote: I like it -23 Vote: I do not like it

Can people currently not enrolled in college participate and compete for prizes? :P Just asking for clarification as the post doesn't put any restrictions!

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

    Anyone can participate and win the overall 1st,2nd and 3rd prizes. Same is true with the best in India prize.

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

Where can I find the tasks of past years of machine learning and cyber security contests?

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

    These are the links for the previous year's machine learning and CTF contests.

    Also, this year's CTF event has already started and can be found here.

    This year's machine learning and NLP events will also start soon.

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

      it seems last year's machine learning problems are not available, also registering for CTF is closed

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

        Last year's Machine Learning problems are only visible to registrants of the contest. I think it is some error on Hackerearth's side. Registrations for CTF are open again. You will be able to register now.

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

          it seems registration for CTF is not working, sign up button is not responding in particular.

          I did some investigation and it seems the POST request initiated by ajax technique when I press sign up is getting error 500

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

            If name field gets red after sugn up button, just try to login. it worked for me Even tho I never got "successful registration" or email of any sort.

»
3 months ago, # |
Rev. 3   Vote: I like it -115 Vote: I do not like it

Is it rated?

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

    The round is rated for both Div1 and Div2 participants and consists of 7 problems.

»
3 months ago, # |
  Vote: I like it -31 Vote: I do not like it

It is hard to belive that 7 problems for 2 hours... Ok. We will do this. :D

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

    Manthan, Codefest 17 will take place on Sunday 24th September, 2017 08:05 IST with a duration of 2.5 hours (tentative).

»
3 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Hope it'll be a nice round, and no math and geometry.Wish everyone high rating.

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

    And it must be XD.

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

      regular trainings will improove your skill, just try your best

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

    well every one cant have high rating ...

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

      Well..... Didn't the announcements always wish every one high rating?

      Maybe I said something wrong o(╥﹏╥)o.

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

        thats just an impossible thing :) only happens if every one gets the exact same score which is impossible

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

    I won't post any comment taking about the future contest.Every time I post such comments I got TONS OF DOWNVOTE!!!!!!!

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

When I saw IIT BHU's event, I was expecting praran26 as one of the problem-setters.

»
3 months ago, # |
Rev. 2   Vote: I like it -49 Vote: I do not like it

contest prepared by IITians.

»
3 months ago, # |
  Vote: I like it -52 Vote: I do not like it

Is this contest rated?

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

    Sometimes we should enjoy the process of the game rather than care about the rating...

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

      Some people enjoy contests because of the learning opportunity, some want to be the best in the long-term ranking, some compete just for fun. I don't see why anyone //should// anything :P

      That said, Ctrl+F "rated".

»
3 months ago, # |
  Vote: I like it -28 Vote: I do not like it

My First Rated Contest.

All the best to Indian Guys. Your Prime Minister is very aggressive. Namo Namo !

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

The time in the link text is incorrect it should be 20:05 IST, not 08:05 IST.

»
3 months ago, # |
  Vote: I like it -46 Vote: I do not like it

The university is next to my home and currently facing students protest for a girl's molestation , i hope they don't do in the contest :D

»
3 months ago, # |
Rev. 3   Vote: I like it -77 Vote: I do not like it

Sorry!!!

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

gl hf

»
3 months ago, # |
  Vote: I like it -23 Vote: I do not like it

The contest duration is 2.5hrs but the banner says 8:05 pm — 10:05 pm. It should be 8:05 pm — 10:35 pm.

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

Where will this contest be held?

»
3 months ago, # |
  Vote: I like it -37 Vote: I do not like it

No doubts all IIT guys knows problems...

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

    Even if they did, it won't matter. Cause they won't be able to win. :D

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

It is 13 minutes before the contest starts and I cannot register. I says "Registration Completed". Shouldn't registration complete 5 minutes before contest?

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

    That means you already registered

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

      LOL I realized that five minutes in when it let me enter submit code tab.

      /╲/( ͡⎚ ͜U ͡⎚)/\

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

Scoring?

»
3 months ago, # |
  Vote: I like it -46 Vote: I do not like it

Is it rated ?

»
3 months ago, # |
  Vote: I like it -36 Vote: I do not like it

I know that all of the problems are about religion

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

Is it really Div1 + Div2? Seems like just Div1 xD

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

    In B, Did you applied DP ?

    It smells like DP.

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

      No need for dp.
      You need to try all a[i] as a coefficient for q value. Once you have chosen a[i] * q you need to take the best a[left] for p value and take the best a[right] for r value.

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

        This is all I did. Find maxes for each

        p multiplied by each array item
        
        q multiplied by each array item
        
        r multiplied by each array item
        

        and return the final sum. One test kept failing. Did we have to return sum%(10^9+7) or something?

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

          No. p<=q<=r. So You Should keep in mind that if q != p then you can't use r if r <= p.

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

          Doing that won't ensure that you chose i <= j <= k when building sum a[i] * p + a[j] * q + a[k] * r. One of the right solutions (I don't know if there are more) is Pixar's above.

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

            missed this. so naive.

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

              me too lol

              that's why test case three didn't work i think

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

        Precomputing the best a[left] and a[right] is DP!

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

          Is it dp?

          int sum = 0;
          for (int k = 1; k <= n; k++)
              sum += k;
          
          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yes you can call it dp, since to calculate the sum upto index 'n' you have used the sum upto index 'n-1' which in turn uses sum upto 'n-2' and so on. This is only what defines dp..

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

            In some sense yes. But even if you say no. I'm sure that you don't compute the best a[left] with a for loop for each a[i]. This will get you TLE. I cannot see your solution yet, but I'm sure you precomputed all best a[left] and a[right] values. And that is DP.

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

              What about this one?

              int sum[n + 1];
              sum[1] = 1;
              for (int k = 2; k <= n; k++)
                sum[k] = k + sum[k - 1]; 
              
              • »
                »
                »
                »
                »
                »
                »
                »
                3 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I think prefix sums are a form of dp.

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

                Of course, this is DP. DP is a recursion + memoization. The recursion here is sum(k) = k + sum(k-1) and the memorization happens when you compute all values and store them in an array.

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

                  Ok.
                  I always thought that it is necessary that we have exponential number of states in the original problem.

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

                  i think you meant memoization

                  but i shouldnt really be talking cuz i suck at dp

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

                  Yes, you are correct. Although memoization and memorization bascially mean the same thing. memoization is just the computer science term for memorization.

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

        Hello pixar,

        I have looked at your solution but I can see that you are considering all possibilities based on whether p,q and r are either positive or negative? Am I correct?

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

          Yes, you are correct. That is the first solution that came to my mind. After I have submitted solution I realized how it could be simplified.

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

Am I the only one seeing codeforces like only the left half of it and right side is blank? Edit: sorry I had clicked on mobile version by mistake

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

shit > Problem D

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

Waiting for problem B massacre during system testing :)

»
3 months ago, # |
  Vote: I like it -33 Vote: I do not like it

How To Pass That Case In B With C++ :- 1 -1000000000 -1000000000 -1000000000 1000000000

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

    Please ask these things after the contest

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

      Sorry

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

        why don't you use long long ?

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

          No. long long is out of range as the result will be -3000000000000000000

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

            long long can handle numbers from -9223372036854775807 to 9223372036854775807.

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

              the 1st rule of the fight club — nobody should know about fight club

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

              it is -922337203685477580 8, not 7.

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

After the contest ends, can someone tell me how to solve that C? (btw, rip rating)

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

    My solution:

    We can distinguish three types of parents for each node:
    1. A parent which is high security, which means this node has to have a type that is smaller than k
    2. A parent which is not high security, but has a type 1...k-1, so this node could be high security, or have a type from 1...k-1 or from k+1...m
    3. A parent which is not high security, but has a type k+1...m, so this node can not be high security, but it can have a type from 1...k-1 and k+1...m

    So you can specify a dynamic programming state as node id, parent type, number of high security nodes in subtree, which leaves a complexity of O(N*3*x)=O(Nx) which is small enough.

    I didn't manage to implement it during contest successfully, but I'm pretty sure it's correct :/

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

      I came up the above you mentioned in about 15 minutes, but still can't solve it during contest:(

      If you know the subtree for this vertex has exactly i high security nodes, how can you know how many high security nodes come from each child?

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

        You can start of with the first child and try to give it j (ranging from 0 to i) high security nodes, and then there will be i-j nodes left for the other children. So here you can keep another dynamic programming state with properties node id (of the child), number of high security nodes left for the remaining children (so i-j) and type of parent. This will take an additional O(4*i*N)=O(Nx), so it should still be OK.

        Basically just try out every number for each child and use dynamic programming to avoid TLE.

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

Can someone tell me after contest what may be wrong with solutions for D in case 9 ? Is there any special condition that you can figure out from the problem statement that is not so obvious? Thanks

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

At first I thought B was too easy and submitted it 2 times..But then i realized they said i<=j<=k and I stopped...out of 7 problems they cant afford to have two easy problem for newbies like me... Why so cruel!!!!

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it -30 Vote: I do not like it

    .

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

      The contest is still running.

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

        In last 2 minutes hardly anyone will benefit from this comment.

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

          Doesn't mean you should be discussing problems and solutions before the contest has finished.

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

      But i try to solve it greedy why is this wrong ? https://pastebin.com/AbG3BwLX

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

        You're missing i <= j <= k

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

          Xd": ok that's dp , i'll hang a rope and suicide

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

            No No. Don't do that !! There is lot more contests to come. This is not the last contest of CodeForces. And also DP problems will come too.

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

    Did we have to print answer modulo 1^9+7 or something for Problem B? My submission kept failing.

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

Wow, in D, type 1 of relationship in statement corresponds to type 0 in input. Nice.

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

    also the structure is not a tree but a forest and "...An object is considered to be neither a part of itself nor a special case of itself". That caused me 2 WAs :(

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

How to solve E?

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

How to solve C?

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

Hack for B?

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

    Overflow:

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

    I hacked with this 1 1000000000 1000000000 1000000000 -1000000000

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

    min or max value of result -3e18 or 3e18 wtf

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

    3 -2 3 -2 1 2 1

    Answer: 2

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

Will dp[len][mask][base] for smaller length, and fixing the first digit that differs work in E?

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

TC4 for C? Does standard tree dp not work?

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

I think I spent around 45 minutes for understand D task, and maybe I didn't understand it correct :D

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

    Yes, "object", "special case", "part" all these terms are very unintuitive and it was very difficult to reason anything about this. I tried for 5 minutes and for the sake of my sanity I decided to let go this problem even if it later turns out to be very easy :P

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

Wow, problem D was so beatiful, understanding complicated statement and dealing with stupid corner cases (forest + in query of type 2 if v is ancestor of u then NO), such fun

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

    ah, it can be forest. Beautiful. Wonderful. So I guess that's why I got WA 9.

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

    How is it possible to get "in query of type 2 if v is ancestor of u then NO" from the statement? I don't think it follows from "An object is considered to be neither a part of itself nor a special case of itself." sentence. Why a special case of object is object? It looks more like isinstance vs type in python :)

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

      This is clear (but not easy to observe), you simply have no rule to infer that B is a part of A if A is a special case of B.

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

the best part of the contest were the problem statements. any potterhead there?

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

Am I right in thinking B, C and E are all DP or DP variants? I got sick of coding C and was still coding E when time ran out, but I'm pretty sure B is a linear DP, C is a DP on trees and E is a recursion which pre-processes cases such as the number of all magic numbers smaller than bk so sort-of DP-like?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    .

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

      It's not that I don't know that. I solved B in about 20 minutes. You were discussing the solution to problem B with another user 4 minutes before the contest was over.

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

    I honestly felt the difficult was A<B<E<D<C. Both E and D are well known problems and E takes less time to code while D is so difficult to understand with so unusual choices for terms and input conditions. In the case of C, maybe I'm approaching it wrong but I couldn't get the problem state in any clearer manner than 4 parameters (2 to specify sub-tree, number of high security, can build high security) with several end conditions.

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

      Actually, your formulation of the Problem C is almost perfect — it can be solved with dp[current node][number-of-special-nodes-left][is-neighborhood-of-special][is-neighborhood-of-node-with-whose-number-higher-than-special].

      After defining the table, you can fill it with knapsack inside recursion.

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

How did you guys solve the Problem E?

I approached it with DP but it turned out in random testing that dp solution runs slow(about 8 seconds for 10^5 test cases).

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

    If you're at state "I can use every number from now because I guaranteed current number is smaller than R", then you have nothing to do with R so you can just use precalculated values for every base.

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

    Precompute the following values: dp[base][length][mask] = number of combinations of the digits 0 to base-1. The binary representation of mask determines, which digit should appear odd and which even times.

    Then you can define a function f(base, x), which returns the number of numbers <= x, with each digit appearing an even time. Then the answer is f(r) - f(l-1).

    To implement f:

    • Convert x to base base.
    • iterate over all possible lengths of the numbers
    • if the length is stricktly smaller then the length of x, the answer is sum(dp[base][length-1][1<<digit] for 1 <= digit < base).
    • and if the length is equal to the length of x, you need to iterate over the digits of x, keep the mask and build similar sums.
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried just like that(even for the precomputation parts!) but it ran 8sec on my computer given this dataset(generator):

      from random import randint
      
      n = int(1e5)
      
      print n
      
      for _ in range(n):
          b = randint(2, 10)
          x, y = sorted([randint(1, int(1e18)), randint(1, int(1e18))])
          print b, x, y
      
      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 5   Vote: I like it 0 Vote: I do not like it

        I think you made some mistake somewhere. The precomputation part takes no time at all on my laptop. And computing f(base, x) has runtime log(x). So this should be fast enough for n = 10^5. Pretests took 249ms.

        edit: accepted with 421ms.

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

          Thanks, I found the BUG! it was frequent memset. I also made it work by fine-tuning memset calls(sadly, though the contest is over).

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

            How did you submit? System is not letting me submit

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

              I didn't but I just tested with my generator(see above).

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

How to Solve B?

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

    Yes, it is also interesting for me (

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

    Fix the position of q. Then p matches with max(input[1..pos_q]) and r matches with max(input[pos_q...n]). Both maxes can be calculated in O(1) thanks to easy precomputations.

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

      i spent almost one and half hours but couldn't and after seeing this i realize that i know nothing (:

      great solution!

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

    I figure this is much much simpler than DP:

    	ll bestp = -INF;
    	ll bestpq = -INF;
    	ll bestpqr = -INF;
    
    	for (int i = 0; i < n; i++) {
    		bestp = max(bestp, p * values[i]);
    		bestpq = max(bestpq, bestp + q * values[i]);
    		bestpqr = max(bestpqr, bestpq + r * values[i]);
    	}
    
    	cout << bestpqr << endl;
    
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +73 Vote: I do not like it

      This is, my boy, called DP solution.

      Btw, one should take care and set INF to at least 3e18, not to 1e18 as I did.

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

        Hello, I find it quite hard to understand this solution and how to come up with it. I see everyone mentioning DP, but I have no knowledge about it, could you give me some source for researching this type of algorithms?

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

          Google "Dynamic programming"

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

      can you please explain how it works correctly?

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

        So first we want to find the best if we just choose p, which is bestp. We can also choose to use the current one for q, which is bestpq, and it builds off of everything before us (stored in bestp) so we can maintain if it is the best over time. We do the same thing for bestpqr which is our answer.

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

D is just LCA and recording the relations between the query nodes and LCA right? I kept getting WA on test 5, found bug, then got compile error in the last 5 second... (anyone know if that's the right idea though?)

Also, how to solve C + E?

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

    You can solve C with next DP states DP[ root of subtree] [ amount of highest elements] [ value of current element ( smaller than k, equal to k, bigger than k ].

    For E I think it is also some easy DP, I think it is called DP on Digts — but I didn't try to write code :)

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

      Can you elaborate how we choose the amount of highest elements for the child? I got tripped up there.

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

        you can just fix the number of special elements in subtree of children = x, and number of special elements we already had before in other subtrees of node = y, update states with x + y

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

        You can run another DP, something like amount of ways to choose i highest elements in subtrees of first j childs. And with third dimension in previous post (value of current element), you exactly know what values can be in children ( I think if value of current node equal to k than children must have that state smaller than k, it value of current node smaller than k, than children can have any value, and if it is bigger than k, children must be smaller than k or bigger not equal).

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

Reducing to graph reachability is wrong in D?

Btw, is E really easier than D. For D at least I still have some idea, but for E my mind is completely draw a blank.

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

    E is just well-known DP on digits.

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

      But with large b, the naive dp on digit will work in O(q * 2b * logba), which is not fast enough. So I think there must be some other observation here.

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

        Just precalc dp[B][l][mask] = number of numbers in base B, with len l that have mask of digits mask. Now you can answer fast

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

        Precompute first so you can remove 2b from the complexity

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

        I don't have 2b factor even in preprocessing. I just keep number of digits with odd number of occurences (and I preprocess it).

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

        You can do it for each base

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

    At least, E's statement is much easier to understand than D's.

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

In D : v is not a special case of v if u is a special case of v , v is not a special case of u

just thought about these two in the last 5 minutes where there was no time :(

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

Hack Case for B ?

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

    For example if somebody set the final answer as 0 then update it in O(n) process then when there have some cases like

    4 12 14 16

    -1000000000 -1000000000 -1000000000 -1000000000

    then he will output 0 instead of correct answer

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

In problem d we have two rooted forests.

forest 1 and forest 2.

For queries of type 1 just check if vertex 1 is ancestor of vertex 2 in the forest (using the dfs in and out tree).

For queries of type 2 I think the following works: For each vertex let let F(v) be the root of its component in forest 1. Add all edges that v has in forest 2 to F(v).

now do the dfs in the modified graph and check:

vertex 2 is son of F(v1)

vertex 2 is equal to F(v1) and there is a loop at F(v1)

If none of these happens print No.

I forgot to check the loop thing, I think thats why I failed pretest.

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

    How did you solve C?

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

      let Rs[x][i] be the number of ways to color the subtree of vertex x such that there are i max security vaults and the node x has a security less than k.

      Let Ry[x][i] be the same but such that node x has max security and let Tb[x][i] be the same but such that node x has security larger than k.

      You can then obtain the values of R[x][i] from the values of R[y][i] such that y is a son of x.

      So it is like a dynamic programming on the tree.

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

Best Problems i ever had...

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

Am I the only one who skipped i<=j<=k condition in B ??? So stupid of me :(

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

I solved E as even number of times means equal number of times and realized it's wrong while testing the samples :(

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

    I think if it was each of the digits from 0 to b - 1 appears even number of times instead of all the digits from 0 to b - 1 appear even number of times, it would've been less confusing.

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

    Try this one 1 -430770061 -822021323 -993560291 674829238 ans is -1515903789120273650

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

how to solve problem E?

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

Shit! No large pretest for E. "calc(int b, int l)" still pass pretest!

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

The time limit for problem C seems very strict to me. I had to somehow squeeze my solution by making stupid optimizations and still think it will get TLEd on main tests.

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

Can anyone please explain the solution idea for problem C and D? Thanks in advance. During the contest time I thought that D can be solved using LCA and some query on it. But I am not sure.

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

    The solution for D is indeed LCA. Let's say each edge is either type 'a' or type 'b' (because the problem changes the notation mid-problem anyway).

    • One of the queries is asking if u is an ancestor of v & if the path between the two is composed only of type 'a'.

    • The other query is to find the LCA of u and v which we denote 'p'. If p exists & the path from u to p is only of type 'a' & the path from v to p is only of type 'b'. (I might have mixed up the symbols)

    Along with the parent sparse table and height we use for LCA, we also use a boolean sparse table with the recursion reachA[x][d] = reachA[x][d-1]&&reachA[parent[x][d-1]][d-1] or similar to see if the path is with only type 'a' or type 'b'.

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

    UPD: Ok, my D failed. Maybe you don't want to listen to me about it :D

    Problem D: You were right. Let sc[i] be the uppermost (the one with lowest level) node which can be reached from i by following only special case edges and part[i] be the uppermost node which can be reached from i by following only part edges. Calculating these two values is a trivial DP/DFS. Now type 1 query simply asks if U is an ancestor of V and sc[V] is ancestor of U. Type 2 query asks if U and V are in the same tree (if so, let's say L is their LCA) and both sc[U] and part[V] are ancestors of L.

    Problem C: Okay, I am pretty sure I have overkilled this problem. Anyway, there are three types of labels — those less than K, those equal to K and those greater than K. Labels from the same type are indistinguishable. I use dp1[node][typeOfParent][numberOfHighlySecureVerticesInTheSubtreeOfNode].

    Now, there might be an easier way to calculate the state which I don't know so what I do in such cases is use a second dp, dp2[node][currentChildOfNode][typeOfParent][numberOfHighlySecureVerticesInTheSubtreeOfNode] which works by looping over node's children and assigning some number of highly-secured vertices for each of their subtrees.

    So dp2[node][idx][type][cnt] is equal to the sum of dp1[v[node][idx]][type][i] * dp2[node][idx + 1][type][cnt - i] for i from 0 to cnt. v[node][idx] is the idx - th child of node. The value of dp1[node][type][cnt] is simply dp2[node][0][type][cnt]. To get the value of dp1[node][type][cnt], we will first need to choose the type of node. After that, we can easily obtain its value from dp2[node][0][type][cnt] or dp2[node][0][type][cnt - 1], depending on which type we have chosen.

    Note that in the second dp the number of pairs [node][currentChildOfNode] is O(N) — it's just the number of edges.

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

      For fixed i and j, you can combine your dp1[i][j][k] into coefficients of a polynomial, of degree x. Then dp[i][j] is going to be a product of the corresponding polynomials of the children of i. (You have to fiddle around with exactly which polynomials to multiply — basically translate the rules about neighbors of highly-secure vertices).

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

Type 1 relation means that the child object is like a special case of the parent object. Type 2 relation means that the second object is always a part of the first object and all its special cases.

If typei = 0, this implies that the object i is a special case of object parenti. If typei = 1, this implies that the object i is a part of object parenti.

Triggered.

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

    This takes effort.

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

    Very weird statement. Nice problem, but a better care with the statement would have made a great difference.

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

Could anybody please explain me why my solution to B TLEd on test 66?

Link to submission

UPD: Nevermind, I initialized my dp array with -1 while -1 is a possible answer. :(

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

System test is over, should we be able to submit or is there bug?

edit: also cannot view other people submissions

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

GOOD for fast system testing :)

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

CF Format hit me hard today. Made the silliest of bugs on B, didn't get hacked throughout on it, solved a much more harder C, and now I have to deal with ending below some people who got many hacks.

So much related to luck is CF format, isin't it ?

Only if I could change a single character on my B and resubmit.

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

Not able to submit even after tests ? Is there some sort of bug ?

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

2nd problem was good :)

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

What is the solution for this test case for problem D?

5
-1 -1
1 0
1 0
2 1
2 0
4
2 1 4
2 2 4
2 3 4
2 5 4
»
3 months ago, # |
  Vote: I like it +18 Vote: I do not like it

When can I submit??

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

enable upsolving?

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

For B, what is problem with this solution If p,q,r is negative, multiply it by smallest ai. Else, multiply it with biggest ai.

Sum those 3 and print.

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

    You have to maintain order of A[i], A[j], A[k] such that i <= j <= k. I think you are sorting your array . This was not allowed

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

    1 <= i <= j <= k <= N.If p is positive and q is negative.Then, that condition(i<=j<=k) won't be satisfied in your algorithm.

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

      Lol. Thanks, I totally forgot that order i,j,k matters ( i is for p and so on..)

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

    For test case 3 p = -1 q = -1 r = 10 A = {1 1 0} Answer = 8

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

someone please tell me how to solve problem B. If u can give correctness of ur solution will be very helpful

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

    Let f[i] = a[i] * p and g[i] = a[i] * r. Now let pref[i] = min(f[1], ..., f[i]) and suf[i] = max(g[i], ..., g[n]). The answer is obviously pref[i] + a[i] * q + suf[i] for some i.

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

    Traverse the array, find the maximum value of p*A[i] for each prefix i ie., Prefix_A[i] = max(prefix_A[i-1],p*A[i]).This can be done in O(N).Now,find the maximum value of p*A[i]+q*B[j] for each prefix j ie., Prefix_B[j] = max(Prefix_B[j-1],B[j]+Prefix_A[j]) — O(N).At last find the maximum value for each prefix k of p*A[i]+q*A[j]+r*A[k] using this Prefix_B array and take the maximum of them ie., Ans = max( C[k] + Prefix_B[k] , Ans ).

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

Ratings are updated without deleting cheaters now. They will be removed and the ratings will be recalculated, they may slightly change.

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

    Sir, When will you enable upsolving?

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

    Why isn't other's solutions accessible?

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

    Have they been recalculated yet?

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

    The code of these two accounts in many games is similar or even the same: 770780079 pb0207

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

      It seems only 770780079 had his code skipped, shouldn't pb0207 get skipped as well? Is this a flaw of anti-cheat program?

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

        Perhaps this is a flaw in the anti-cheating software, but it seems that the code submitted early should be counted as AC. Because after locking the code, you can view the code of others.

        And for example, replace the variable name, add useless function, add useless comments, add a black line. Will make anti-cheating procedures can not be detected.Their code is too similar, and I also participated in those rounds, I do not think this coincidence caused by the coding habits .

        854C:77,pb

        861C:77,pb

        862D:77,pb

        862C:77,pb

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

          It should be that both users are disqualified — they shared code, and the "alternate account to look at solutions after lock" is clearly not what is happening. It is definitely flaw of the system. By the way, you are great detective.

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

what is pretest 4 of problem C??

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

How to solve problem B. Good problem in my opinion.

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

What is the test 75 of problem B. Got Wrong answer on test 75 [main tests] → 30680748 -_-

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

Literally my worst round ever.

  • A: Map string to int, done
  • B: Just iterate over the array from left to right, and from right to left. Unfortunately, I set the minimum answer to  - 1018 and end up getting hacked.
  • C: Tree DP takes some time to implement, but not hard.
  • D: Realizes that it's just LCA, incorrectly handles the statement "An object is considered to be neither a part of itself nor a special case of itself."
  • E: Obviously digit DP, but I have never done digit DP very quickly. Spends 1,5 hours trying to debug and submits with a couple minutes left. After the contest ends, I realize that I did not properly handle the case where r = 1018.

--> rating gain from MemSQL Round 1 completely erased :D

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

http://codeforces.com/contest/855/submission/30682143 http://codeforces.com/contest/855/submission/30686094 — what a "tricky" solutions to F (of people from 1st and 4th places). Did setters spend at least 5 minutes on tests to this problem?

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

    Look at solution, I see related problem.

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

    The code of Shik without

    #pragma GCC optimize("Ofast,no-stack-protector")

    #pragma GCC target("avx,tune=native")

    receives TL30.

    ¯\_(ツ)_/¯

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

    Oh, common. This is SSE optimized solution.

    How many setters even know about SSE/AVX? I doubt authors simple solution works >2x of TL.

    SSE speed up anta's solution >4x times: 30682143 30690004

    Guys, it's 2017, it's time to read something about vectorization. It's more useful on CF than learing suffix tree and other complex useless stuff.

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

      http://codeforces.com/contest/855/submission/30686153

      Without any vectorization and #pragmas.

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

      I put these in the headers of some of my previous codes and there's a significant speed up. So there are no extra things I have to worry about? I can just put it in my template and give my poorly-optimized codes a boost?

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

      Can you tell a bit more about what does SSE/AVX do?

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

        Regular instructions (without AVX/SSE) are executed by the processor one at a time, while AVX/SSE instructions use special registers capable of holding more bits than a regular register, for instance, there are processors that support AVX-256, meaning that it provides instructions for executing operations (such as loading, storing, adding...) on 256 bits (8 integers/floats or 4 doubles/longs...) at once. It is basically a form of instruction-level parallelism (SIMD).

        You can ask the compiler for trying to compile your code into those special instructions, it will be done when possible, for exemple, if you're dealing with arrays, loops will take bigger steps and execute operations on more than one element at a time, that can cause speedups of 2, 4 or even 8 times. You could also, instead of asking the compiler, use those instructions yourself with high level functions, but the problem is that you would have to know which version of AVX/SSE the target processor supports.

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

          Is there any reason to not include above pragma's in your code by default?

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

            I don't think so. Apparently what made a big difference was:

            #pragma GCC optimize ("O3")
            #pragma GCC target ("sse4")
            

            The compiler already uses SSE (< 4) instructions with the flag O3. And SSE4 has been around for quite some time, so it will probably work for most online judges. I'm not sure if the compiler still uses SSE4 if the processor doesn't support it, my guess is that it ignores the pragma (I could't find an older processor to test it).

            Analysing the differences in the assembly between 30682143 and 30690004, there seems to be very little change except for a few instrutions that get the same result in less steps, those new instructions are some of the ones introduced in SSE4. The speedup in that case is 4x (very high) because those faster instructions are in the middle of the two innermost loops! Which means that including the pragmas in every code will probably not make that big of a difference in the execution time.

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

              So what if I have both the sse and avx header? There's no problems to worry about?

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

                Well... There's usually some loss of efficiency when using both SSE and AVX, but apparently GCC takes precautions when that's the case. So I guess that using both pragmas isn't a problem, but I'm not sure about how much it improves the performance, it really depends on the program you're compiling.

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

    That's so sad I haven't read the statement of problem F during the contest. It is very obvious with such limits that it can be solved by O(NQ) =(

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

Can someone recommend some DP on tree problems like C, where you compute the DP states inside the dfs and stuff like that? Thanks!

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

When will editorial be published?

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

I was looking at someone's submission and I found this block of code. Can someone explain what the ONLINE_JUDGE flag is?

#ifndef ONLINE_JUDGE
    FILE *stream;
    freopen_s(&stream, "input.txt", "r", stdin);
    // freopen_s(&stream, "output.txt", "w", stdout);
#endif
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    ONLINE_JUDGE is a flag used by most OJ's, basically that if the flag not set #ifndef, enter that bloc of code which change the input/output stream to those files.

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

Editorial right after the contest can be the best gift.

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

What happened to ratings ? :(

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

Any idea why the rating changes were removed?

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

    They are back already, i believe it is something like people cheating, so they invalidate person's contest and recalculate the ratings, if you observe, some people had ratings increased by 1 or 2

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

My little question about problem D:

If object i is a special case of object j and object j is a part of object k. So is object i a part of object k?

It's really bad to find out that you got FST on D because you remembered to examine one more case.

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

    no, this is like if you have i is a monster truck wheel, j is a wheel, k is a car.

    So all car will have wheel but that doesn't mean it has monster wheel

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

Can anyone please help me find the reason for WA in test 5 in the B question...Here is the link to my solution...http://codeforces.com/contest/855/submission/30981196