Блог пользователя mahmoudbadawy

Автор mahmoudbadawy, история, 7 лет назад, По-английски

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

Условия задач Codeforces Round 435 (Div. 2)
  • Проголосовать: нравится
  • +353
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Cool.

»
7 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -60 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Is it ....emmmmm geometrical?

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -48 Проголосовать: не нравится

Is it rated?

»
7 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится -54 Проголосовать: не нравится

is it rated?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Gl & Hf to everyone!

»
7 лет назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it mathematical?

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Hope the server will work effiently

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

why the last contest was unrated?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

if repeted problem sucks

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

Hope someone from CodeForces notices this!

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I think it is fixed now.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Same here. Try test: 2 0

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Maybe RAND_MAX is 32767?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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 лет назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится

                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 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

How to solve C? Good problem in my opinion

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You failed systest because p can be zero right?

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

        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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    n — 2 random numbers and then generate last two.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      My problem was NO case :(

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

ignore*

found my mistake in div2c

»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

So fast system testing

»
7 лет назад, # |
Rev. 7   Проголосовать: нравится +11 Проголосовать: не нравится

System Testing Pending
Refresh Page after 10min
79% done

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

upvote for the very quick testing

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

C with x=0 really made the problem trickier.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится -59 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

please don't make other rounds

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://mirror.codeforces.com/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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
      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 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Rev. 6   Проголосовать: нравится +2 Проголосовать: не нравится

      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.