2
\$\begingroup\$

Here is the link to the problem: Aladin on Kattis.com

Problem

Aladin was walking down the path one day when he found the strangest thing: N empty boxes right next to a weird alien machine. After a bit of fumbling around he got the machine to do something. The machine now accepts 4 integers \$L\$, \$R\$, \$A\$ and \$B\$. After that hitting the big red glowing button labeled "NE DIRAJ"1 causes the machine to go crazy and follow the next routine:

  • Set the number of stones in the box labeled L to A modulo B.
  • It proceeds to fly to the box labeled L + 1, and set the number of stones there to (2 ⋅ A) mod B.
  • It procedes to fly to the box labeled L + 2, and set the number of stones there to (3 ⋅ A) modB.
  • Generally, it visits each box labeled between L and R, and set the number of stones there to ((X − L + 1) ⋅ A) mod B, where X is the box label.
  • After it visits the box labeled R. It settles down for further instructions.

During the game Aladin wonders what is the total number of stones in some range of boxes.

Write a program that simulates the device and answers Aladin's questions.

Input

The first line contains two integers: the number of boxes \$N\$ (\$1 \le N \le 1000000000\$) and the number of queries \$Q\$ (\$1 \le Q \le 50000\$).

The next \$Q\$ lines contain information about the simulation.

If the line starts with 1, than it follows the format "1 L R A B" (\$1 \le L \le R \le N\$) (\$1 \le A, B \le 1000000\$), meaning that Aladin keyed in numbers \$L\$, \$R\$, \$A\$ and \$B\$ in the device and allowed the device to do its job.

If the line starts with 2, then it follows the format "2 L R" (\$1 \le L \le R \le N\$), meaning that Aladin wonders how many stones in total are ther stones are in boxes labeled \$L\$ to \$R\$ (inclusive).

Output

For each query beginning with 2 output the answer to that particular query. Queries should be processed in the order they are given in the input.

Sample Input 1

6 3
2 1 6
1 1 5 1 2
2 1 6

Sample Output 1

0
3

Sample Input 2

4 5
1 1 4 3 4
2 1 1
2 2 2
2 3 3
2 4 4

Sample Output 2

3
2
1
0

Sample Input 3

4 4
1 1 4 7 9
2 1 4
1 1 4 1 1
2 1 4

Sample Output 3

16
0
#include<iostream>
#include<fstream>
#include<string>

using namespace std;

long countStones(long, long, long, long, long, long);

int main(int __argc, char *__argv[])
{
    std::string filepath;
    long N, Q, *boxes;

  if(__argc == 2) {
    filepath = std::string(__argv[1]);
  }

  std::ifstream* infile = !filepath.empty() ? new std::ifstream(filepath.c_str()) : static_cast<std::ifstream*>(&std::cin);

  *infile >> N >> Q;

  long opt, L1 = 0, R1 = 0, L2 = 0, R2 = 0, A, B;

  for(long i = 1; i <= Q; i++) {
    *infile >> opt;

    if(opt == 1) {
      *infile >> L1 >> R1 >> A >> B;
    }
    if(opt == 2) {
      *infile >> L2 >> R2;
      cout << countStones(L1, R1, L2, R2, A, B) << endl;
    }
  }

    return 0;
}

long countStones(long L1, long R1, long L2, long R2, long A, long B) {
  long ret = 0, start = L1, end = R1;

  if(R2 < L1) return 0;
  if(L2 > R1) return 0;

  if (L2 > L1) start = L2;
  if (R2 < R1) end = R2;

  for(long i = start; i <= end; i++) {
    ret += ((i - L1 + 1) * A) % B;
  }

  return ret;
}

The problem works fine with all the with Sample Cases #1, #2, & #3. But when I upload the code on the website (open.kattis.com) it fails on the case #4, which is unknown to me. I couldn't find a logical error in my code.

Also, when I had written the code which was storing the modulo calculations for each box (array) the problem did pass the case #4 but failed #5 (Memory Exceeded). So I changed the code to NOT STORE the values in the array & just calculate on the fly & add it to the count of stones.

I need to modify the code so that it passes Test #4, whose input values are unknown to me. That is to find the logical error in the code.

\$\endgroup\$
4
\$\begingroup\$

Don't use underscore as a prefix. In most situations this is a reserved identifier. Defiantly never use double underscore in an identifier. This is reserved in all situations.

__argc  /// This is so wrong. It will break.

Read a couple of other C++ reviews. They all explain why this is a bad idea:

using namespace std;

This is not old school C. You don't need to declare the variables at the top of the function.

long N, Q, *boxes;

Declare them as close to the point of use as possible. This becomes important when your types have constructor/destructor (as they execute code). But it also makes the code easier to read as the type information is close to the usage of the object.

Please declare one variable per line (easier to read).

long    N;
long    Q;
long*   boxes; // The * belongs close to the type (as it is part of the type info).
               // PS you probably should not be using pointers. In modern C++ they
               // are vanishingly rare (as there is no ownership semantics associated
               // with a pointer).

Don't do this.

std::ifstream* infile = !filepath.empty() ? new std::ifstream(filepath.c_str()) : static_cast<std::ifstream*>(&std::cin)

Should I call delete on this? Yes if it is a file. No if it is std::cin. So not a good solution. Also std::cin is not a file stream so casting it is going to do nasty things. You should never cast things (it means you have something wrong with your design (or you are working at very low level (which most people should not be doing))).

But they are both std::istream. So you could do this.

std::ifstream   file;
if (!filepath.empty()) {
    file.open(filepath);       // Modern C++ allows std::string here.
}

std::istream& infile = !filepath.empty()
                             ? file 
                             : std::cin;

You may want to check that the read works:

*infile >> N >> Q;

Very easily done with:

if (infile >> N >> Q) {
    // Read was good.
    // Do stuff.
}

Main is special. So does not need a return code.

return 0;

So if your application never fails (ie always returns 0). Use this info. A missing return in main is an indication that the application never fails.

\$\endgroup\$
  • \$\begingroup\$ Code still fails at the Test #4 (on kattis.com) with your suggestions. \$\endgroup\$ – Kunal B. Jan 9 '15 at 1:23
  • \$\begingroup\$ @KunalB. That does not surprise me. Its not as if I was looking to fix your problems (that is not what this site is for). I did not look at the logic of your code. I was trying to explain to you some of your bad habits so that you would write better code. \$\endgroup\$ – Martin York Jan 9 '15 at 17:42
  • \$\begingroup\$ I am sorry if my words meant something else. But the code update was removed by someone. And the above comment was a comment to readers of original post to see the updated code (which was removed). So my comment's context changed. \$\endgroup\$ – Kunal B. Jan 9 '15 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.