mohammedehab2002's blog

By mohammedehab2002, 5 months ago, In English,

Hi!

I'm back with not one, not two, but three contests, although I have no promises about when to expect them....

The first of them, codeforces round #563, will take place on Jun/03/2019 17:05 (Moscow time). It's rated for the second division, but, as usual, first division participants can take part out of competition.

I'm the problemsetter of the round. I'd like to thank KAN for coordinating the round (and his patience .. try coordinating ~20 problems), arsijo for helping with the preparation, Um_nik, opukittpceno_hhr, Aleks5d, Rifai, pllk, ulna, Ivan19981305, and PrianishnikovaRina for testing the round, and MikeMirzayanov for the great codeforces and polygon platforms.

In this round, you'll be given 6 problems and 2 hours to solve them.

UPD: I decided to drop the 3 seconds rule. The scoring distribution is 500-1000-1500-1750-2500-2500. That means you should probably read both E and F :D

Good luck & Have fun!

UPD: here's the editorial.

UPD: congratulations to the winners!

Div.1+Div.2:-

  1. oxytocyna
  2. E869120
  3. 800iq
  4. cerberus97
  5. Anadi

Div.2:-

  1. 800iq
  2. Alex18mai
  3. Mikaeel
  4. prick
  5. wasyl

See you in the second round :D

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

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

Trying to make enough money to afford MIT. I see you. Only a few ten thousand dollars left np

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

By tradition, the scoring distribution will be announced 3 seconds before the contest.

So accurate!

»
5 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Imagine next rounds you would actually use high precision clocks to measure the interval of announcing score distributions... ;)

»
5 months ago, # |
  Vote: I like it -7 Vote: I do not like it

The time is good for Chinese.

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

    Oh,No.The best time is before 8 p.m, so that they can go to bed earlier.

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

    code with girlfriend wonderfully

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

i m very excited about the new contest

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

4 contests in the next 7 days, great.

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

Looking forward to more fun XOR questions

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

Upvoted for creating 3 contests simultaneously (Great job!).

Downvoted for not capitalize "Codeforces" and "Polygon".

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

It seems that another competition season has come

So many contests these days :)

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

mohammedehab2002 previous rounds all problem names start with "Mahmoud"(round #396), "Ehab"(round #525) and "Mahmoud and Ehab"(round #473). Guess which start is next ??

»
5 months ago, # |
  Vote: I like it -22 Vote: I do not like it

up to which rating second division?

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

    Upto 2099, but if div1 and div2 rounds are held simultaneously people who are rated greater than equal to 1900 must participate in div1

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Wait, sorry guys I am new here. Do you have to start at that exact time? Or is there a contest window where we can choose to do it?

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

    You need to register before the contest starts. Registration's usually open till 5 minutes prior to the start of a contest. Some contests support extra reg which opens 10 minutes after the contest start and continues for 20 minutes.

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

      I did register, but do you have to start at that exact time? Thanks,

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

        You can start the contest any time, only registration's the key. Though the quicker you solve a problem the more points you receive for it.

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

    There's no window, the contest starts at the same time for everyone.

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Let's get ready to rumblllllllleeeeeeeeeeeeeeeeeeee!!!!!!!!!!!!!!

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hope this round not unrated and no accident

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Do we have a hacking phase?

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

Scoring distribution shall be announced 3 seconds before contest

I decided to drop the 3 seconds rule. The scoring distribution is 500-1000-1500-1750-2500-2500.

Rules are made to be broken here. xD

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

You really like GCD and prime numbers ! (WOW!)

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

    The description of the topic is short and concise。

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

Apparently, it wasn't.

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

    if only query d at beginning and query s on LCA

    then will get FST

       /\
      /\ \
     /\ \ \
    /\ \ \ \
    

    but I have no idea to solve it correctly now : /

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

How To solve problem D ?

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

    Think in terms of prefix xors.

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

    Instead of directly construct the array, just construct the prefix xor version of the array S1, S2,..., Sn. So the condition that no subseg has the xor equals to 0 or x is the same as the array S is distinct and there is no pair in S that xor of them is x.

    So iterate from 1 -> 2^n-1, if x^i also belongs to the given range [1, 2^n) then just pick one, or else pick both.

    To construct the answer array A from S, use : Ai = Si^S(i-1).

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

      What is prefix xor ? And why prefix xor array changes the condition?

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

    First observation, if there is no number x restricted. You can simply construct something like 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1... This pattern is optimal because at every i-th number where i is 2^x, you cannot add any new number using numbers in range [1..2^x), any new addition will cause XOR to be 0. Hence, you will need to add 2^x every time you are at the 2^x-th number (1, 2, 4, 8, 16, ...).

    Now, what about the restricted number? Well you can simply take the biggest 2^x that forms x. e.g. if x is 5, restricted number will be 4. Now, you can simply skip the restricted number when you want to form the sequence. (Why biggest? To minimize the largest number in the sequence) e.g. x = 5 1 2 1 8 1 2 1 16 1 2 1 8 1 2 1, if at any time the number has exceed 2^n, just stop adding new sequences.

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

    What can be pretest 7?

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

      I thought of something like 4 5. Answer should be longer than 1 2 1 8, ... But I initially only answered 1 2 1 which is a wrong answer

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

    I will explain the complete solution of D.

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

I found B to be harder than C and D maybe because I was approaching it wrong way.

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

How to solve B? And why does it get TLE 55041556 ?

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

    To be honest, B is so simple. If we have both odd and even numbers, then the sorted array is the answer, or else just print the original array. Correct me if I'm wrong

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

      Maybe i dont understand you but what about this test: 3 2 3 2 1 (n = 5)

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

        Oh. Why 1 will be at the first place? We can swap only odd and even numbers, isnt?

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

        It is 1 2 2 3 3. Because both odd and even exist, we can easily prove that using the allowed operation could sort the array, and obviously the lexicographically smallest array.

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

        "You can perform the following operation on it as many times as you want:". Of course i again solve another problem (( .

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

        You could swap the array as: 3 2 3 2 1 -> 2 3 3 2 1 -> 1 3 3 2 2 -> 1 2 3 3 2 -> 1 2 2 3 3 -> swap can be performed as many times needed

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

    if the input contains both odd and even numbers the result will always be a sorted array.

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

    You need to notice that, if there are only odd or only even numbers you can not make any swap. Otherwise you can sort the whole array.

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

    If we have at least one odd and another even number, we will be able to reorder the whole array (swap two odd numbers or two even numbers). For example, if you wanna swap two odd numbers o1 and o2, with an even number e, you can do:

    swap o1 and e, swap e and o2, swap e and o1.

    And the position of o1 and o2 was swapped as a result.

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

Hints for F please.

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

    Firstly, ask the distance from 1. Now find the centroid of the current tree and check if it is an ancestor by checking if dist(root,centroid)+dist(x,centroid) == dist(root,x) , if that holds true, query the next node on the path and make it the root and now distance from root is dist(x,centroid)-1. otherwise, you can delete the subtree rooted at the centroid and everything else remains the same.

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

I've seen successful hacks made. Any hints what they were about?

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

    In my room there were submissions that checked if there is any odd numbers and sorted based on that (I found one more submission like that after the end of contest :@ ) .

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

    One of the mistakes on problem A was dividing sum of the numbers by 2 for checking the answer, while the sum is odd.

    Sorry for bad English. :)

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

How to solve F?

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

god damn it when I started to feel I'm halavin I failed on the fourth hack

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

    wow 3 hacks, how did you get them? was there a corner test case or something?

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

      Who did not solve A by sorting the array for some reason they were swapping the first different element from the first half with the other half and then print the array

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

        nice

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

        Isn't there an ambiguity in Problem A? In the end, it says "They must form a reordering of a. You are allowed to not change the order". What does that mean? As per my understanding, it meant that we're allowed rotate the array(so that ordering remains same) but, can't sort it completely.

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

          you are allowed to not change the order means you can leave it as it is and they must form a reordering of a means you can swap any element as many times as you want

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

            Oops, that reordering thing got me. Thanks.

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

seem too difficult for me..... the code has some question...

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

this is the worst!

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

Hints for F? Can it be solved using LCA?

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

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

    After solving (A,B,C)^zzzzzzzzzzzz
    01:59:29 Successful hacking attempt

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

How to think and approach problem D?

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

    Every number has only one number that makes (A^B == X) true. The problem asks for sub segment so it's another way to tell you to think of prefix xor. The answer should be clear after that.

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

fml, my bug on F was that I'm doing return the answer if there is only one edge from the current node, which should be the back edge to the parent, but I forgot the root!

Nice round, I really liked it :D

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

Any ideas for E? i see most solution use dp. can anyone explain!

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

    For E, $$$a_1=p_1^{e_1}p_2^{e_2}$$$. then max is $$$1+e_1+e_2$$$. that's exp step down. so $$$a_1$$$ must be $$$2^k$$$ or $$$2^{k-1}3$$$ (if $$$\leq n$$$). then remain is combination count. but no time to code.. the annoying $$$3$$$.

    Am I right? or is there a better solution? wait for tomorrow morning:) sleep now

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

    Actually, I didn't use DP. I used only multiplying. Seriously, I didn't use DP.
    My solution of problem E is as follows:

    ---

    Step 1: What is the maximal possible value of $$$f(p)$$$?
    Actually, the maximal possible value of $$$f(p)$$$ is as follows:

    • $$$1 \leq N \leq 1$$$ : $$$max=1$$$
    • $$$2 \leq N \leq 3$$$ : $$$max=2$$$
    • $$$4 \leq N \leq 7$$$ : $$$max=3$$$
    • $$$8 \leq N \leq 15$$$ : $$$max=4$$$
    • $$$16 \leq N \leq 31$$$ : $$$max=5$$$

    But why? Think about the sequence of {$$$g_1,g_2,g_3,...,g_k$$$} if you assume $$$g_1>g_2>g_3>...>g_n$$$. For example, if $$$A=$$$ {$$$4,6,2,1,5,3$$$}, the prefix gcd will be {$$$4,2,2,1,1,1$$$}, so $$$g$$$ will be {$$$4,2,1$$$}.

    Because the optimal sequence of $$$g$$$ is {$$$2^{k−1},2^{k−2},2^{k−3},...,4,2,1$$$}. Suppose $$$N=11$$$. For the sequence {$$$8,4,2,1,11,10,9,7,6,5,3$$$}, it is easy to find that $$$g$$$ is {$$$8,4,2,1$$$}.

    ---

    Step 2: How many ways are the maximal answer?
    Let's think about writing the value of $$$a_i$$$ which changed the prefix gcd. For example, if $$$g$$$ is {$$$8,4,6,5,2,3,1,7$$$}, the values that you will write will be {$$$8, 4, 6, 5$$$}.

    So what is the possible sequence of values which you will write? Suppose $$$N=8$$$.
    • 1st value: $$$8$$$. Only $$$1$$$ way.
    • 2nd value: $$$4$$$. Only $$$1$$$ way.
    • 3rd value: $$$2, 6$$$. $$$2$$$ ways are possible.
    • 4th value: $$$1, 3, 5, 7$$$. $$$4$$$ ways are possible.

    So the number of possible sequence of values which you will write will be $$$1 \times 1 \times 2 \times 4 = 8$$$.
    But, how about the other values? If sequence is {$$$8,4,6,5$$$}, you should insert other values: {$$$1,3,7,2$$$}.

    You should think about inserting in order of $$$1, 3, 7, 2$$$. (Insert from values which is not divisible of $$$2$$$, next not divisible for $$$4$$$, next not divisible for $$$8, 16, ...$$$

    • There are $$$1$$$ ways to insert $$$1$$$: Just after $$$5$$$.
    • There are $$$2$$$ ways to insert $$$3$$$: Just after $$$5$$$, or just after $$$1$$$.
    • There are $$$3$$$ ways to insert $$$7$$$: Just after $$$5$$$, just after $$$1$$$, or just after $$$3$$$.
    • There are $$$5$$$ ways to insert $$$2$$$: Just after $$$6, 5, 1, 3$$$, or $$$7$$$.
    So for each sequence you wrote, there are $$$1 \times 2 \times 3 \times 5 = 30$$$ ways of insertion. It means there are $$$8 \times 30 = 240$$$ permutations of $$$N=8$$$ which is maximal.

    So, let's move on another example. Suppose $$$N=11$$$:
    • Ways to write: $$$1 \times 1 \times 3 \times 6 = 18$$$ ways
    • Ways to insert the other values: $$$1 \times 2 \times 3 \times 4 \times 5 \times 7 \times 8 = 6720$$$ ways
    • So, the answer will be $$$18 \times 6720 = 120960$$$.

    Did you get it? :)

    ---

    Step 3: Thinking about other cases, not only $$$g =$$$ {$$$2^{k−1},2^{k−2},...,4,2,1$$$}
    If $$$N=12$$$, not only {$$$8,4,2,1$$$} is maximal, but also {$$$12,4,2,1$$$}, {$$$12,6,2,1$$$}, {$$$12,6,3,1$$$} is maximal.
    So you should brute force sequence $$$g$$$ (There are up to $$$O(\log N)$$$ ways). If you determined the sequence $$$g$$$, you can do like step 2: first calculate the number of sequence that you will write, second calculate the number of ways of insertions and finally mutiplies.

    Since the complexity for each $$$g$$$ is $$$O(N)$$$, so the total complexity is $$$O(N \log N)$$$. If you precount factorial and inversions, you can also solve with $$$O(N+\log^2 N)$$$.

    Sorry for my poor English.

    Code (Uploaded at 2:01 JST, 56 minutes after the contest)
    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Thanks for your great explanation ! I just have a small question: In step 2, when you were inserting values 1,3 and 7, why isn't it possible for all of the values to be inserted before 5?

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

        No need for further explanation. I get it now by some other way (not sure if it is different from your explanation)

        • 1st number has only 1 option, which is 8
        • 2nd number has only 1 option, which is 4
        • 3rd number has 2 options, 6 & 2 (suppose we take 6)
        • 4th number has 5 options, 1,2,3,5 & 7 (suppose we take 7)
        • 5th number has 4 options, 1,2,3 & 5 (suppose we take 5)
        • ... we continue like this

        the result = 1 * 1 * 2 * 5! = 240

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

      Thanks

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

seems that problem B shares the same trick with problem C in Global Round 3..

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

    what i felt and is true for most cases : if u don't know proof just input garbage and get gold.

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

    Yeah exactly same over here too!

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

I like problem E.

»
5 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Thanks for mathforces (no)

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

Tears of unskilled.

»
5 months ago, # |
Rev. 4   Vote: I like it +19 Vote: I do not like it

61741833-1039620329569556-2416932415634145280-n

X is 29.

Apparently this tc was not there in PreTest of F.

Naive Solns asking only type 2 queries will take atleast 8 queries.

Extending this tc — for $$$n*(n+1)/2$$$ vertices will take $$$n$$$ queries.

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

In the problem A, it was mentioned in the problem that order of the array should not be changed! What did that line mean and how do we reorder it without changing the order? Please Help!

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

    "You are allowed to not change the order", not "You must to not change the order"

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

    Please read it carefully :

    You are allowed to not change the order.
    

    I guess u miss read it as:

    You are not allowed to change the order.
    
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oops! Thank you so much! Will surely take care from next time!

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

$$$A, B$$$ and $$$C$$$ felt like typing test. The situation drastically changed afterward :(

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Very very nice contest, 10/10. Tl63 just because of using included sort. I hate this test -_-. But in general all it was good.

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

Can someone explain how to solve this example in F?

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

    You can use a method named "Heavy-Light Decomposition".

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

wow I got TLE on test 63 and my rating is gone

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

    The test 63 is the hack I used during the round, so I want to clarify a couple of points:

    First that seems the only test with anti Quick sort test, I can see that 150+ solutions failed this test and if it wasn't added all these solution may have been passed, I've also always see Quick sort solution pass sys test in previous rounds, so I think such test should be always added to any problem that require sorting.

    Also I'm not very proud with that kind of hack, because all I did is check if a java solution that uses sort for primitive array, so I want to raise attention against this.

    For those who still want to use primitives you can build your own sort function like the radixSort function that I use in my solutions, wich I copied from uwi code ( I hope he doesn't mind )

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

JAVA submissions have been judged on the C++ time limit for the B question. Getting a TLE for an O(nlogn) approach. However I didn't use a StringBuilder which is bad on my part but still a correct solution should pass.

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

    Yeah i notice that. Everyone using java got TLE. I did it using StringBuffer still got TLE.

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

    Problem is not time limit. Problem is the inbuilt sort in Java have worst case complexity of n^2. Hence the time limit. There is blog somewhere on the codeforces discussing this SORTING IN JAVA.

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

Hope that the rankings would be revised. Otherwise rating would take a great hit.

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

55036867 why using StringBuildfer was wrong and a get TLE? java

UPD: 55052153 problem was oin primitive types, only in that, i am so disappointed=(

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

    Everyone using java got TLE.

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

      no i see guy who didnt use stringbuilder, just sout and hes solution was accepted

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

    Arrays.sort() for primitive data types in java uses quick sort O(n^2) while Collections.sort() uses merge sort . Quick sort can have O(n^2) complexity in worst case

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

      55023792 only cuz he used wrapper he passed? nice one

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

        So we were supposed to know that it was going to give a TLE?

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

          now we know; somedyas it will helps, but not tooday; so shitty feeling

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

            63 was the last test case. Looks like some put it there intentionally knowing all java solutions would fail. lolxD

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

            The ratings have changed. its -8 for me,no a big fall so i have no issue.

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

              its not about rating, its about solution, we did it right, but java fucked us

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

                yes that is correct. I could have saved some time and did problem 3 a lot sooner. But i decided to do B first which did take some time which is now all waste.

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

      Java uses Mergesort for user defined objects and quicksort for the rest.Using List or Array won't make a difference i guess.

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

      So what we are not supposed to use Arrays.sort() in future contests?

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

        in this particular case, we can use Integer insted of int, looks like its using another, type of sort, need to check source of class Arrays

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

         what i found

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

      Also judgement was based on 1s time limit. For java it should be 2s i guess.

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

        Does the TLE differ for different languages?

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

          No I was mistaken. Checked previous contests and found that time limit is same for all languages. However many other platforms have extended limits for Java and Python.

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

    I also used BufferedReader, Arrays.sort(), and StringBuilder but still got a TLE :(

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

Lmao, I was so pissed when my naive solution for F had bugs and didn't get accepted, while so many people solved it.
Now I see anyway my naive solution would have got verdict Wrong answer on test 99xD.

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

Wrong answer on test 99. Such pain in F

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

Problem F
qkbjv

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

I passed F in last 5 minutes. Exciting!

Thanks for the round very much!

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

Sorry, does the #23 testcase from F shows "wrong answer query limit exceeded"?

I made a submission with assertion but couldn't see that I was exceeding the limit. 55048680

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

    May be it's because you have a query in your main but you didn't count that ?

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

https://codeforces.com/problemset/problem/1054/D a question similar to today's D

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

Nice Contest.

Btw a simiar (a̶n̶d̶ ̶a̶n̶ ̶e̶a̶s̶y̶ ̶v̶e̶r̶s̶i̶o̶n̶?̶) of F recently appeared in Codechef Cook Off MYS00T

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

Problem F, a very nice tree and interactive problem! Thanks for writers.

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

Well I'm stupid and haven't debugged my F during contest, but here is my solution that should works but it got AC:

First of all let's know a height of x by first type of query with vertex 1, let it be H.

Let root be the lowest vertex that we know that has X in it's subtree.

So let choose a type of query randomly!

If we chose first type then just choose some vertex with height H in root subtree randomly and then change root!

If we chose second type then just change a root!

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

Was a randomized solution intended to pass for F?

Instead of using any heavy-light/centroid decomposition, I just picked a leaf at random for the current subtree, and then asked similar queries as given in the editorial.

https://codeforces.com/contest/1174/submission/55047296

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

    I dont think randomized was intended. But sometimes its difficult to break randomised. Until and unless probability of failing it is high.
    I did saw some randomised solns and one of my friend also used randomised in F.

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

Since editorial is not linked — EDITORIAL

»
5 months ago, # |
  Vote: I like it -16 Vote: I do not like it

^ Click here to go up! ^

»
5 months ago, # |
  Vote: I like it -15 Vote: I do not like it

how. to. calculate. the. contribution. ?why. the. contribution. for. me. is. negative. ? i. do. nothing. God

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

Very neat and clear problem descriptions. Thanks to the writer.

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

Isn't there an ambiguity in Problem A? In the end, it says "They must form a reordering of a. You are allowed to not change the order". As per my understanding, it meant that we're allowed rotate the array(so that ordering remains same) but, can't sort it completely.

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

I think there is a time limit problem in problem 2 for java. Same logic gets accepted for C++ but TLE for java..

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

How to solve the problem D ??

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

hello .. can any one fix this issue with the problem A in round 563 div 2 i had a working code which not getting passed the test #9 here is my code http://codeforces.com/contest/1174/submission/55111106 could any one help me with this...

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

You can change the tags of new problems

You can put the segment tree or... next to the data structure tag