bharat.khanna.cse14's blog

By bharat.khanna.cse14, 7 years 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 vintage_Vlad_Makeev 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. jqdai0815

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!

| Write comment?
»
7 years ago, # |
Rev. 2   Vote: I like it +49 Vote: I do not like it

7 problems in 2 hours?!

UPD: Contest extended.

  • »
    »
    7 years 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?

    • »
      »
      »
      7 years 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.

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

        Why so many downvotes? I just said my opinion!

        • »
          »
          »
          »
          »
          7 years 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?)_

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

          ignore these shit tards my friend.

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

    1

»
7 years 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. :)

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

    YEEEEEEEEEEEEEESSSSSSSSSS!!!

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

    Codefest'17 is excited to present a mathematical programming contest — Mathmania. It will bring a delectable collection of problems which will be an absolute delight for all the mathematics geeks. Cash prizes worth INR 50,000.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it -26 Vote: I do not like it

      Thats nice to hear, because Maths is good for health.

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

        It's bad for the health of my rating though

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

          Yeah same here brother, I have been trying since a year to reach that dark blue area of expert.

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

        because Maths is good for health.

        You look healthy,I think.(just a joke

»
7 years 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!

  • »
    »
    7 years 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.

»
7 years 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?

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years 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

      • »
        »
        »
        »
        7 years 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.

        • »
          »
          »
          »
          »
          7 years 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

          • »
            »
            »
            »
            »
            »
            7 years 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.

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

Is it rated?

  • »
    »
    7 years 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.

»
7 years 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

  • »
    »
    7 years 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).

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

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

    And it must be XD.

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

    well every one cant have high rating ...

    • »
      »
      »
      7 years 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.

      • »
        »
        »
        »
        7 years 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

  • »
    »
    7 years 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!!!!!!!

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

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

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

contest prepared by IITians.

»
7 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Is this contest rated?

  • »
    »
    7 years 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...

    • »
      »
      »
      7 years 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".

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

»
7 years 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

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

Sorry!!!

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

»
7 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Where will this contest be held?

»
7 years 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?

»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Scoring?

»
7 years ago, # |
  Vote: I like it -46 Vote: I do not like it

Is it rated ?

»
7 years ago, # |
  Vote: I like it -36 Vote: I do not like it

I know that all of the problems are about religion

»
7 years ago, # |
  Vote: I like it +54 Vote: I do not like it

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

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

    In B, Did you applied DP ?

    It smells like DP.

    • »
      »
      »
      7 years 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.

      • »
        »
        »
        »
        7 years 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?

        • »
          »
          »
          »
          »
          7 years 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 egor.okhterov's above.

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

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

        • »
          »
          »
          »
          »
          7 years 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;
          
          • »
            »
            »
            »
            »
            »
            7 years 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..

          • »
            »
            »
            »
            »
            »
            7 years 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.

            • »
              »
              »
              »
              »
              »
              »
              7 years 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]; 
              
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I think prefix sums are a form of dp.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years 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.

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

        Hello egor.okhterov,

        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?

        • »
          »
          »
          »
          »
          7 years 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.

»
7 years 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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

shit > Problem D

»
7 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Waiting for problem B massacre during system testing :)

»
7 years 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

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

    Please ask these things after the contest

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

  • »
    »
    7 years 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 :/

    • »
      »
      »
      7 years 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?

      • »
        »
        »
        »
        7 years 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.

»
7 years 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

»
7 years 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!!!!

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

    .

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

      The contest is still running.

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

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

        • »
          »
          »
          »
          »
          7 years 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.

    • »
      »
      »
      7 years 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

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

        You're missing i <= j <= k

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

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

          • »
            »
            »
            »
            »
            »
            7 years 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.

  • »
    »
    7 years 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.

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

  • »
    »
    7 years 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 :(

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

How to solve C?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack for B?

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

    Overflow:

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

    I hacked with this 1 1000000000 1000000000 1000000000 -1000000000

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

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

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

    3 -2 3 -2 1 2 1

    Answer: 2

»
7 years 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?

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

    I approached just like yours(with some hardcoded precomputations) but it was too slow.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

TC4 for C? Does standard tree dp not work?

»
7 years 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

  • »
    »
    7 years 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

»
7 years 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

  • »
    »
    7 years 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.

  • »
    »
    7 years 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 :)

    • »
      »
      »
      7 years 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.

»
7 years 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?

»
7 years 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?

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

    .

    • »
      »
      »
      7 years 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.

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years 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.

»
7 years 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).

  • »
    »
    7 years 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.

  • »
    »
    7 years 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.
    • »
      »
      »
      7 years 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
      
      • »
        »
        »
        »
        7 years 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.

        • »
          »
          »
          »
          »
          7 years 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).

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

            How did you submit? System is not letting me submit

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

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

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to Solve B?

  • »
    »
    7 years 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.

  • »
    »
    7 years 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;
    
    • »
      »
      »
      7 years 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.

      • »
        »
        »
        »
        7 years 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?

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

          Google "Dynamic programming"

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

      can you please explain how it works correctly?

      • »
        »
        »
        »
        7 years 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.

»
7 years 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?

  • »
    »
    7 years 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 :)

    • »
      »
      »
      7 years 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.

      • »
        »
        »
        »
        7 years 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

      • »
        »
        »
        »
        7 years 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).

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

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

    E is just well-known DP on digits.

    • »
      »
      »
      7 years 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.

      • »
        »
        »
        »
        7 years 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

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

        Precompute first so you can remove 2b from the complexity

      • »
        »
        »
        »
        7 years 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).

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

        You can do it for each base

  • »
    »
    7 years 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.

»
7 years 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 :(

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack Case for B ?

  • »
    »
    7 years 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

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

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

    How did you solve C?

    • »
      »
      »
      7 years 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.

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Best Problems i ever had...

»
7 years 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 :(

»
7 years 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 :(

  • »
    »
    7 years 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.

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

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

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

how to solve problem E?

»
7 years 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!

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

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

  • »
    »
    7 years 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'.

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years 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).

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

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

    This takes effort.

  • »
    »
    7 years 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.

»
7 years 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. :(

»
7 years 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

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

»
7 years 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 ?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

2nd problem was good :)

»
7 years 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
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

When can I submit??

»
7 years ago, # |
  Vote: I like it +49 Vote: I do not like it

enable upsolving?

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

  • »
    »
    7 years 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

  • »
    »
    7 years 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.

    • »
      »
      »
      7 years 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..)

  • »
    »
    7 years 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

»
7 years 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

  • »
    »
    7 years 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.

  • »
    »
    7 years 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 ).

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

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

    Sir, When will you enable upsolving?

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

    Why isn't other's solutions accessible?

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

    Have they been recalculated yet?

  • »
    »
    7 years 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

    • »
      »
      »
      7 years 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?

      • »
        »
        »
        »
        7 years 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

        • »
          »
          »
          »
          »
          7 years 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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is pretest 4 of problem C??

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

»
7 years 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

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

http://mirror.codeforces.com/contest/855/submission/30682143 http://mirror.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?

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

    Look at solution, I see related problem.

  • »
    »
    7 years 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.

    ¯\_(ツ)_/¯

  • »
    »
    7 years 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.

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

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

      Without any vectorization and #pragmas.

    • »
      »
      »
      7 years 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?

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

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

      • »
        »
        »
        »
        7 years 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.

        • »
          »
          »
          »
          »
          7 years 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?

          • »
            »
            »
            »
            »
            »
            7 years 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.

            • »
              »
              »
              »
              »
              »
              »
              7 years 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?

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years 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.

  • »
    »
    7 years 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) =(

»
7 years 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!

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

When will editorial be published?

»
7 years 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
  • »
    »
    7 years 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.

»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Editorial right after the contest can be the best gift.

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

What happened to ratings ? :(

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

Any idea why the rating changes were removed?

  • »
    »
    7 years 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

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

  • »
    »
    7 years 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