mahmoudbadawy's blog

By mahmoudbadawy, history, 7 years ago, In English

Hello Codeforces!

I'm glad to announce that on Sep/19/2017 15:05 UTC Codeforces Round #435 for the second division will take place. As usual, First division participants can take part out of competition.

This round was prepared by me.

I'd like to thank mohammedehab2002 for writing the statements and the editorials and testing the round, Livace,Alladdin,300iq and cdkrot for testing the round, vintage_Vlad_Makeev for helping us in contest preparation, translating the statements into Russian and making one of the problems more interesting, KAN and Ahmad_Elsagheer for giving their opinions and thoughts about the problems and MikeMirzayanov for the great Codeforces and Polygon platforms.

You will be given 6 problems and 2 hours to solve them.

The scoring distribution will be announced later.

UPD. 500-1000-1500-1750-2000-2750

**UPD Congratulations to the winners:

Div1+Div2:

1-Shik

2-KassiJulgus

3-I_love_Tanya_Romanova

4-MrDindows

5-scanhex

Div2:

1-KassiJulgus

2-scanhex

3-qscqesze8

4-UpdateRatingOrRIOT

5-NickR

UPD editorial

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

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

Cool.

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

Hope there wont be too long In Queue submissions...Fix this..its ruining CF...

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

You should have post this announcement after today's QF Quals mirror is finished.

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

Is it ....emmmmm geometrical?

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

please end... contests had be unrated for many times.

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

Is it rated?

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

Pls do something about the long queues. Yesterday's contest was just an example of it but in practice also these days the subs take too much time to judge.

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

    Mike told that it was his mistake and there was no internal fault(that's what I understood from his explanation :) sorry if I am wrong). Yes many times while practicing there are situations of LONGGGG queues... Anyways hope it will be a good RATED round :)

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

is it rated?

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

hope this time in the questions the fullstops and multiplication signs will be different! last time they used '.' for both and it made the question A look way complicated XD lol!

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

    Do you mean you can't distinguish this: "·" from this: "."?

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

Gl & Hf to everyone!

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

The queue problem isn't going away. Even in yesterday's NEERC Subregional, the queue was too long and it affected the contest. When you submit a code, and you get a WA after 7-8 minutes, it doesn't feel good. In a contest, every second counts. Also, you can't concentrate properly on another problem even if you want to while waiting for a queued verdict. It's frustrating. I hope this doesn't occur in today's round. If it does, then it'd be really disheartening. CF is the best, we want it to remain the same way.

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

Is it mathematical?

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

    he is also the author of this round. so maybe you can try it to find out?

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

      In fact, Most of the problems in round #396 are mine while most of the problems in this round are his .

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

Hope the server will work effiently

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

My first contest in CODEFORCES is Round 396 which is conducted by you and I am very happy that again I am participating in your contest.

Thank you.

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

why the last contest was unrated?

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

Score Distribution ? Not Declared Yet , 1 & Half Hour Left

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

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

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

if repeted problem sucks

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

Scala support is completely broken and couple of users reported it for a while. See: http://codeforces.net/blog/entry/54283 http://codeforces.net/blog/entry/54245

I also messaged the admins about it and its still not fixed :(

Hope someone from CodeForces notices this!

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

    I think it is fixed now.

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

      Thank you MikeMirzayanov — I verified it works now!! If it is possible, can you reset my ratings to before the past couple of contests? All my Scala solutions failed during contest due to this bug (I verified they would have passed tests otherwise now).

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

Am I the only one that gets stuck on infinite loading when trying to submit? Have been trying to submit C for 15 min already with no success.

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

How to solve B ?

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

    Count the number of nodes in the odd levels of the tree (first set) and count the number of nodes in the even levels of the tree (second set). Then multiply both of them and subtract the edges that are already exist.

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

      I can`t understand why the following code gives wrong answer

      int one = 0;
          queue<int> q;
          q.push(1);
          v[1] = true;
          while(!q.empty())
          {
              int u = q.front();
              q.pop();
              if(v[u])
              {
                  one++;
              }
              vector<int>::iterator iter;
              for(iter = e[u].begin(); iter != e[u].end(); iter++)
              {
                  v[*iter] = !v[u];
                  q.push(*iter);
              }
          }
      
          int count = (one * (n-one)) - (n-1);
      
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        It might be because of overflows. Change int to long long may be.

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

    here's my solution.Maybe it's make sense.first,we can mark every nodes with zero or one following the the rules of Bipartite Graph,and we can figure out how many ones and zeros, and the result is the count of zeros times ones' ,at last,we should minus the loops.

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

can someone help me figure out why my solution gives tle? I used a random algorithm, the expected running time should be small and it runs fast in my computer. I cant pass pretest 6.

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

    Same here. Try test: 2 0

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

      Hi, gives no in 0.003 seconds.

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

    Maybe RAND_MAX is 32767?

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

      Yes, that was it! Thanks a lot. Its good I learned this while not actually participating. In my computer MAX_RAND is way bigger so it worked fine.

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

        So in general it would be wise to first take the residues mod 32767? and then use them? In case RAND_MAX is bigger, so you dont get overflow

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

          To get around it you could go (rand()<<15)|rand()

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

            Hello, thanks for the comment, can you explain the logic behind this when RAND_MAX is 2^31-1?

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

              Well, the whole point of using this is that Codeforces is run on Windows servers, which means that RAND_MAX is in fact 2^15-1, so this of course combines two random numbers to get one that is ~2^30. If you were using a *nix system then there would be no need for the bit shift, however if you did, then it would overflow. It's probably safer then to have an if statement along the lines of

              if(RAND_MAX < 1<<16)
                  x = (rand()<<15)|rand();
              else
                  x = rand();
              
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                Oh, I understand. That safe solution makes a lot of sense, Ill do that from now on, thanks for the help. fare well and prosper.

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

How to solve C? Good problem in my opinion

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

    I did this : if n <= 4 then you can just brute force, also in 2 0 case answer is NO, else i just find xor of all numbers from 1 to n — 2, the you just have to find two numbers, such that their xor is equal to (xor from 1 to n — 2) ^ x. Also, if (xor from 1 to n — 2) ^ x is 0, I delete n — 2 and add 0 to answer, so I find two numbers, such that their xor is equal to (xor from 1 to n — 3) ^ x

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

    NO only if the case is 2 0.

    if n>=2 then let the first number be 2^18. Then keep filling numbers starting from 1, incrementing by 1 or 2[by 2 if the xor so far turns out to be 2^18], till there's one number left to be filled. The last number = xor(xor so far, x).

    UPD: failed systests :(

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

    When n ≥ 3, define ak = k for k = 0, ..., n - 3. Calculate p = x^0^1^...^(n - 3). Then define an - 2 = 218 and an - 1 = 218 + p or similar. This will guarantee that there are no two identical numbers in the sequence ai and all elements are smaller than 219 - 1 < 106

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

      You failed systest because p can be zero right?

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

        Actually, no. I forgot the case n = 2 and x = 0. I took care of the case p = 0 by redefining a0 = 219 - 1, an - 2 = 3 × 217, an - 1 = 217 - 1. I considered that corner case, and yet forgot abound n = 2 and x = 0. Forgot to mention this in the original comment.

        Most recent submission : 30524864

        Submission during contest : 30508844

        Only difference is the case n = 2.

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

    n — 2 random numbers and then generate last two.

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

    stupid (n == 2 && x == 0) if :(

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

Nice problems, how to solve C?

I had an idea that if a is odd number then aXOR(a + 1)XOR(a + 2)XOR(a + 3) = a - 1, so we generate first 4 * k numbers and find remaining ones with some bruteforce.

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

    I used the same but when a is even a^(a+1)^(a+2)^(a+3)=0

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

      My problem was NO case :(

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

        OK, I couldn't debug my solution during contest ( cause of stupid Wi-Fi problems) but I did now and it got AC, I will try to explain it:

        We have 2 cases that we need to deal with:

        1) N is odd

        2) N is even

        Let P be a power of 2 > 1e5. And in every case we will use an auxiliary array "numbers" which has n numbers such that not one of them is x.

        Case 1 solution: let the first n-1 numbers be ans[i] = P + numbers[i] and their xor be _xor. our last number will be ans[n]=xor ^ _xor

        Case 2 solution: let the first n-2 numbers be ans[i] = P + numbers[i] and their xor be _xor. If _xor = x, we will just change one of ans[i] to be a diffrent and number and ans[n-1] = _xor ans[n] = x;

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

    here is a countercase for your claim. 3, 4, 5, 6 by your claim, answer is 2 but correct answer is 4.

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

Can answer be "NO" in C except 2 0 case?

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

    6 0

    10 0

    n%4==2 0

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

      0 1 2 262147 4 262148

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

      Oh with this case I expect lots of people will be failing. I myself got hacked.

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

      6 0

      YES
      1 2 3 4 8 12
      

      doesn't it work?

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

      My program gives 1 2 3 4 8 12 to 6 0 and i think its correct

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

      1 2 4 8 16 31

      satisfies 6 0 case

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

      YES 29637 1088 18455 13546 1 2937

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

      For 6, 0 my code prints:
      781959 11593 584443 901753 630736 488604
      Which when xor'ed gives 0. Am I missing something?

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

      Now i don't have to wait System testing, C is WA :(

»
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

    Binary search. Even tho I expect that my code runs in an infinite loop for some cases.

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

    Use srand(time(0)) and rand() to generate 15 different integers in range 1 to n. Then Check By Changing the position of a string of n '0'es . Then Print The Answer.

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

And Don't lie that you didn't try to send random solve for C.

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

Will the random solution pass for problem C? (If not, how to hack it?)

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

    my solution is random solution , but i can not prove its time complexity.

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

    Yes, random solution works.
    I randomly pick up (n — 1) different numbers from 0 to 524287 , calculate there xor sum S, then check if S xor x is used. if not, then these (n — 1) numbers and S xor x together is a solution (S xor x < 524288, obviously); if so, then make another try. Since there are plenty of numbers to choose, the probability to success is about 90% percent, maybe higher (I test n = 100000 several times, and they all succeed at the first attempt). So, if you tried many many times, (say, 100 times) and failed, then you can assume this is impossible and print "NO".
    I passed system test, used 46ms/2100Kb, it works.

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

Can anyone say this code bug?(Div 2/c)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+7;
int a[maxn];

int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,x;cin>>n>>x;
	int sum=0;
	for(int i=0;i<n;i++)a[i]=i,sum^=i;
	int nwx=x^sum;
	a[0]=nwx;
	if(nwx>0&&nwx<n)a[nwx]+=(1<<15),a[(nwx==1?2:nwx-1)]+=(1<<15);
	for(int i=0;i<n;i++)cout<<a[i]<<" "
}
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I wanna cry, it was 5 seconds left before I press submit and it tells me contest is over((( Pretty sure the code i was about to submit was correct

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

    Same here hhh. I just adds "stdout.flush()" 5 seconds before it ends.

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

For problem E, I have O(N + M + (M — N) log (M — N) + Q log (M — N)). Is that right?

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

Here is a solution to F:

First of there is a basic observations which is important for the solution.

  • lcp(sl, sl + 1, ..., sr) = min(lcp(sl, sl + 1), lcp(sl + 1, sl + 2), ..., lcp(sr - 1, sr))

Now lets use ai as lcp(i, i + 1) ( ai = lcp(i, i + 1) ).

The problem becomes:

We have an array ai. We have queries for finding the maximum value of min(ai, ai + 1, ..., aj - 1) * (j - i + 1) for some i and j in a given range. We also have a query for updating a value at a given position.

We also have some additional constraints. There are at most different values ai — it's easy to prove.

So the main idea is to store different segment trees (for every value of ai). In the segment tree for a value X we will consider only elements with values  ≥ X. For simplicity let's assume that in the segment tree all positions with value  ≥ X are set to 1 and all other to 0. Then if we want to find the maximum length of an interval [i;j] inside our query interval such that min(ai, ai + 1, ..., aj - 1) >  = X we can simply find the length of the longest interval in the segment tree for X with all elements equal to 1.

Then the query can be done by considering every segment tree, doing query for each of them and then getting max X * TX.query(l, r).

The update can be done by simply preforming at most updates in segment trees.

The only problem with this solution is the memory. It will consume memory. Fortunately we can use a persistent segment tree instead of a regular one and this way the memory will be .

PS: I was to lazy to write it during the contest, but is should pass.

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

    That is so brutal! I hope there is a nicer solution!

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

    Wow. ._. I thought of this solution as well, but didn't code it cause I was sure it would get TLE >_<

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

ignore*

found my mistake in div2c

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

How 2 solve D ? I do not even understand why there is mention of fflush

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

    fflush is to let the system know that you have print something so it can response to it. (Or under normal condition all the outputs are sent together at the end to save time.)

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

      Does it mean that the input and output of this question are interactive? I first encountered this type of problem.So I need to design the query sequence?

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

        Yes, you may decide what the next query will be based on what you have received.

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

So fast system testing

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

System Testing Pending
Refresh Page after 10min
79% done

This times system testing is running at speed of thunder lmao :D

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

upvote for the very quick testing

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

I could succeed to hack one's code ,if the website can run faster ,and my rank will be rise 200 and more!!! why my hack in the last minute can't do it's proper work?

By the way, how to solve the f**k problem C?

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

Easy solution for C. if n<3, brute force. otherwise, xor first n-3 numbers,say res.(res = 0^1^...^(n-4)) Then 0,1,...,(n-4),(1<<18),(1<<19),((1<<18)+(1<<19))^(x^res) is answer.

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

    I just randomly picked all but one numbers and force the last number to fit the requirement.
    No math here, great!

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

      You are lucky, your algorithm is incorrect. What if e.g. n=4 x=0 and your random pick is [1, 2, 3]?

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

        Read the question carefully, 0 is allowed so just 0 xor 1 xor 2 xor 3 = 0

        Although the last number did have a collision, I would throw everything away and restart for another try. If it always failed ( say, failed 100 times or so), It could be pretty sure that this was impossible and should print "NO". It's the same as what Miller-Rubbin primality test do.

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

          You are right about reading carefully, the example should have been n=4 x=1 with [1, 2, 3]. In your original message you didn't mention trying '100 times or so'. You'd have to be very unlucky indeed.

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

Easy solution for problem C : https://ideone.com/FZ6rfw

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

C with x=0 really made the problem trickier.

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

vintage_Vlad_Makeev, KAN, MikeMirzayanov, I have accidentally sent the same hack twice (the page did not reload and I sent it from a new tab). Now I have two unsuccessful attempts. Can it be fixed?

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

Looks like I'm finally going to div.1! I'm so happy, it was quite a long journey :)

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

Hello, actually my wrong solution for problem D passed main tests. Here is my solution — http://codeforces.net/contest/862/submission/30518750 and it runs into an infinite loop in the following case : "10"

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

    "10" is test case #121 (last), and seems your solution works on it.

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

      Thanks for the good news. Idk how its working but on my machine its not running. Just felt that in case the main tests were wrong, I should have informed.

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

Now my C solution failed for the stupidest reason, I forgot to print YES before the answer itself in one of the cases. Why is output so poorly formatted anyway? Isn't it the tradition of problem setting to print -1 when there is no solution?

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

    Somehow I managed to accumulate more downvotes than "is it rated" comments :D

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

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

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

After 17 fails and 1:49 my submission for D passed, but it failed again on 59th test. The worst feeling ever

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

nice problems, c is interesting for me and random_shuffle() solution hhe

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

How can one proove that random brute solution for C will not time-out ?

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

please don't make other rounds

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

can anyone please help me! This is my solution can someone please tell why is it a run time error one the codeforces compiler? it works in my system and had passed all the testcases! but then it gave a run time error?? thank you!

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

    At this statement if(fans[sizea]==0) you might be getting a runtime error as size of fans is sizea.

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

Does anyone knows what exactly compiler version and flags are used when you choose GNU C++11? I have a trouble with my solution http://codeforces.net/contest/862/submission/30520451. On my computer it answers 0 on first test using GCC 5.4.0, and on my friend's computer it returns the same answer using GCC 4.8. But test system thinks that answer is -273605408. What the problem?

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

    dude i guess they use something quite different because i had the same kind of issue! i ran your code in my computer and it gives 0. i guess codeforces has totally different compiler and flags. its just bad luck that we dont have their compiler version.

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

      May be we should ask admins about it? I have too few rating points to loose it that way :c

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

        Dude I asked KAN and he said it had nothing to do with compiler, actually I tried accessing memory that wasn't allotted so in that case it works sometimes and sometimes it doesn't! I guess something similar in your case too! Maybe but if you think there is still a problem you should approach. :)

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

          Well, then i should check my code again.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
      vector<int> pref_l(n);
      pref_l[0] = layers[0];
      if (max_l > 0) pref_l[1] = layers[1];
      for (int i = 2; i <= max_l; ++i) {
        pref_l[i] = pref_l[i - 2] + layers[i];
      }
    

    Here max_l can equal n and also you access pref_l[1] which might not exist if n is 1.

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

Can someone give me some links to good random algorithms tutorial. I see a lot of people used it to solve C.

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

i have got 237 point int this round keep doing well mahmoudbadawy thank you so much for this round and problem :)

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

for problem C you can just select first n-1 elements randomly (from 0 to 2^19-1) and see if the number that you need to get the desired xor is available. try it 100 times, if none of those 100 times works then print NO. this works because the probability the nth number will be available is approximately 1/5 so the probability you get it wrong is 1/5^100. Of course this is just a heuristic, you need some sort of uniformity argument but w/e.

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

    thats because 2^19-1 is approximately 5*10^5, so at least four fifths of the numbers are unnocupied.

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

      Wow, I used exatly the same algorithm here, same range and also tried 100 times.

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

        did it work? I had to fix one little thing, I used srand and rand(). You need a small modification because rand only goes up to 2^15-1.

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

          Yes, I made a little function to do that. int randInt(){return (rand() * RAND_MAX + rand()) % 524288;}

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

    Could you please elaborate a bit more on the 1/5 probability? Specially when we don't know the number of solutions. Also why (from 0 to 2^19-1) and not [0, 10^6]? Thanks!

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

      In the worst case ( n = 100000 ), we have 524288 numbers ([0, 524287]) to choose and 99999 numbers used. The last number y to choose, which is the xor sum of these 99999 numbers and the given x, has a probability 99999 / 524288 to bump into another used number. That's about 1/5 probability to fail.(note that y and x is one-to-one corresponding, so all these numbers have equal probability)

      And why we are not using [0, 10^6]? Let's take a smaller situation to think about. Say, the number limitation is 10, would you be ok to randomly pick up numbers from [0, 10]? For example, if you picked up 8 and 7, and 8 xor 7 is (1000)2 xor (0111) 2 = (1111)2 = 15, which is above the limitation. However, if you only choose number from [0, 7], then the forth binary digit will always be 0, so ther xor sum will be smaller than 8, of course smaller than 10.

      So that's what happening here, everything here will be less than 524288, since the 20th binary digit is always 0. There's no need to expand the range to 1000000.