Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

mohammedehab2002's blog

By mohammedehab2002, 9 days ago, In English,

Hi!

I'm back with a new contest, a new color, and a new batch of xor problems.

Codeforces round #525, rated for the second division, is taking place on Dec/04/2018 17:35 (Moscow time). As usual, first division participants can take part out of competition.

I'm the problemsetter of the round. I'd like to thank 300iq for the great effort coordinating the round, isaf27, cdkrot, BudAlNik, and gritukan for testing the round, scanhex for translating the statements to Russian, mahmoudbadawy for giving his opinions about the problems, and MikeMirzayanov for the great codeforces and polygon platforms.

Like my previous round, you'll be given 6 problems and 2 hours to solve them.

After the contest, I'll be on the community Discord server to discuss the problems.

UPD: the scoring distribution will be 500-1000-1500-2000-2500-3000.

UPD: something wrong happened and the editorial was deleted. I'll post it as soon as possible :(

UPD: the editorial has been re-written.

Good luck & Have fun!

UPD: congratulations to the winners!

Div.1+Div.2:-

  1. Madball
  2. Shayan
  3. ei133333
  4. paulica
  5. _Kuroni_

Div.2:-

  1. paulica
  2. DXC
  3. 0101-1001
  4. problem_destroyer420
  5. knil_GMO
 
 
 
 
  • Vote: I like it  
  • +473
  • Vote: I do not like it  

»
9 days ago, # |
  Vote: I like it +79 Vote: I do not like it

xor problems

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

Egyptian problem setters , great ^^

»
9 days ago, # |
  Vote: I like it +38 Vote: I do not like it

Generally xor problems are really nice problems, hope this contest will be nice too.

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

    Really? This might be an unpopular opinion, but I feel like xor problems often involve the same few tricks (trie, solving the problem for each bit independently, making use of the involution property, segment tree of xor's, etc.).

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

      What is the involution property?

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

        An involution is a function f: x -> x that, when applied twice, brings one back to the starting point. -Wikipedia

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good!

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

Thanks :)

»
9 days ago, # |
  Vote: I like it +29 Vote: I do not like it

your previous round was one of the best rounds i've seen since i join codeforces

hope to see such a great contest again

»
9 days ago, # |
  Vote: I like it -45 Vote: I do not like it

this is so great but will it be rated?

»
8 days ago, # |
  Vote: I like it +2 Vote: I do not like it

my favourite colour is green

»
8 days ago, # |
  Vote: I like it +32 Vote: I do not like it

i will try my best to solve some problem , and get higher rating :')

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

Mahmoud and Ehab and the Xor, Mahmoud and Ehab and Xor-MST. These problems are freaking difficult and awesome. Expecting more difficult and great problems ;)

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

good

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

    wow , my friend :D , hope you'll become green after this contest :D

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Let the strongest be lucky at the contest. All the will of Allah. You can't keep an eagle in a cage.Inshallah!

»
8 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Whats up with long submission queues!

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

Good Luck for us all

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

GO gritukan GO for newbie this time :P.

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

I was a bit scared at the first place seeing green color in the thanksgiving section.Then I realized the joke!

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

With the kind of determination gritukan is showing in making his rating fall, he'll definitely beat the lowest rating of worse one day.

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

    nobody can beat worse,even tourist

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

      Maybe that's why he wants to achieve this feat. :)

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

      dont get too carried away so soon, mighty pakistan beats everyone in every direction. In east we beat china, in south we beat india and in north we beat afghanistan, and in west we beat europe. hail us! we breath in war

»
7 days ago, # |
  Vote: I like it -20 Vote: I do not like it

i DO NOT understand what this is about. can someone explain please?

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

Is it rated?

»
7 days ago, # |
  Vote: I like it -30 Vote: I do not like it

sorry i cant read

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

I can't submit my code. Please help me.

I tried to send some codes with several languages, but the system always says "You have submitted exactly the same code before", even though "My submission" is still empty.

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

The scoring distribution provided here seems not matching the ones in standings page.
Please have a look.

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

Problem C seems buggy

»
7 days ago, # |
  Vote: I like it -30 Vote: I do not like it

MAN what is not ok with problem C????!?! it compilation erorr VERBOTEN why post a broken contest i don’t understand??? i’m very sorry if i offended anyone with this matter.

dumb russian apes

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

I have a dream...

that one day...

problems will go from easy to hard GRADUALLY and not like this

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

Someone else having problems with the interactor of problem D???

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

    yesssss

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

      It's printing things I am not asking it to print !!! This is crazy, I wrote a solution in the 34 minute and it still didn't pass the first test !!! I don't know what is it printing :(

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

        for me it says my answer is "60" , it's not even possible to mycode print it ;

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

          Same here, printing 30 -_-

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

          I think 60 is the number of questions you made not the real output of your program

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

    Guys, interactive tasks are technically different in preparation :/ The output shown to you is the number of questions. Sorry if it made an inconvenience but some people asked in the clarifications and we cleared it.

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

      It is possible to write an interactor in a different way — printing the participant's answer, not a number of questions. Interactor should exit with WA if query limit is exceeded. And checker should check the answer if the interactor finishes successfully. For me, it is the most convenient way.

      And yes, I consider MikeMirzayanov's approach with printing number of queries as a bad practice :)

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

what's wrong with problem D ??? i test it in my system and in custom test and i get correct answer in test 1 and when i submit that i gave wrong :///////

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

Is the idea for F that output tree must be a strict min heap. And now first value is hoax. For second value we need what is min value in 2^i distance tree from every vertex? How to do find min value in 2^i distance tree for all vertices ??

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

    F is only about extracting information from the statement. Let's interpret w as sum of cost of edges. Now, what we need is to find the minimum spanning tree. In the first tree, root at minimum value vertex. For each vertex, we only concern about edges connect it with 2i-th ancestor or root.

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

2o50s2

me.

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

Oh God I forgot question marks in D

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

In any universe will this code print 30 for problem D???

link

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

    Because you wrote "for(int i=0;i<30;i++)" instead of "for(int i=29;i>=0;i--)", thus your algorithm is wrong?! x)

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

    My upvote is for the rick in the profile pic and multiverse reference in the comment.

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

i'm so stupid today. I don't think that a and b in problem A can be equal :(

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

    I tried the trivial solution with brute force and after I run these test cases, I figured out that they can be equal :D

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

    i think one of the pretest needed a and b to be equal the first one i sent(thinking they couldn't be equal) got WA on test 10 i changed the one line and got accepted

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

-

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

    Solution for E: Observation: the biggest fraction is always equal to the answer for k = 1 : the subtree with maximum sum. How to choose more components now? They all must have sum equal to maximum sum in a subtree, otherwise the fraction won't be the biggest

    So first we find answer for k = 1 dp on trees. dp[x] = the best subtree rooted at x

    dp[x] = val[x] + sum(max(0, dp[y]) | y is son of x); We calculate this dp using dfs.

    Let us denote maximum sum of a subtree with M.

    Now we can do a greedy to find maximum number of subtrees. We reapply the first dp algorithm again, but now when we obtain that dp[x] = M, we pick this subtree in answer, and disregard node x so it won't influence answer for father of x.

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

How to solve D?

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

    XOR with powers of 2

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

      Could you elaborate more? What do we achieve by this?

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

        first you ask it ? 0 0 and know which one is bigger ( name it first comp ) , then you ask all power of 2 between 0 to 29 , if the comparison was the same with first comp then both have it or both don't have it so you ask c = 2^i and d = 0 and know they both have it or not , and if it wasn't same with first comp then the biggest one has it .

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

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

    Just find non-equal bits, then you can easily restore equal bits. To find first one if answer for (a, b) differs from answer for (a+1^i, b+1^i) change a and b.

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

      I got stuck restoring equal bits, how do you achieve that?

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

        ask (a+2^i, b) if it's -1 then both are 1, else both are 0

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

      How do you restore the equal bits?

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

    Let a = a1a2... a30 and similarly define b. We will find bits from MSB to LSB. Initially find the result with c = 0, d = 0. This will give you a comparison between a and b. Let us call this r.

    Now suppose we are discovering (i)th bit. We will always keep c = a1a2... ai - 1 and similarly d. Now query for c + 2i, d + 2i. If the result is opposite of r then you know the values of ai, bi and ai ≠ bi. Here you will need to update r once again for unknown bits.

    Else we have ai = bi. Here you do not need to update r :). So, to find the value of ai, bi just query c, d + 2i.

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

interesting problems, thank you

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

xor + interactive

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

    you should quit using bold letters. thats annoying

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

Can anyone explain the second sample of problem F? I can't get 44 from the optimal tree.

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

I felt like tourist when I solved A in 1 min xD

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I feel like tourist when I travel around the world.

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

i do not care

»
7 days ago, # |
  Vote: I like it -45 Vote: I do not like it

make this platform hacker free..... my solution just got hacked.. use good antivirus

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

    Pakistan, apni akal kabar me khod ke aaya hai kya...inshallah, boys played well karte karte dimaag bhi sooj gaya hoga...lol

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

This is not cool. C — 1500 and D — 1750. And D is way more difficult than C.

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

    For me C was harder than D. I do agree that the problems were harder than on an average div2 round though.

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

      mango_lassi I just checked out your submissions. How are you able to get wrong pretests at a moment and submit the correct code in just 1-2 seconds after that?

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

        What do you mean? I resubmitted B 3 minutes after failing pretests, and C a minute after.

        In C I outputted the numbers for the operations in wrong order, so it was very fast to fix

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

          Oh my bad!!! Actually since you out of competition contestant, your submissions were shown in hh:mm format, while others(in-competition contestants' submissions) were in mm:ss format. NVM, I misunderstood minutes as seconds and out of curiosity asked immediately. So sorry.

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

      Same. I feel so stupid. How do you solve C? Edit: Never mind. I got it. So fucking stupid.

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

        In first step make all elements equal to 0 by "2 n 1".

        Make all elements equal to a large number say 1000000 by "1 n 1000000".

        Now, run a loop from 1 to n-1 (not n) with iterator i and take modulus by 1000000 — i by "1 i 1000000-i".

        Total n+1 steps and your task is done.

        Note that all indexes less than 'i' will not be affected by taking mod at any step, as they will become smaller in the previous steps itself.

        Thus, your final series will look like 1,2,3....,n-2,n-1,1000000 (independent of the array, just depending on the array size).

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

    yeah what the hell C was rigged to not accept my problem even if it was completely correct just so we get lower ratings WTF

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

Why system testing is late today? Any specific reason?

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

    yeah they don't actually know how to code so they can't say whether the problems are correct or not so they have to manually call a friend who knows how to code and make him verify every single problem

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

Thanks for an interesting content! And, I have a question on prob. D, which I've been getting on it for an hour. It annoys me.... My question is why I always get a WA on case 1. I don't think I have printed anything larger than 2^30.. Could anyone help me? Thanks a lot! here is my solution.46617886

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

    I don't really understand why people don't test their solutions for interactive problems.

    Just set the number of bits to 2 instead of 30 (so that you have less questions) and interact with your program. Just don't forget (like me) to set the number of bits back to 30 when submitting.

    Had you checked, you would've seen that your program outputs some weird numbers. The problem seems to be you used uninitialized variables, i.e. you wrote int a, b; instead of int a = 0, b = 0;.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, you are right! It works. Thanks. I'm so frustrated that I should have made such a mistake. Actually, I tested my solution. That'y why I posted this. Maybe my complier optimized such a mistake so that I couldn't notice. Thank you for your help. It's a stupid mistake.

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

    Each pair of submissions seems identical. They will be caught by cheating detector for sure.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    umm this is normal in india :)

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

How to solve E?

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

Umm was this round not rated?

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

    It usually takes a while after the contest ends for ratings to change

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

Why is he doing it? 46594591, 46591499

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

Happened to be my last Div2 contest, and it was a good one. Thank you!

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

paulica ANIMALLLLLLL

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

Got stuck on D for 1.5h during contest without reading E. After contest I read E and solve it in 25 mins :D.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

ok. guys. i am new in competetive programming. please help me.

i have a source code on mergesort whenever i need to use that on problem, i just reform that.

include<stdio.h>

int temp[100000];

void mergesort(int low, int high, int num[]){

if(low == high){

    return;
}
int mid = (low + high)/2;

mergesort(low, mid,num);

mergesort(mid + 1, high,num);

int i,j,k;

for(i = low,j = mid + 1, k = low; k <= high; k++){

    if(i == mid + 1){

        temp[k] = num[j++];
    }
    else if(j == high + 1){

        temp[k] = num[i++];
    }
    else if(num[i] < num[j]){

        temp[k] = num[i++];
    }
    else{

        temp[k] = num[j++];
    }
}
for(k = low; k <= high; k++){

    num[k] = temp[k];
}

} int main(){

int n,i,num[100003];

scanf("%d",&n);

for(i = 0; i < n; i++){

    scanf("%d",&num[i]);
}
mergesort(0,n - 1,num);

for(i = 0; i < n; i++){

    printf("%d ",num[i]);
}
return 0;

} i used the code with just a little change of a book here

at B, i just got my solution coincides. why.

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

For C, I'm unsure why my submission fails at pretest 2. I traced out the moves and the array should be strictly increasing.

I think I am overlooking something obvious. Can someone take a quick glance?

Edit: I mixed up the operations

»
6 days ago, # |
  Vote: I like it -21 Vote: I do not like it

people who watch anime are braindead

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain problem D Solution?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How would one approach problem C if we were to determine the minimum number of steps to make the array strictly increasing??

»
17 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

problem D was a really nice up and down dp tnx codeforces and authors for these problems ;)