Osama_Alkhodairy's blog

By Osama_Alkhodairy, 11 months ago, In English

Hello Codeforces!

We are glad to invite you to Codeforces Round #613 (Div. 2), which will be held on Jan/10/2020 17:05 (Moscow time). The round is rated for Div. 2 contestants. There will be six problems with a duration of 2:15

The problems were prepared by me, mohammedehab2002, DeadPillow, and MikeMirzayanov.

I'd like to thank pikmike for coordinating the round, dorijanlendvaj, aryanc403, Ari, ZeroAmbition, defolaut, Pavlova, mahmoudbadawy, zoooma13, Mohammad_Yasser, Rox, and BledDest for the invaluable testing, and MikeMirzayanov for great Codeforces and Polygon systems.

Good luck!

UPD1: We decided to add one more problem and extend the duration to 2:15 to make the contest more balanced.

UPD2: Score distribution: 500-1000-1250-1750-2250-3000

UPD3: Editorial is out.

UPD4: Thanks for participating! Congratulations to the winners:

Div. 1 (unofficial) participants

  1. Benq
  2. tzuyu_chou
  3. Andreikkaa
  4. neal
  5. mango_lassi

Div. 2 participants

  1. fmota
  2. FSTForces
  3. yet_another_ATS
  4. iwasa
  5. DP_I_J_K_L_M_N_O
 
 
 
 
  • Vote: I like it
  • +401
  • Vote: I do not like it

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

Cyan setters are all gone but it'll be good round.

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

I don't think I've ever seen a shorter contest announcement before

EDIT: Hope the statements are as short as the announcement

  • »
    »
    11 months ago, # ^ |
    Rev. 4   Vote: I like it -15 Vote: I do not like it

    There was such a short announcement before. But it became longer as details have been added. Perhaps this announcement will be the case too. Anyway I hope the description of the problem is as simple as this announcement at the upload.

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

    I hope so! And the tasks will be easier than others in early contests

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

as always hope for interesting and SHORT STATEMENT problems!

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

Waiting for XOR problems.

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

Osama_Alkhodairy's fan club members are so proud of you <3

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

I always like that type of question which has no story.

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

It will be a nice round

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

Arabic round :D

I will participate for sure

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

I look forward to more XOR questions from mohammedehab2002

Fantastic job at setting the questions !

$$$F$$$ looks like a classical question but somehow I am not able to figure out how to do it. Surely, there must be similar Project Euler questions ?

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

    It's Ehab. Please correct. I still remember the Ehab and expected XOR problem. That was my best contest so far.

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

5 problems... I think it will be good contest

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

I predict that there will be a gap between problem C and problem D Let's see (:D

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

Egyptian!! I'm so proud ❤

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

An Egyptian round! :D I can't wait to see how good the problems will be tomorrow <3

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

Where the cyan gang at?

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

so proud of you guys , keep going <3 <3 i love Egypt

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

Egyptian contest Of course i will participate ❤️

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

Hope to become newbie after this round.

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

Hope pretest passed => system test passed

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

I know we're not a big audience, but it would be nice to have some contests at viable times for those in the PST time zone (California) :) I feel like most contests in the past year have started between midnight and 6:30 AM for us.

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

    Thanks for calling it out!

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

    I'm in California too and I totally agree. The convenient thing is, at the very least, 6am contests are generally before school/work.

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

Nice Five

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

Very nice First Arabic round for Me

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

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

Expected suitable problems .

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

nice day, atcoder -> codeforces, two contests

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

Waiting for short problem !!!

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

What's the score for each problem?

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

Thanks for the sixth problem. You are the best

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

means the added problem can be solved in 15 minutes hope the problem added would be moderateUPD1:

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

    It means that the added problem can be solved by the top level in 15 minutes.

    I expect the added problem to be C or D. Likely, the middling finishers will do A,B, and possibly C, then looking at the old next problem with over an hour left, they would find it nearly impossible. However, with this added problem, these middling finishers can now attempt to solve the added problem, with the hour they have left.

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

means the added problem can be solved in 15 minutes hope the problem added would be moderate

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

I am getting feels that many solutions will fail on system tests.

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

The problem statements are as short as the announcement was.

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

How to Solve D?

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

    Trie + dp:

    You build a trie bit by bit with the first edges corresponding to the most significant bits. after that, you define dp[node] = minimum-maximum for the numbers in this subtrie(i made this word up) if you don't consider the first bits(up to the one corresponding to our node). The edge cases when you only have one child are easy. After all the subtrie which will have the opposite bit is gonna be the one which determines our answer so all you need to do is "dp[nod] = min(dp[child1], dp[child2]) + our current power of 2" and that is it.

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

    Hint — If I have atleast one number where ith bit is 0 and another number where ith bit is 1, I can't avoid having answer lesser than 2^i.

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

      I found that, but because many bits are connected, I couldn't reach the solution.

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

    No dp required. Complexity will be O(NlogN). Let solve(vec,bitpos) indicate the answer , Now if all the numbers in the vector have same bit set/unset recurse solve(vec,bitpos — 1). Else answer is 2^bitpos + min(solve(vec1,bitpos-1),solve(vec2,bitpos-1)). Where vec1 and vec2 are vectors having the current bit set/unset respectively.

    Proof?: If X has current bit set answer has to come from the opposite set ( having bit complementary to X). This is because the numbers belong to the set having same bit parity can never contribute higher minimax that the complementary set.

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

What is the pretest 6 on problem D?

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

Pretest 2 of B?

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

    It was just maximum subarray sum without including [1,n]

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

      Yeah, i got that. But i don't know why my solution was failing.

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

        if maximum subarray sum is equal to total sum by kandane's algo then subtract minimum of minimum of prefix sum and minimum suffix sum. If sum becomes less than previous sum then print yes else no . It took me 4 WA's to realise this case.

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

          when sum get's equal i subtracted min(ar[0],ar[n-1]) from maximum subarray sum

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

        Try this:

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

        3 0 0 100

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

How to solve E?

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

    think when does removing a segment actually increases the answer. think about difference arrays (of what? think about that too xD). just saying, but in both [1,10] [2,15] [3,17], and [1,10], [2,15], [12, 17], remove the middle segment and see?

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

    Sort all points in increasing order, process them from left to right, keep a set of segments. If a segment starts at a give point, add to the set and vice versa. When number of segments changes from 2 -> 1 -> 2, we update increase[index]++ where index is the index of the segment when the num segments were exactly 1 in the pattern 2 -> 1 -> 2.

    Answer is number of union set without removing + max_element of increase.

    Hope I explained it fine.

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

      Honestly I had the same idea, but after atcoder got a bit too lazy to implement it...

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

What's the pretest 2 of question B?

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

In problem D 1285D - Dr. Evil Underscores

The answer always will be $$$2^x$$$ where x is an integer between 0, 30 right ? I came with this idea but I don't know whether its correct or no

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

    I tested this case:

    5

    10 13 16 20 26

    and I found the answer is 20, which is not the power of 2.

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

      Oh my idea turns out to be wrong Thanks for your help :)

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

    NO, take $$$n=7 ,arr = $$$ $$$1,2,3,4,5,6,7$$$

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

    Not true. Consider the input

    4
    0 1 2 3
    

    Answer is 3

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

i have a feeling all my solutions will be wrong in system tests lol

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

Recursion.....uggggh

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

xorforces lcmforces, great contest, thanks!

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

task-B -> find maximum subarray sum for a[0..n-1] and a[1...n-1] take the max of those 2 and compare with array sum

task-C -> find the divisors and store them in vector. Now by brute-force check every pair of elements and output the answer.

EDIT: My C failed :(

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

    for problem B wouldn't your sol is O(n^2)

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

      No its O(n). Search for Kadanes algorithm for maximum subarray sum. :)

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

        Yeah but you are searching for max subarray for 0 to n-1 to [n-2,n-1] right? So you are calling kadanes n time right ?

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

          No i calculate once for a[0 ... n-1] and once for a[1 ... n]

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

What was Pretest 5 for C? and is the answer for 999999999999: 999999 1000001

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

    Try : 8

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

      Its 2 4 ?

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

        should be 1 and 8 since lcm of 2 and 4 is 4 instead of 8

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

        It should be 1 8

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

        LCM of $$$2$$$ and $$$4$$$ is four, not $$$8$$$

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

      It's giving 1 8

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

        Can you share your approach?

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

          If x is even: then loop through 1 to sqrt(n) and find a number(k) which is greater than x/4 and smaller than x/2. If number not found answer is 1 and X otherwise k and x/2 If X is odd: then loop through 1 to sqrt(n) and find number which is divisible by X and form the optimal pair(min of max(a,b) where a = divisor and b = quotient)

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

            Try: 49

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

              Gotcha. It's giving 7 7

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

                That is definitely incorrect... You are making a mistake of including sqrt(X) in the loop which shouldn't be because, in case of perfect square number, this will always lead to two same factors.

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

                  How did you come up with this number?

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

                  Two same factors will make the that number as LCM which is not X which is the target.

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

          Approach for C is simple.

          find set S={Pi^ci: Pi is prime divisor of N. ci is integer >0} it's guarantee that no of distinct element in S can't be more than 15. Because 15!>10^12.

          Now you have to partition this set into two half(say S1 and S2) and find a partition such that max(x,y) {where x=product of no in S1 and y=product of no in S2} is minimum.

          since |S|<=15 you can use Bit-masking for finding such portioning or just do recursion.

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

            Hey, my number theory is weak, Can you suggest me some good resources?

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

How to solve D? Explain for me, plz

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

    One way is to use a prefix trie. If you are at a node at the i'th bit, if there is only one valid edge, say a 0, then that means you can take a 1 without increasing the max xor.

    If there are two valid children, then that means no matter if you pick a 0 or 1, you will have to increase the max xor by 2^i. So, you can just add 2^i to your answer, recurse on the child nodes and take their minimum.

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

    Note that the answer won't exceed than 30 bits.

    Starting from 30th bit, check if the numbers in the array have the same bit on the 30th bit or not. If yes, it is possible to put the same bit in X to make minimum XOR-SUM.

    If not, then we can put either 1 or 0 in X at the 30th bit. If the 30th bit is set 1 in X, then all the numbers in the array with 30th bit as 1 will not give max XORSUM. Hence form a new array with the numbers having 0 as the 30th bit, and continue further towards 29th bit. Similarly, for 30th bit as 0 in X can be handled and take the minimum of them.

    I handled it recursively. LINK TO MY SOLUTION

    P.S. Don't forget to empty the array before starting pushing the array. I wasted 30 minutes to debug that mistake.

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

      We have two choices for Every X so it seems that its 2^30 can you correct me?

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

        Well, if you would observe closely, every number in the array will be appearing the same number of times as the number of bits.

        It is (n*lg(n)), since lg(n) bits are there which is 30 here. The choice of the bit at a particular position also reduces the size of the array, though it's really difficult to explain.

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

          can you elaborate more how the complexity is n*lg(n) ?I think it should be n^2 according to your explanation

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

            at every choosing position, we divide the current array into two parts one with on bit elements and another with off bit.thus it become log(N) with total complexity of O(N log N).

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

    Let's use a Binary trie. Insert all N numbers in the trie. If a number has its 30th bit on then it goes to the right of the root, else goes to the left. similarly at the next level we'll make decision for the 29th bit and so on.

    After you have inserted all numbers in the trie, consider what is the answer for a particular subtree.

    if the root of the subtree has only one child that would mean all numbers under consideration have this bit either on or off and hence we may choose a number such that our answer will have this bit off. In this case answer will the same as the childAns.

    if the root of subtree has two children then numbers under consideration belong to both bit on and off categories and hence no matter what number we choose this bit will definitely be on in our answer. In this case the answer will be (1<<bitPos) + min(leftChildAns, rightChildAns).

    Also for time complexity analysis, the solution can be implemented with a simple DFS. Maximum possible nodes in the trie : 10^5 * 30.

    implementation : https://codeforces.com/contest/1285/submission/68543045 (I hope it passes the systest xD).

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

    Alternative soln without trie: Sort all the elements. Let solve(l, r, pos) be the function which gives the answer for the range [l, r] considering only pos least significant bits. Now, observe that most significant bit will be 0 first then 1 in the sorted order. Let f the last position of 0 bit. Now, you can do recursive calls to solve(l, f, pos-1) and solve(f+1, r, pos-1) and then take the answer as (1<<pos) + min(solve(l, f, pos-1), solve(f+1, r, pos-1)). Link to code

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

Thank you for quality problems. Had fun

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

F. Classical?

Yes.

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

    I just copy-pasted code from a problem I solved yesterday :Dd

    (Simpler solutions exist for sure though)

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

      In our defense we had no knowledge of this problem and it only appeared recently. But I agree it does look like a google-able problem, But we didn't find any similar problems so we though why not. I would like to see if there is an old problem with similarities to this one.

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

How to solve F?

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

it felt that this was the easiest Div2 contest I have ever participate but still... :')

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

    wait till you get a surprise WA in sys tests lol, i know i will

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

Is Trie without DP enough to pass D?

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

C can be solved by this way:

Change the A from [sqrt(X)] to 1, and find A and B in which A*B==X and gcd(A,B)==1. The larger A is, the smaller B is, so when A is first found to satisfy the above conditions, A and B at that time are the answer..

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

    Dude, nobody was asking for c solution, why did you put it here?

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

      Because it is related to the competition anyway, and there is no matter.

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

      Dude, nobody was asking for your opinion, why did you put it here?

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

        its recursion. Dude, nobody was asking your opinion, why did you put it here?

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

          Why did you reply him, dude? Nobody was adking for your opinion, why did you put it here?

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

    how you are sure that this will give right answer.. can u explain it more

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

Hello, mango_lassi. Your solution for B is so simple. Can you care to explain?

Thank you :)

https://codeforces.com/contest/1285/submission/68502173

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

    Solution for B:

    Yasser's Score = sum of Ai's

    Adel's Score = max sum of subarray of A (Can be found using Kadene's Algorithm, by running from 1 to n-1 and 2 to n.... Since we can't take the whole array sum)

    if (Yasser's score > Adel's score) Print("Yes") otherwise Print("No")

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

    If $$$\sum a_{i} \leq 0$$$, Adel can just pick any cupcake with nonnegative tastiness. Answer NO.

    If some prefix has sum at most zero, Adel can buy all cupcakes not in that prefix. If some suffix has sum at most zero, Adel can buy all cupcakes not in that suffix. Answer NO.

    Otherwise answer YES. Assume Adel buys the interval $$$[l, r]$$$. Then Yasser's tastiness minus Adel's tastiness is $$$sum(1, l-1) + sum(r+1, n) > 0$$$, as all nonempty prefixes and suffixes have positive sum, and either the prefix or suffix is nonempty.

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

    Calculate prefix and suffix sum of array

    if any term in prefix or suffix sum array is less than or equal to 0, then the answer is "NO" else the answer is "YES"

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

    He did it smartly say the sum of the array is S, Now if prefix sum is less than or equal to 0 then suffix sum must be greater than or equal to S Hence [Fail] As prefix sum + suffix sum = S, Similarly, we can do it for suffix case.

    Now you may think it may not cover all the cases, Consider any [l,r], Say the cases we stated above doesn't happen, Then sum[0,l-1] > 0, So it is safe to consider [0,r] and you can easily visualize that sum[0,r] won't be greater than or equal to S in any case, As sum[r,n] > 0. Hence we prove that for any [l,r] We won't find sum>=S Hence[Pass]

    Hope this helps.

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

When would the system testing start?

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

it's too late to start system test........

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

https://codeforces.com/contest/1285/submission/68549930 can anybody explain why is this giving wrong answer?

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

    The initial value of min is too small. If $$$X$$$ has a divisor that is a power of a prime number and this divisor greater than INT_MAX, the correct min will greater than INT_MAX.

    For example: If $$$X=10000600009=100003^2$$$ ($$$100003$$$ is a prime number), your solution outputs 4 2147483647, correct answer is 10000600009 1.

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

      thank you so much. so basically i missed out on 1100 points because of that

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

The contest was great. But I'm anxious for system test and it's too late.

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

 Wow,8000 passed pretest, good number

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

Anyone feels that C was easier than B

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

    Yup, C was indeed easier than B

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

    B was infact copy-paste from gfg (kadane's algo),tho C required some brain cells Ps: I got accepted B in 6 attempts lol

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

      I solve C without much thinking and even though i know B need kadane's algo still i couldn't solve

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

        see my solution for B,I just took care of the condition which requires not to select whole array as subarray. here

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

    I tried C first than B because I felt it easier and I wasn't sure of my approach of B...But it wasn't a good strategy xd

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

Good D problem.

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

DeadPillow Tell me the truth. You started the system test late to add the case that breaks my problem F. :P

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

Can someone give me a hint for problem F?

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

Just saw a WA on 159! Time to leave earth!

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

Can anyone explain why the output is to be NO for this case for problem B
1
10
10 5 -12 7 -10 20 30 -10 50 60

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

    take [20 30 -10 50 60] 20+30-10+50+60 = 10+5-12+7-10+20+30-10+50+60

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

Never use INT_MAX as infinity....today i realised it is smaller than 10^12

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

After several tries on F, passed in the last second!!! ...

 System test: What? What did you say?

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

Guys , I submitted the second problem( B ) successfully . In the system testing it gives me TLE , on the go I resubmitted the same code and it submitted succesfully . HOW ?? Can anyone explain to me ?

cf MikeMirzayanov

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

    Quite strange.The TLE code shown is accepted. I think, you must tag admin in this case.Maybe he can help.

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

Nice and balanced problem set.

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

I just got a mail saying that my solution of problem D coincides with another contestant (Hemose) . The solutions are completely different except from the Scanner class that is used by most of German University in Cairo students because it is implemented by a senior in our community here is a link to the Scanner class https://github.com/AhmadElsagheer/Competitive-programming-library/blob/master/other_algorithms/Scanner.java. All my problems are "skipped" . Help!!!

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

problem D had really bad pretest.

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

Problem C.

Can anyone tell me why my solution gets TLE on test case 84. My solution is find all divisors of x and store in a vector. Then iterate all possible pair and pick which pair is minimum.

Submission Link: https://codeforces.com/contest/1285/submission/68510565

Thanks :)

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

    I also did the same and got TLE during system testing. I read somewhere that the upper bound on the number of divisors of a number is of the order n^1/3. So the total complexity of the solution will be O(n^2/3). Which according to the constraints will run till 10^8. Correct me if I am wrong.

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

Dear Sir/Ma'am,

I have not committed any kind of plagiarism act in this contest.The question is very common and the same has already been taught to both of us in our Coding institutes named Coding Ninjas. We have done the same way as our mentor taught us. This may be the reason why our codes are matching. Please believe me I have dont been involved in such activity and will make sure that my code doesn't match with anyone. Please update my ratings as soon as possible instead of marking it as a System error.This is really unfair with me.All my submissions are marked as skipped.Please help. 1285B - Just Eat It!

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

Dear Sir/Ma'am,

I have not committed any kind of plagiarism act in this contest.This question is very common and the same has already been taught to both of us in our Coding institutes named Coding Ninjas. We have done the same way as our mentor taught us. This may be the reason why our codes are matching. Please believe me I have dont been involved in such activity and will make sure that my code doesn't match with anyone. Please update my ratings as soon as possible instead of marking it as a System error.This is really unfair with me. All my submissions are marked skipped.Please help.1285B - Just Eat It!

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

Can somebody help me figure out the cause of runtime error in this 68552675. Here is the accepted solution 68560810.

Only thing I changed is a line in comparator, I changed it from if(a & (1ll << bit)) return 1; to if((a & (1ll << bit)) && !((b & (1ll << bit)))) return 1;.

I have already checked the two numbers for equality (and returned zero if they are equal). Is there anything else that is needed to be taken care of while using comparators? Can someone one point out my mistake?

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

Unable to understand div2 round613 editorial for question C for(int i = 0 ; i < (1 << n) ; i++){ ll a = 1, b = 1; for(int j = 0 ; j < n ; j++){ if((i >> j) & 1) a *= f[j]; else b *= f[j]; } if(max(a, b) < max(ansa, ansb)){ ansa = a; ansb = b; } }

This part, what is it doing?

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

please explain problem f classical

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

After seeing today's solution div3 A's reaction will be like this->

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

Please help!! I got WA in test case 7 in Problem C. The testcase is

999999999989

In my computer the output is 999999999989 1

But in judge output is 1 1

My submission 68590352