Tommyr7's blog

By Tommyr7, history, 7 years ago, In English

Hi, Codeforces!

I'm quite excited to invite you to Codeforces Round #439 (Div. 2) which takes place at 16:35 MSK on 6 October and lasts for two hours.

One of the five problems is created by quailty, and the others are created by me. This is our first round here.

The round couldn't have been realized without efforts of KAN and vintage_Vlad_Makeev. Besides, I also want to say thanks to our testers: cyand1317, visitWorld, Nisiyama_Suzune, cdkrot and 300iq. Thanks for your help to the contest. Also, thanks to MikeMirzayanov with the fantastic Codeforces and Polygon platforms.

The contest will consist of five problems and it is rated for Div. 2 contestants. The same as before, Div. 1 contestants can take part out of competition.

The problems will feature... Well, let's wait and see for another time ;) As per Codeforces tradition, moderate length text and no spoilers about the actual plot.

I hope you can have fun during the contest. Good luck and have fun, wish you high rating!

The scoring distribution will be announced later.

See you tomorrow!

UPD1 : The scoring distribution is 500-1000-1500-2250-2500.

UPD2 : The contest is over. The editorial is available.

UPD3 : Congratulations to top five coders!

Division 2 :

  1. 1heart2plans (solved all problems!)
  2. fateice_ak_ioi
  3. esfeng738
  4. XZA
  5. T404

Division 1 + Division 2 :

  1. 1heart2plans (solved all problems!)
  2. unused
  3. fateice_ak_ioi
  4. nuip
  5. chemthan

Have fun! See you next time! (Let's wait and see...)

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

| Write comment?
»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).

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

    The E's data has some weak,because many people violence passed,but if Op 1 is 50000 and op 3 is 50000 many people will be TLE.

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

      Well... It's my issue... In fact, the generator for div2. E isn't easy to code... I added 20 tests after randomly getting the ractangles... and I didn't consider this situation... Maybe I will do better next time... Thanks for pointing out!

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

Tommyr7's round, must be very nice to perticipate.

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

Another chinese round. Hope for short problem statements.

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

Not only Chinese round,but Shanghai Round as well.It must be a fantastic one as the ones written by cyand1317!

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

WOW Shanghai Round OvO

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

zici!

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

%%%%Q神

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

Wow, another round with special starting time. I can't stop craving those thought-provoking problems.

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

Very good! Hope the statement will be short.

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

Nope

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

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).

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

I did terribly today and cannot wait until tomorrow to try to restore my confidence.

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

gl hf every one

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

good luck!

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

Hope this contest problems also have a short statements like previous. Wish everybody luck! YA!

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

Its not.

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

    If there written "Codeforces Round #***", it means that it is rated. But not always, for example.

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

      Right. In addition, "Codeforces Round #***" can be unrated if there occurs any unexpected technical problem (though those contests are declared as rated, later they're declared as unrated in those cases).

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

Wish that this contest announcement will be, as short as, statement)

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

Yeah, This contest will held on my Dad's birthday.The bad thing that I will be doing this contest during my family сelebrating dad's birthday(((

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

    I really think you should celebrate your dad's birthday in case contest clashes with the party time :)

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

Finally came to a Chinese Round!Fantastic! Zici Tommyr7's first round. And ORZ Giant Red Q ! I think at Tommyr7's and quailty's level , it's not difficult at all to prepare for Div1!

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

    Yes, and they (classified information) with (classified information).

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

    Well, it's our first round. So I think it more proper to prepare for just one Div. 2 round.

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

      proper uh... how to understand this words ? my English is not so good sorry ... proper means suit? maybe... QAQ

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

Chinese Round,fighting!

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

Congratulations....hope your 1st contest will be very interesting and expecting high rating :)

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

So before every contest, I get an email announcement for the upcoming contest, and every time it states that the contest has an unusual start time.

Out of curiosity when is the usual start time?

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

For quailty hit call(escape

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

If you ask me zici not zici, I'm zici

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

EMPTY

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

As someone who is about to retire, I hope to have a happy ending.Come on!

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

quailty, I hope the problem's quality is very good.

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

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).

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

I wonder how Tommyr7 became rating ~2300 so fast (3-4 months) from rating 1800 (with many participation)...

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

    In fact... I can't performance well in Div. 2 contests and I even don't know why...

    Always FST on div2AB may be one of the reasons...

    You can see that I fst problem B yesterday again... which makes me very upset...

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

Let's Hack it!!!!

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

Someone tell me how to solve C??

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

    excuse me?

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

    Let me bring my crystal ball... Oohhhh, I can't find it. Must have missed it on the field some day.

    Well, now you're gonna need to read the problem first.

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

    You can do it greedily. Just sort the array and try all the numbers from smallest to largest.

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

    You can use Brute force. Just O(n^2). n is less than 10000. So brute force can solve it.

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

      But time limit is only 439 miliseconds. And implementation is pretty heavy so the program can be slow. How can you deal with it?

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

        You can use fastIO, such as read() or fread(). :)

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

      The brute force solution seems to be O(n^2), but is actually O(n*log(n)), so the solution can easily pass all tests.

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

    I solved it with Convex Hull on linked list! :)

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

Yay! I don't have to feed the cows this morning. Let's have fun in this contest :) !!!

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

Today's round ID is 869, which is one of the substring of E869120. I'm lucky that I can participate.

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

    The next contest which's ID will be in your username as substring will be 912. After some more contests :)

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

the start round doesn't suit me, i've to run from college to home quickly and the contest has started 10 minutes :)

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

It seems that chinese round is difficult as usual.

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

    That's why people shouldn't vote up the announcement before they read problems.

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

I am not being able to open any solution for hacks. [Locked solutions]

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

Awesome Chinese names got me!! :-P Instead of "Koyomi", I wrote "Kayomi" and got pretests passed. So, I locked for hacking and now I realized that I made a mistake!! Worst feeling when you know your submission is going to fail in system testing and you cant do anything :-P

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

    dont worry...have hope...it wont fail :p

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

    The answer is always Karen so don't worry and you'll be accepted

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

      Damn...that is great! Totally missed it.

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

        I realized that when I tried to hack this code:

        int main() { printf("Karen\n"); }

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

          It's not always :)

          Consider the case: 2 4 1 5 4

          No of pairs: 3 (1,1) (2,1) (2,2)

          Luck wasn't in my side, and contest got over before i could hack a submission.

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

      Why is it always Karen? Sorry I'm kind of slow on these things.

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

        It's easy to see, xor(X,Y) = xor(Y,X) right ? So if (X,Y) is a valid pair, (Y,X) would be as well.

        As you can see the answer comes in pairs, that's why it's always even.

        Don't forget that xor(X,X) = 0 and 0 is not allowed in the problem so you will never count this one.

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

    I guess the names are Japanese as the characters from the problems are a part of an anime known as the Monogatari Series.

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

      Yes, they're Japanese names. Though Kanbaru didn't appear in problems XD

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

502 Bad Gateway

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

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

C is savage :/

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

    Why ? As I am new to the world of CP. Why Chinese contests are not good ? :P

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

      There is a difference between Hard and good :/

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

since when codeforces started allowing Div2 participants in Div1 contests.....???

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

How to solve A ? [ What is the hack case for A as I solved it using O(n * n)]

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

    ans for A is always "Karen".

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

    The answer will always be karen because the number of pairs will be even always. Suppose, for pair (1,2) the answer(xor of both numbers) exists in array, then obviously for (2,1) answer will also exist. Hence for x (x1,x2) number of pairs there are other x(x2,x1) pairs. Hence 2x pairs in total. so the answer will be karen.

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

I am not able to see other solution for hacking after locking my solution. Also my score shows 0 in my room. Why is this happening? :/

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

Problem descriptions were not that long. Thank you!

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

It was a high quality round.

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

what should be the output for

1 1048576 1048575

in A ? update- it was my mistake .

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

      I tried to hack one solution which was giving Koyomi but ended up with unsuccessful hacking attempt.

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

        bool vis[2000200]; will get Runtime Error, but int vis[2000200]; wiil not. I tried to hack the second twice but both failed! It is really strange…

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

    Karen?

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

    Are there any test cases that don't give Karen?

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

    It is always "Karen"

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

Math, Math and more Math.

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

I did hashing on fenwick tree for problem E. Even though I did double hashing, I'm still crossing my fingers.

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

When you're < 30 seconds late from submitting a solution.......

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

Is there any alternate approach to E, mine is ->

I maintain a 2D BIT, where in every cell I store hash of set of rectangles that affected it. For query, I just check if hash of given two cells is same. Query as well as updating all elements inside rectangle while adding or deleting it takes O(log(n)2) time.

My hashing technique though is very naive, first I assign unique numbers to rectangles, now I maintain few functions like sum of numbers, sum of squares, xor of numbers, xor of squares in every cell. Comparing two cell then will require to compare these 4 numbers. Using lesser and better functions should also suffice.

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

A. Nice Hello World

B. Nice problem for Python

C. Nice problem for Python

D. Nice difficulty

E. Nice data structure

The difficulty distribution is 500-500-1500-3000-2000.

Please dynamic problem scoring.

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

Mathematic round

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

do the pretests of E contain big tst cases

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

In problem B one should check for 0!/0! case answer should be 1 .

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

How to solve C?

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

    Fix the number of edges between a-vertices and b-vertices. Let there be x of them. Choose x out of a possible a-nodes and x out of b possible b-nodes and connect them in x! ways. Do same for a-c and b-c pairs. Multiply all 3 values to get final answer.

    Code

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

      I don't get it :/. What do you mean by "Fix the number of edges between a-vertices and b-vertices" ? Can you explain with the example a={1,2} and b={1,2,3} ?

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

        x can range between 0 and min(a, b). In this case, x can be 0, 1 or 2.
        If x = 0, number of ways = C(a, 0) * C(b, 0) * 0!
        If x = 0, number of ways = C(a, 1) * C(b, 1) * 1!
        If x = 0, number of ways = C(a, 2) * C(b, 2) * 2!
        C(n, r) is number of ways of choosing r objects from n objects.

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

          C(a, 0) * C(b, 0) * 0!,
          C(a, 1) * C(b, 1) * 1!,
          C(a, 2) * C(b, 2) * 2!

          Sir, can you explain why you multiplied the expression with the factorial? 0!, 1!, 2!??? satyaki3794

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

            After you've chosen x values each from the two sets of nodes, you need to make x pairs from them. For the first a-node, you have x possible b-nodes to choose from. Make a pair. Now, for the 2nd a-node, you have x-1 possible b-nodes to choose from, and so on. Total ways is x!.

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

    Calculate F(a, b) independently for 3 pairs and multiply.

    if a <  = b, F(a, b) = F(a - 1, b) + F(a - 1, b - 1) * b

    Because, for 1st element of first set, if nothing is assigned in 2nd set, there are F(a - 1, b) ways left, and if 1st is assigned in b ways, F(a - 1, b - 1) ways are left.

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

      why not so:F(a-1,b-1)*a+F(a,b-1)

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

        The relation is symmetric, hence I mentioned a <  = b before it.

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

          But How are they independent of each other ???

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

            When you have joined a point in set 1, with a point in set 2, joining this point to any point in set 3 doesn't contradict any given conditions, hence you can treat them as independent.

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

swap(D,E)

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

I did not enjoy the difficulty this round. The difficulty was A, A, D, E, E. One small mistake on the first two problems can drop your rank by 500.

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

I've been tricked After I hacked someone's code,I saw this: #define int long long int

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

    That's cruel.

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

    Exactly this was something I faced in a previous round. From then, I always check ;)

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

      Yeah,I will check it from now on.I were so innocent...

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

    I use this, It save me from overflows :D

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

      but long long int is time consuming.

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

        Codeforces is not so strict with time limits :D until you are writing some sub-optimal solution in which case you need to edit this #define int long long

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

wanna cry, come to the solution of C in the last ten minutes but fail to submit it.

»
7 years ago, # |
Rev. 2   Vote: I like it +37 Vote: I do not like it
x[i]^y[i] Test 23 A

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

Answer of A is Always Karen ????

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

    Yah

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

    Yes. Because, if A^B = C then B^C = A and A^C = B both are true. When you find a pair A and B such that A^B = C and C is one of the numbers of your list, then it's guaranteed that you will find another pair looks like A^C (Which will give B) or B^C (Which will give A). So for one successful XOR another successful XOR is guaranteed!

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

    ordered pairs was the key word.

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

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).

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

Oh my god, I made an obvious mistake and I passed the pretest of problem A..... Farewell my rating.

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

using map in A gets TLE :(

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

    Solution was O(1) answer is always Karen :D

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

      Too lazy to think for problems which can be solved with brute force approach :p

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

        Same happened with me in B i just looped from a+1 to b without noticing constraints lost 50 points :(

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

    no it doesn't my submission

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

      but why it's with me:31069010

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

        It's giving TLE with [] operator but passing with find() but both are logarithmic in complexity .

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

          Using [] operator adds keys to the map(if it doesnt exist), thus making it too large for further operations. So find() runs fine but [] gives TLE. Made the exact same mistake !

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

            I had a small doubt, if [] is making keys then when it is called for the second time why doesn't it return true.

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

              Map stores key value pairs. Sure it adds new keys, but maps them to false value.

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

    Lol, never use a map just to map something to bool, you can always just use set in such case instead.

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

O(N^2*6) DP getting TLE in C but O(N^2) Pascal's trangle passing :( too strict time limit

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

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).

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

CodeForces runs 10^8 operations in 1 second? correct me

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

In problem C, it is Impossible to solve the problem in Java using O(N2) Dp. However the same solution, in c++ passes like a wonder.

Remember that I used my mind to come up with an idea for a good problem, I type the Code in Java, TLE on pretest #7. The same code I type in C++, AC 740 MS. So, U should also prefer a better language, not only use ur brain to solve problems.

I have been facing disappointments like these from time to time.

I'm just going to stop using Java anymore, because I feel a lack of respect towards it in the programming Community.

Some Proof :

C++

Java

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

how 2 solve E in 8 minutes like fatice did ?

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

    begin with E first read problem in 1 minute think for 2 minutes code BIT in 1 minute code others in 3 minutes submit code in 1 minute

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

    In fact, fatice ranked 1st in CNOI2017.

    He's really cool.

    /And I was shocked when I knew he took part in the round...lol

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

      That 's amazing !!! When I was in the game, I was shocked when I looked at the rankings. Now read his code, I think in this life I can hardly write such a simple and concise code. lol

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

Perfect contest time after a long week.

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

This contest is not showing up in my profile. Is there some time to wait before it is updated?

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

checking an element a1 in map like ma.find(a1)!=ma.end() passes all the testcases for A but checking like ma[a1]!=0 gets TLE. why??

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

    When you use the second option, an element with key a1 is inserted on the map, so the runtime will be slower since you gonna have more values in your map

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

      but time complexity is same for both the cases and also atmost 4*10^6 elements will be inserted.

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

Running on tc22 for 15 mins...Can someone explain why

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

why in problem A mp[] gives TL ,, okay it will insert more elements in the map but still the max size of the map should be 2000+2000+(2000*2000)=4004000 so the overall complexity should be n*n*log(4004000) and this should pass in one second!

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

The constraints given in problem A are wrong thats why my solution did not pass The constraints for xi and yi given are 1 — 2*1000000 whereas actually the constraints are 1-4*1000000. Please correct me if I am wrong.

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

    constrains is right but A^B may be more than 2*10^6

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

when the ratings will be updated? can't wait to become purple

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

Am I the only one who solved problem B by finding the repeating pattern of the last digits of b!/a! ?? This is my solution.

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

ratings?

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

What kind of joke it is to provide editorial of only 2 problems? :/

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

what is difference between finding in map and direct checking? ex. map<int,int>mp; mp.find(x)!=mp.end() and mp[x]!=0

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

    If you access a key using the indexing operator [] that is not currently a part of a map, then it automatically adds a key for you. This makes a really large map (up to 4000000) in this problem. You should use .find() or .at() for lookup.

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

Is there a good deterministic solution to E?

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

How to solve D?

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

My solution is hacked again. It's a sad story.T_T

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

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).

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

If 1e18*9 is not allowed by long long,then I could have hacked many solutions on B:D

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

Auto comment: topic has been updated by Tommyr7 (previous revision, new revision, compare).